c ⃝Christophe Bertault - MPSI Arithmétique des entiers relatifs 1 Division dans

c ⃝Christophe Bertault - MPSI Arithmétique des entiers relatifs 1 Division dans Z 1.1 Relation de divisibilité Définition (Divisibilité, diviseur, multiple) Soient a, b ∈Z. On dit que a divise b, ou que a est un diviseur de b, ou que b est divisible par a, ou que b est un multiple de a, s’il existe k ∈Z tel que b = ak. Cette relation se note a|b. Théorème (Propriétés de la relation de divisibilité) Soient a, b, c, d ∈Z. (i) La relation de divisibilité | est réflexive et transitive sur Z, c’est même une relation d’ordre sur N, mais elle n’est pas antisymétrique sur Z car : a|b et b|a ⇐ ⇒ |a| = |b| ⇐ ⇒ a = b ou a = −b. (ii) Si d|a et si d|b, alors d (au + bv) pour tous u, v ∈Z. (iii) Si a|b et si c|d, alors ac|bd. En particulier, si a|b, alors ak|bk pour tout k ∈N. Démonstration (i) Déjà prouvé au chapitre « Relations d’ordre ». (ii) Si d|a et d|b, alors a = dk et b = dl pour certains k, l ∈Z, donc au + bv = d(ku + vl) avec ku + vl ∈Z pour tous u, v ∈Z, donc enfin d (au + bv). (iii) Si a|b et c|d, alors b = ak et d = cl pour certains k, l ∈Z, donc bd = (ac)(kl) avec kl ∈Z, bref ac|bd. ■ 1.2 Relation de congruence modulo un entier Définition (Relation de congruence modulo un entier) Soient n ∈N et a, b ∈Z. On dit que a est congru à b modulo n si n (b −a), i.e. s’il existe k ∈Z tel que b = a + kn. Cette relation se note a ≡b [n].    Explication Les relations de congruence généralisent la relation de divisibilité : n|a ⇐ ⇒ a ≡0 [n]. Théorème (Propriétés de la relation de congruence) Soient a, a′, b, b′ ∈Z et m, n ∈N. (i) Relation d’équivalence : La relation · ≡· [n] est réflexive, symétrique et transitive. (ii) Somme : Si a ≡b [n] et si a′ ≡b′ [n], alors a + a′ ≡b + b′ [n]. (iii) Produit : Si a ≡b [n] et si a′ ≡b′ [n], alors aa′ ≡bb′ [n]. En particulier, si a ≡b [n], alors ak ≡bk [n] pour tout k ∈N. (iv) Multiplication/division par un entier non nul : Si m ̸= 0 : a ≡b [n] ⇐ ⇒ am ≡bm [mn]. Démonstration (i) Réflexivité et symétrie sont immédiates, montrons seulement la transitivité. Soient a, b, c ∈Z. Si a ≡b [n] et b ≡c [n], alors n (b −a) et n (c −b), donc par somme n (c −a), i.e. a ≡c [n]. (ii) Si a ≡b [n] et a′ ≡b′ [n], alors n (b −a) et n (b′ −a′), donc par somme n (b + b′) −(a + a′)
, i.e. a + a′ ≡b + b′ [n]. (iii) Remarque : bb′ −aa′ = b(b′ −a′) + a′(b −a). Du coup, si a ≡b [n] et a′ ≡b′ [n], alors n (b −a) et n (b′ −a′), donc n b(b′ −a′) + a′(b −a)
, i.e. n (bb′ −aa′), ou encore aa′ ≡bb′ [n]. (iv) Enfin : a ≡b [n] ⇐ ⇒ n (b −a) m̸=0 ⇐ ⇒ mn m(b −a) ⇐ ⇒ am ≡bm [mn]. ■ 1 c ⃝Christophe Bertault - MPSI 1.3 Division euclidienne Théorème (Division euclidienne) Soient a ∈Z et b ∈N∗. Il existe un et un seul couple (q, r) ∈Z × N tel que : a = bq + r et 0 ⩽r ⩽b −1 (ou encore : 0 ⩽r < b). On appelle a le dividende de la division euclidienne de a par b, b son diviseur, q son quotient et r son reste. Par ailleurs : q = ja b k et r ≡a [b].    Explication • Le théorème de la division euclidienne est un résultat d’existence et d’unicité : voilà l’essentiel. • En termes de congruences, le théorème de la division euclidienne affirme simplement que tout entier relatif a est congru modulo b à un unique entier r compris entre 0 et b −1. Par exemple, on peut ramener l’entier a = 123 à l’un des entiers 0, 1, 2, 3 ou 4 modulo b = 5. Précisément : 123 |{z} a = 5 |{z} b × 24 |{z} q + 3 |{z} r , et donc 123 ≡3 [5]. Démonstration • Existence : L’idée de la preuve est simple. Si a est positif, on lui retranche b une fois, deux fois, trois fois. . . jusqu’à ce que a ait presque complètement fondu, c’est-à-dire jusqu’au moment où le résultat est compris entre 0 et b −1. Si a est négatif, on fait pareil mais en ajoutant b au lieu de le retrancher. L’ensemble D = n a −bk o k∈Z ∩N est une partie non vide de N — il contient a si a ⩾0 et a(1 −b) si a < 0 — donc possède un plus petit élément r. Pour un certain q ∈Z, on peut donc écrire ceci : a = bq + r, et bien sûr r ⩾0. Se peut-il qu’on ait r ⩾b ? Si c’était le cas, a −b(q + 1) = r −b serait un élément de D strictement plus petit que r = min D — impossible. Conclusion : 0 ⩽r ⩽b −1. • Unicité : Soient (q, r) et (q′, r′) deux couples de la division euclidienne de a par b. Aussitôt |r′ −r| ⩽b −1, mais par ailleurs b(q −q′) = r′ −r. Supposons q ̸= q′. Dans ce cas |q −q′| ⩾1, donc : b ⩽b|q −q′| = |r′ −r| ⩽b −1, donc b ⩽b −1 — contradiction. Conclusion : q = q′, donc aussitôt r = a −bq = a −bq′ = r′. • Pour finir, comme 0 ⩽r = a −bq < b, alors : a b −1 < q ⩽a b , donc en effet q = ja b k . ■    En pratique (Algorithme de la division euclidienne) On vient de le voir, le couple (q, r) de la division euclidienne de a par b se calcule à partir de a par une série d’additions/soustractions. Hélas, si le principe est simple, sa mise en œuvre paraît pénible. Pour diviser 1000 par 3, sommes-nous vraiment obligés d’effectuer 333 soustractions ? Oui et non. En réalité, vous pratiquez sans le savoir la division euclidienne depuis votre plus tendre enfance. Tâchons de le comprendre sur la division de 347 par 5. Dans un premier temps, on retranche en apparence 6 × 5 = 30 de 34, mais en fait on retranche 60 × 5 = 300 de 347 puisque le « 6 » apparaît comme chiffre des dizaines dans le quotient. Dans un second temps, on retranche 9 × 5 = 45 de 47. Au total, on a donc effectué 69 soustractions mais en deux fois seulement : d’abord 60, puis 9. Le reste obtenu est 2. 3 4 7 −3 0 (0) 4 7 −4 5 2 5 6 9 Conclusion : diviser, c’est soustraire. Pour un ordinateur, un grand nombre de soustractions n’est pas un problème. Pour nous autres cerveaux c’en est un. Nous compensons en apprenant et en utilisant les tables de multiplication, car ça nous le faisons vite et bien. C’est grâce aux tables de multiplication que nous avons trouvé les chiffres « 6 » et « 9 » du quotient dans l’exemple précédent. Exemple Soient x, y, z ∈Z trois entiers solutions de l’équation de Fermat x3 + y3 = z3. Alors l’un des entiers x, y ou z est divisible par 3. En effet Raisonnons par l’absurde en supposant que ni x ni y ni z n’est divisible par 3. x [9] x2 [9] x3 [9] 1 1 1 2 4 8 ≡−1 4 16 ≡−2 −8 ≡1 5 ≡−4 16 ≡−2 8 ≡−1 7 ≡−2 4 −8 ≡1 8 ≡−1 1 −1 Alors le reste de la division euclidienne de x par 9 est l’un des entiers 1, 2, 4, 5, 7, 8 — on peut rejeter les cas 0, 3 et 6. Etudions un à un ces différents cas dans le tableau ci-contre. Il en ressort que x3 ≡±1 [9]. On montrerait de même que y3 ≡±1 [9] et que z3 ≡±1 [9]. Or par hypothèse x3 + y3 ≡z3 [9]. A gauche on a modulo 9 soit 1 + 1 = 2, soit 1 −1 = 0, soit −1 + 1 = 0, soit −1 −1 = −2, et à droite ±1. Impossible ! 2 c ⃝Christophe Bertault - MPSI Exemple Le reste de la division euclidienne de 265362 par 7 est 2. En effet La démonstration de ce résultat est très longue si on applique l’algorithme précédent comme un rustre, car l’entier 265362 possède près de 20000 décimales. Or on remarque que 23 ≡8 ≡1 [7]. uploads/Management/ cours-arithmetique-des-entiers-relatifs-14 1 .pdf

Documents similaires

c ⃝Christophe Bertault - MPSI Arithmétique des entiers relatifs 1 Division dans 0 0

CHAPITRE V : LA GESTION DE LA RELATION CLIENT (CUSTOMER RELATIONSHIP MANAGEMENT 0 0

Sommaire Problématique et introduction générale................................ 0 0

Les fiches En Lignes de La lettre du CEDIP* Fiche n° 77 Septembre 2017 Des clés 0 0

1 Présentation Présentation Bilans de production Bilans de production des cinq 0 0

SATISFACTION DU CLIENT ET EFFICIENCE DU PERSONNEL EN CONTACT DANS LA RELATION D 0 0

MARKETING RELATIONNEL Pourquoi Marketers et RRH? Pour un RRH: Les RH sont au c 0 0

Curriculum Vitae Nom : FERHANE Prénom : FETHI Adresse : Villa N°31 cité Fellaou 0 0

1 L’humour … à quoi ça sert ?... Enquête sur l’humour dans l’activité d’animate 0 0

Présenter par: - Hamza med maslouhy - Hamza matmit LA COMMUNICATION AU SEIN DES 0 0

• Détails
• Publié le Fev 21, 2022
• Catégorie Management
• Langue French
• Taille du fichier 0.1527MB