c ⃝Christophe Bertault – Mathématiques en MPSI Arithmétique des entiers relatif
c ⃝Christophe Bertault – Mathématiques en 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 une relation d’ordre sur N mais elle est seulement réflexive et transitive 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. Explication Dans ce chapitre entièrement dévolu à la relation de divisibilité, toute expression comme « plus grand » ou « minorant » est à comprendre au sens de la divisibilité sur N et non au sens de la relation ⩽. Ces deux relations ne sont pas sans lien cela dit, gardez bien en tête que pour tous a, b ∈N∗— on exclut 0, attention : a|b = ⇒ a ⩽b. Démonstration (i) Si a|b et b|a, alors b = ak et a = bl pour certains k, l ∈Z, donc b = bkl. – Si b = 0, alors a = bl = 0 donc |a| = |b|. – Si b ̸= 0, alors kl = 1, donc soit k = l = 1, soit k = l = −1, i.e. soit a = b, soit a = −b, i.e. |a| = |b|. (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. ■ Définition (Diviseur/multiple commun) Soient a1, . . . , ar ∈Z. • On appelle diviseur commun de a1, . . . , ar tout entier relatif qui divise à la fois a1, . . . , ar. • On appelle multiple commun de a1, . . . , ar tout entier relatif divisible à la fois par a1, . . . , ar. Explication Dans le cas où a1, . . . , ar sont positifs, alors au sens de la divisibilité qui est une relation d’ordre : – les diviseurs communs positifs de a1, . . . , ar sont exactement les minorants de n a1, . . . , ar o , – les multiples communs positifs de a1, . . . , ar sont exactement les majorants de n a1, . . . , ar o . Exemple Les diviseurs positifs de 12 sont 1, 2, 3, 4, 6 et 12, ceux de 18 sont 1, 2, 3, 6, 9 et 18. Leurs diviseurs communs positifs sont donc 1, 2, 3 et 6. Leurs multiples communs sont tous les multiples de 36 — ce que nous ne chercherons pas à justifier proprement pour le moment. 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]. 1 c ⃝Christophe Bertault – Mathématiques en MPSI 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 modulo un entier) Soient a, a′, b, b′ ∈Z et m, n ∈N. (i) La relation ≡[n] est une relation d’équivalence sur Z. (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 L’assertion (i) a été prouvée au chapitre « Relations binaires ». (ii) Si a ≡b [n] et a′ ≡b′ [n], alors n divise b −a et b′ −a′, donc aussi (b + b′) −(a + a′) par somme. Ainsi 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 divise b −a et b′ −a′, donc aussi b(b′ −a′) + a′(b −a) = bb′ −aa′. Ainsi aa′ ≡bb′ [n]. (iv) Enfin : a ≡b [n] ⇐ ⇒ n (b −a) m̸=0 ⇐ ⇒ mn m(b −a) ⇐ ⇒ am ≡bm [mn]. ■ 1.3 Division euclidienne Théorème (Théorème de la 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. • On peut reformuler ce théorème en termes de congruences : ∀a ∈Z, ∃! r ∈J0, b −1K/ a ≡r [b]. Cette proposition affirme simplement que tout entier relatif a est congru modulo b à un unique entier r compris entre 0 et b −1. L’ensemble quotient de Z par la relation ≡ [n] est donc l’ensemble n nZ, nZ + 1, . . . , nZ + n −1 o à n éléments noté généralement Z nZ. Par exemple, on peut ramener 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 , 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 que a = bq + r avec 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 . ■ 2 c ⃝Christophe Bertault – Mathématiques en MPSI 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 uploads/Management/ cours-arithmetique-des-entiers-relatifs 1 .pdf
Documents similaires
-
21
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Dec 26, 2021
- Catégorie Management
- Langue French
- Taille du fichier 0.1876MB