Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

c ⃝Laurent Garcin MPSI Lycée Saint-Exupéry ARITHMÉTIQUE DES ENTIERS RELATIFS Co

c ⃝Laurent Garcin MPSI Lycée Saint-Exupéry ARITHMÉTIQUE DES ENTIERS RELATIFS Commençons par une propriété fondamentale de l’ensemble des entiers naturels. Théorème 0.1 Toute partie non vide et majorée de N possède un plus grand élément. Toute partie non vide de N possède un plus petit élément. Remarque. Toute partie non vide et minorée de Z admet un plus petit élément. Toute partie non vide et majorée de Z admet un plus grand élément. 1 Division dans Z 1.1 Relation de divisibilité Déﬁnition 1.1 (Divisibilité, diviseur, multiple) Soient a, b ∈Z. On dit que a divise b et on note a|b s’il existe k ∈Z tel que a = kb. Dans ce cas, on dit que a est un diviseur de b ou que b est un multiple de a. Remarque. 1 divise tous les entiers. 0 est divisible par tous les entiers. Proposition 1.2 (Propriétés de la divisibilité) Soient a, b, c, d des entiers relatifs. Réﬂexivité a|a. Transitivité Si a|b et b|c alors a|c. « Pseudo-antisymétrie » Si a|b et b|a, alors |a| = |b|. Combinaison linéaire Si d|a et d|b, alors d|au + bv pour tout (u, v) ∈Z2. Produit Si a|b et c|d, alors ac|bd. En particulier, si a|b alors an|bn pour tout n ∈N. Multiplication/division par un entier Si d ̸= 0, a|b ⇐ ⇒ad|bd. Attention ! En arithmétique, on travaille sur des entiers. On évite, autant que faire se peut, de manipuler des fractions quand bien même ces fractions seraient entières. Si, par exemple, a divise b, la fraction b a est bien un entier mais plutôt que de manipuler la fraction b a, il est préférable de déﬁnir l’entier k tel que b = ka et de travailler avec cet entier k. Vous verrez que cela vous évitera nombre d’erreurs. 1.2 Relation de congruence La relation de congruence est une extension de la relation de divisibilité. Déﬁnition 1.3 (Congruence) Soient a, b ∈Z et n ∈N. On dit que a et b sont congrus modulo n si n|b −a i.e. s’il existe k ∈Z tel que b = a + kn. On note alors a ≡b[n]. http://laurentb.garcin.free.fr 1 c ⃝Laurent Garcin MPSI Lycée Saint-Exupéry Remarque. En particulier a ≡0[n] signiﬁe que n|a. EXERCICE 1. Que signiﬁe a ≡0[2] et a ≡1[2] ? Proposition 1.4 (Propriétés de la congruence) Soient a, b, c, d ∈Z et n ∈dN. (i) On dit que la relation de congruence modulo n est une relation d’équivalence car elle vériﬁe les conditions suivantes. Réﬂexivité a ≡a[n]. Transitivité Si a ≡b[n] et b ≡c[n] alors a ≡c[n]. Symétrie Si a ≡b[n], alors b ≡a[n]. (ii) Si a ≡b[n] et c ≡d[n], alors a + c ≡b + d[n]. (iii) Si a ≡b[n] et c ≡d[n], alors ac ≡bd[n]. En particulier, si a ≡b[n], alors ak ≡bk[n] pour tout k ∈N. (iv) Soit m ∈N∗. Alors a ≡b[n] ⇐ ⇒am ≡bm[mn]. La congruence, quoique hors programme en première année, est tout de même très utile en pratique comme le montre la démonstration des critères de divisibilité usuels suivants. EXERCICE 2. Critères de divisibilité usuels Démontrer les critères de divisibilité suivants. 1. Un entier est divisible par 3 si et seulement si la somme de ses chiﬀres est divisible par 3. 2. Un entier est divisible par 9 si et seulement si la somme de ses chiﬀres est divisible par 9. 3. Un entier est divisible par 11 si et seulement si la somme alternée de ses chiﬀres de rang pair moins la somme de ses chiﬀres de rang impair est divisible par 11. 1.3 Division euclidienne Proposition 1.5 (Division euclidienne) Soient a ∈Z et b ∈N∗. Alors il existe un unique couple d’entiers (q, r) ∈Z × N vériﬁant : (i) a = bq + r (ii) 0 ⩽r ⩽b −1 a s’appelle le dividende, b le diviseur, q le quotient, et r le reste. Attention ! Ne jamais oublier la deuxième condition sinon il n’y a plus unicité. Remarque. En termes de congruence, on a donc a ≡r[b]. De plus, q = ⌊a b⌋. Proposition 1.6 Soient a ∈Z et b ∈N∗. Alors b divise a si et seulement si le reste de la division euclidienne de a par b est nul. EXERCICE 3. http://laurentb.garcin.free.fr 2 c ⃝Laurent Garcin MPSI Lycée Saint-Exupéry Quel est le reste de la division euclidienne de 22009 par 7. Les sous-groupes de (Z, +) sont les aZ avec a ∈Z. De plus, on a : (i) aZ ⊂bZ ⇐ ⇒b|a. (ii) aZ = bZ ⇐ ⇒a = ±b. Sous-groupes de (Z, +) 2 Diviseurs et multiples communs Déﬁnition 2.1 Soient a, b ∈Z. On appelle diviseur commun de a et b tout entier qui divise à la fois a et b. On appelle multiple commun de a et b tout entier qui est à la fois multiple de a et multiple de b. 2.1 PGCD Déﬁnition 2.2 (PGCD) Soient a, b ∈Z. On appelle plus grand commun diviseur (PGCD) de a et b tout entier d ∈Z vériﬁant : (i) d est un diviseur commun de a et b i.e. d|a et d|b ; (ii) tout diviseur commun de a et b divise d i.e. ∀δ ∈Z, (δ|a et δ|b) ⇒δ|d. Remarque. Le pgcd est le plus grand au sens de la divisibilité : si a, b, d ∈N, d est la borne inférieure de la partie {a, b} pour la relation d’ordre que constitue la divisibilité. Proposition 2.3 (Existence et « unicité » du pgcd) Soient a, b ∈Z. Il existe un unique pgcd positif de a et b. On le note a ∧b. Deux pgcd de a et b sont égaux ou opposés. Remarque. On montre en fait que aZ + bZ = (a ∧b)Z. Méthode Prouver que deux couples d’entiers ont le même pgcd Soient (a, b) et (c, d) deux couples d’entiers relatifs. Pour montrer que a ∧b = c ∧d, on peut : ◮prouver que tout diviseur commun de a et b est un diviseur commun de c et d et réciproquement ; ◮ou prouver que a ∧b divise c et d et que c ∧b divise a et b. Proposition 2.4 (Propriétés du pgcd) Soient a, b ∈Z. (i) Pour tout k ∈Z, ka ∧kb = |k|(a ∧b). (ii) Pour tout diviseur commun d ̸= 0 de a et b, a d ∧b d = a ∧b d . http://laurentb.garcin.free.fr 3 c ⃝Laurent Garcin MPSI Lycée Saint-Exupéry Lemme 2.5 Soit a = bq + r la division euclidienne de a ∈Z par b ∈N∗. Alors a ∧b = b ∧r. L’algorithme suivant permet de déterminer le pgcd de deux entiers par une succession de divisions euclidiennes. On déﬁnit une suite (rn) de la manière suivante : 1. On pose r0 = a et r1 = b. 2. Pour n ⩾1, rn+1 est le reste de la division euclidienne de rn−1 par rn. (rn) est une suite strictement décroissante d’entiers naturels (à partir du rang 1) : elle est donc nulle à partir d’un certain rang. Soit N l’indice du dernier terme non nul. Le lemme précédent montre que rN = a ∧b. Algorithme d’Euclide Exemple 1. Déterminons le pgcd de 150 et 54. 150 = 2 × 54 + 42 54 = 1 × 42 + 12 42 = 3 × 12 + 6 12 = 2 × 6 + 0 On a donc 150 ∧54 = 6. Théorème 2.6 (Bezout) Soient a, b ∈Z. Il existe u, v ∈Z tels que au + bv = a ∧b. On appelle (u, v) un couple de coeﬃcients de Bezout. Une égalité du type précédent s’appelle une identité de Bezout. Attention ! Ces coeﬃcients ne sont pas uniques. Si (u0, v0) est un couple de coeﬃcients de Bezout, tous les couples de la forme (u0 + kb, v0 −ka) avec k ∈Z le sont aussi. La réciproque de ce théorème est fausse. Ainsi 6 = 6 × 6 −2 × 15 mais 6 ∧15 ̸= 6. On reprend les notations de l’algorithme d’Euclide. Pour tout n ⩾1, on a rn+1 = rn −qnrn−1. Le dernier reste non nul rN est le pgcd d de a et b. On abrégera combinaison linéaire à coeﬃcients entiers en CLE. On peut ainsi exprimer d comme une CLE de rN−1 et rN−2. Puis comme on peut exprimer rN−1 comme une CLE de rN−2 et rN−3, on peut exprimer d comme une CLE de rN−2 et rN−3, etc... Finalement on peut exprimer d comme une CLE de r0 = a et r1 = b. Plutôt qu’un long discours, reprenons l’exemple traité pour l’algorithme d’Euclide standard. Algorithme d’Euclide étendu Exemple 2. Réécrivons les divisions euclidiennes de l’algorithme d’Euclide standard sous une autre forme : 42 = 150 −2 × 54 12 = 54 −1 × 42 6 = 42 −3 × 12 On part ensuite du pgcd (c’est-à-dire 6) et on remonte les lignes de la manière suivante : 6 = 42 −3 × 12 = 42 −3 × (54 −1 × 42) = 4 uploads/Management/ arithmetique-des-entiers-relatifs.pdf