Éducation Nationale Française · MP2I
Arithmétique dans \(\mathbb{Z}\)
Les entiers relatifs \(\mathbb{Z}\) forment, sous leurs addition et multiplication usuelles, un monde clos suffisamment riche pour accueillir une théorie complète de la divisibilité. Ce chapitre la développe en cinq étapes. On part de la relation de divisibilité \(b \mid a\) et du théorème de la division euclidienne \(a = bq + r\), le seul outil algorithmique qui transforme la question « \(b\) divise-t-il \(a\) ? » en la question « le reste est-il nul ? ». On construit ensuite, sur la division euclidienne, le plus grand commun diviseur \(a \wedge b\), à la fois via l'algorithme itératif d'Euclide et via l'identité de Bézout \(a \wedge b = a u + b v\). On isole le cas particulier \(a \wedge b = 1\) (entiers premiers entre eux) et on démontre le théorème de Bézout et le lemme de Gauss — les deux moteurs de tous les raisonnements de divisibilité qui suivent. On introduit les nombres premiers, on démontre leur infinitude (Euclide) et l'existence/unicité de la décomposition en facteurs premiers \(n = \prod_p p^{v_p(n)}\), et on utilise la valuation \(p\)-adique \(v_p\) pour donner des formules explicites de \(a \wedge b\) et \(a \vee b\). On revient enfin sur la divisibilité sous une autre forme — les congruences modulo \(n\) — et on utilise la machinerie précédente pour caractériser l'inversibilité modulo \(n\) (\(a \wedge n = 1\)) et démontrer le petit théorème de Fermat \(a^p \equiv a \pmod p\) pour \(p\) premier.
L'approche est tout du long élémentaire : par convention dans ce chapitre, on ne fait pas appel au langage des structures algébriques. On évite donc, délibérément, toute référence aux groupes, anneaux, idéaux et morphismes ; l'ensemble \(\mathbb{Z}/n\mathbb{Z}\) apparaît dans la section sur les congruences seulement comme ensemble de \(n\) classes, avec un rappel explicite que sa structure d'anneau est hors programme et sera revue dans le chapitre Structures algébriques. Deux autres chapitres prolongent ce travail : Arithmétique des polynômes rejoue toute l'histoire pour \(\mathbb{K}[X]\) à la place de \(\mathbb{Z}\) (division euclidienne, PGCD, Bézout, Gauss, irréductibilité), et Structures algébriques reformule la divisibilité, les idéaux et l'arithmétique modulaire dans le cadre abstrait.
Convention permanente. Tout au long de ce chapitre, un diviseur est toujours un entier non nul. Chaque fois qu'on écrit « \(d \mid a\) », on suppose tacitement \(d \in \mathbb{Z}^*\). En particulier \(\operatorname{div}(0) = \mathbb{Z}^*\) (tout entier non nul divise \(0\)). On utilise \(\mathbb{N} = \{0, 1, 2, \dots\}\) et \(\mathbb{N}^* = \mathbb{N} \setminus \{0\}\). Les notations \(a \wedge b\) (plus grand commun diviseur) et \(a \vee b\) (plus petit commun multiple) sont standard.
L'approche est tout du long élémentaire : par convention dans ce chapitre, on ne fait pas appel au langage des structures algébriques. On évite donc, délibérément, toute référence aux groupes, anneaux, idéaux et morphismes ; l'ensemble \(\mathbb{Z}/n\mathbb{Z}\) apparaît dans la section sur les congruences seulement comme ensemble de \(n\) classes, avec un rappel explicite que sa structure d'anneau est hors programme et sera revue dans le chapitre Structures algébriques. Deux autres chapitres prolongent ce travail : Arithmétique des polynômes rejoue toute l'histoire pour \(\mathbb{K}[X]\) à la place de \(\mathbb{Z}\) (division euclidienne, PGCD, Bézout, Gauss, irréductibilité), et Structures algébriques reformule la divisibilité, les idéaux et l'arithmétique modulaire dans le cadre abstrait.
Convention permanente. Tout au long de ce chapitre, un diviseur est toujours un entier non nul. Chaque fois qu'on écrit « \(d \mid a\) », on suppose tacitement \(d \in \mathbb{Z}^*\). En particulier \(\operatorname{div}(0) = \mathbb{Z}^*\) (tout entier non nul divise \(0\)). On utilise \(\mathbb{N} = \{0, 1, 2, \dots\}\) et \(\mathbb{N}^* = \mathbb{N} \setminus \{0\}\). Les notations \(a \wedge b\) (plus grand commun diviseur) et \(a \vee b\) (plus petit commun multiple) sont standard.
I
Divisibilité et division euclidienne
Deux définitions, un théorème. La définition de la divisibilité est le point d'entrée du chapitre ; la division euclidienne est l'outil algorithmique qui convertit « \(b \mid a\) ? » en « le reste est-il nul ? ». La spécialité de Terminale couvre déjà les deux — on les rappelle brièvement, on les énonce et démontre rigoureusement, et on étend l'énoncé de la division euclidienne aux dividendes négatifs.
I.1
Relation de divisibilité
On dit que \(b\) divise \(a\) si \(a\) est un multiple entier de \(b\). La formulation de Terminale est informelle (« \(a = b k\) pour un certain entier \(k\) ») ; on l'énonce formellement et on rappelle la convention selon laquelle un diviseur est toujours non nul (sans quoi la relation \(0 \mid a\) rendrait la relation dégénérée).
Définition — Divisibilité
Soient \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}^*\). On dit que \(b\) divise \(a\), et on note \(b \mid a\), s'il existe \(k \in \mathbb{Z}\) tel que \(a = b k\). On dit aussi que \(a\) est un multiple de \(b\), ou que \(b\) est un diviseur de \(a\).Notations :
- \(a \mathbb{Z} = \{a k : k \in \mathbb{Z}\}\) est l'ensemble des multiples de \(a\) ;
- \(\operatorname{div}(a) = \{d \in \mathbb{Z}^* : d \mid a\}\) est l'ensemble des diviseurs de \(a\) (une partie de \(\mathbb{Z}^*\) par la convention permanente).
Exemple
\(\operatorname{div}(12) = \{\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12\}\). \(\operatorname{div}(0) = \mathbb{Z}^*\) car tout entier non nul \(d\) vérifie \(0 = d \cdot 0\). L'ensemble des multiples de \(5\) est \(5 \mathbb{Z} = \{\dots, -10, -5, 0, 5, 10, \dots\}\). Exemple
Pour tout \(a \in \mathbb{Z}^*\), \(1 \mid a\), \(-1 \mid a\), \(a \mid a\), et \(-a \mid a\). Donc \(\{\pm 1, \pm a\} \subset \operatorname{div}(a)\) toujours ; pour \(a \in \mathbb{N}\) avec \(a \geq 2\), l'égalité \(\operatorname{div}(a) = \{\pm 1, \pm a\}\) caractérise les nombres premiers (voir la section sur les nombres premiers plus bas). Proposition — Propriétés de la divisibilité
Soient \(a, b, c, d \in \mathbb{Z}\) et \(u, v \in \mathbb{Z}\). - Réflexivité et transitivité. Pour tout \(a \in \mathbb{Z}^*\), \(a \mid a\). Si \(a \mid b\) et \(b \mid c\) (avec \(a, b \in \mathbb{Z}^*\)), alors \(a \mid c\).
- Entiers associés. Pour \(a, b \in \mathbb{Z}^*\), \(a \mid b \text{ et } b \mid a \iff |a| = |b|\). De tels entiers sont dits associés. En particulier, restreint à \(\mathbb{N}^*\) ceci redonne l'antisymétrie de \(\mid\) : \(a \mid b\) et \(b \mid a \iff a = b\).
- Combinaisons linéaires. Si \(d \mid a\) et \(d \mid b\), alors \(d \mid (a u + b v)\) pour tout \(u, v \in \mathbb{Z}\).
- Produit. Si \(a \mid b\) et \(c \mid d\) (avec \(a, c \in \mathbb{Z}^*\)), alors \(a c \mid b d\). En particulier \(a^k \mid b^k\) pour tout \(k \in \mathbb{N}^*\) lorsque \(a \mid b\).
Réflexivité / transitivité. \(a = a \cdot 1\) donne \(a \mid a\). Si \(b = a k\) et \(c = b k'\), alors \(c = a (k k')\) avec \(k k' \in \mathbb{Z}\), donc \(a \mid c\).
Antisymétrie sur \(\mathbb{N}^*\). Si \(a \mid b\) et \(b \mid a\), écrire \(b = a k\) et \(a = b k'\). Alors \(a = a (k k')\), donc \(k k' = 1\) (car \(a \neq 0\)). Avec \(k, k' \in \mathbb{Z}\), cela force \(k = k' = \pm 1\), donc \(|a| = |b|\). Réciproquement si \(|a| = |b|\) alors \(a = \pm b\), donc chacun divise l'autre.
Combinaisons linéaires. De \(a = d k\) et \(b = d k'\), \(a u + b v = d (k u + k' v) \in d \mathbb{Z}\).
Produit. De \(b = a k\) et \(d = c k'\), \(b d = (a c)(k k')\), donc \(a c \mid b d\).
Antisymétrie sur \(\mathbb{N}^*\). Si \(a \mid b\) et \(b \mid a\), écrire \(b = a k\) et \(a = b k'\). Alors \(a = a (k k')\), donc \(k k' = 1\) (car \(a \neq 0\)). Avec \(k, k' \in \mathbb{Z}\), cela force \(k = k' = \pm 1\), donc \(|a| = |b|\). Réciproquement si \(|a| = |b|\) alors \(a = \pm b\), donc chacun divise l'autre.
Combinaisons linéaires. De \(a = d k\) et \(b = d k'\), \(a u + b v = d (k u + k' v) \in d \mathbb{Z}\).
Produit. De \(b = a k\) et \(d = c k'\), \(b d = (a c)(k k')\), donc \(a c \mid b d\).
Exemple
\(5 \mid 15\) et \(5 \mid 25\), donc par la propriété de combinaison linéaire \(5 \mid (15 \cdot 3 - 25 \cdot 2) = 45 - 50 = -5\), en accord avec \(5 \mid (-5)\). Méthode — Décider si \(b \mid a\)
Deux tests équivalents pour \(b \in \mathbb{Z}^*\), \(a \in \mathbb{Z}\) : - Test direct du quotient. Calculer \(a / b\) dans \(\mathbb{Q}\) ; vérifier si le résultat est entier.
- Test du reste (préféré pour \(a, b\) grands). Calculer la division euclidienne \(a = b q + r\) avec \(0 \leq r < |b|\) ; alors \(b \mid a \iff r = 0\) (sous-section suivante).
Compétences à pratiquer
- Démontrer des énoncés simples de divisibilité
I.2
Division euclidienne
La division euclidienne convertit la question de divisibilité en question algorithmique. L'énoncé de Terminale couvre \(a \in \mathbb{N}\), \(b \in \mathbb{N}^*\) ; on étend à \(a \in \mathbb{Z}\), avec le même diviseur \(b \in \mathbb{N}^*\) et la même contrainte sur le reste \(0 \leq r < b\). Le cas négatif est le piège classique : les étudiants doivent se souvenir que \(r\) est toujours positif ou nul.
Théorème — Division euclidienne
Pour tout \(a \in \mathbb{Z}\) et tout \(b \in \mathbb{N}^*\), il existe un unique couple \((q, r) \in \mathbb{Z} \times \mathbb{N}\) tel que $$ \textcolor{colorprop}{a = b q + r \quad \text{et} \quad 0 \leq r < b.} $$ L'entier \(a\) est le dividende, \(b\) le diviseur, \(q\) le quotient et \(r\) le reste de la division euclidienne de \(a\) par \(b\). De plus \(q = \lfloor a / b \rfloor\) (où \(\lfloor \cdot \rfloor\) est la partie entière, de \(\mathbb{R}\) dans \(\mathbb{Z}\)).
Existence. Posons \(R = \{a - b k : k \in \mathbb{Z}\} \cap \mathbb{N}\). L'ensemble \(R\) est non vide : si \(a \geq 0\), alors \(a = a - b \cdot 0 \in R\) ; si \(a < 0\), alors \(k = a\) donne \(a - b a = a (1 - b) \geq 0\) car \(1 - b \leq 0\) et \(a < 0\), donc \(a - b a \in R\). Comme partie non vide de \(\mathbb{N}\), \(R\) admet un plus petit élément ; notons-le \(r\), et écrivons \(r = a - b q\) pour un certain \(q \in \mathbb{Z}\), soit \(a = b q + r\) avec \(r \geq 0\). Il reste à montrer \(r < b\). Supposons par l'absurde \(r \geq b\). Alors \(r - b \in \mathbb{N}\) et \(r - b = a - b (q + 1) \in R\), ce qui contredit la minimalité de \(r\). Donc \(r < b\).
Unicité. Supposons \(a = b q + r = b q' + r'\) avec \(0 \leq r, r' < b\). Alors \(b (q - q') = r' - r\), donc \(|b (q - q')| = |r' - r| < b\), ce qui force \(|q - q'| < 1\). Comme \(q - q' \in \mathbb{Z}\), \(q = q'\), et donc \(r = a - b q = a - b q' = r'\).
Formule pour \(q\). De \(a = b q + r\) avec \(0 \leq r < b\), on divise par \(b > 0\) : \(a / b = q + r / b\) avec \(0 \leq r/b < 1\), donc \(q = \lfloor a / b \rfloor\).
Unicité. Supposons \(a = b q + r = b q' + r'\) avec \(0 \leq r, r' < b\). Alors \(b (q - q') = r' - r\), donc \(|b (q - q')| = |r' - r| < b\), ce qui force \(|q - q'| < 1\). Comme \(q - q' \in \mathbb{Z}\), \(q = q'\), et donc \(r = a - b q = a - b q' = r'\).
Formule pour \(q\). De \(a = b q + r\) avec \(0 \leq r < b\), on divise par \(b > 0\) : \(a / b = q + r / b\) avec \(0 \leq r/b < 1\), donc \(q = \lfloor a / b \rfloor\).
Exemple
Pour \(a = 23\), \(b = 5\) : \(23 = 5 \cdot 4 + 3\), donc \(q = 4\) et \(r = 3\). En effet \(\lfloor 23 / 5 \rfloor = \lfloor 4{,}6 \rfloor = 4\). Exemple — Dividende négatif — piège classique
Pour \(a = -23\), \(b = 5\) : non \(-23 = 5 \cdot (-4) - 3\), car le reste vaudrait alors \(-3 < 0\). La division euclidienne correcte est $$ \textcolor{colorprop}{-23 = 5 \cdot (-5) + 2,} $$ donc \(q = -5\) et \(r = 2\). Vérification : \(\lfloor -23 / 5 \rfloor = \lfloor -4{,}6 \rfloor = -5\) (la partie entière de \(-4{,}6\) est \(-5\), pas \(-4\)). Le reste est toujours dans \(\{0, 1, \dots, b - 1\}\). Proposition — Divisibilité via le reste
Pour \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^*\), le reste \(r\) de la division euclidienne de \(a\) par \(b\) vérifie $$ \textcolor{colorprop}{b \mid a \iff r = 0.} $$
\((\Leftarrow)\) Si \(r = 0\), alors \(a = b q\), donc \(b \mid a\).
\((\Rightarrow)\) Si \(b \mid a\), écrire \(a = b q'\) pour un certain \(q' \in \mathbb{Z}\). Alors \((q', 0)\) est un couple valide de division euclidienne (avec \(0 \leq 0 < b\)), et par unicité \((q, r) = (q', 0)\), donc \(r = 0\).
\((\Rightarrow)\) Si \(b \mid a\), écrire \(a = b q'\) pour un certain \(q' \in \mathbb{Z}\). Alors \((q', 0)\) est un couple valide de division euclidienne (avec \(0 \leq 0 < b\)), et par unicité \((q, r) = (q', 0)\), donc \(r = 0\).
Compétences à pratiquer
- Calculer restes et quotients
II
PGCD et algorithme d'Euclide
Le plus grand commun diviseur (PGCD) de deux entiers \(a\) et \(b\) est, intuitivement, le plus grand entier qui les divise tous les deux. Deux subtilités sont à signaler : (i) « plus grand » doit être précisé — plus grand au sens de l'ordre naturel \(\leq\) sur \(\mathbb{N}^*\) ou plus grand au sens de l'ordre de divisibilité \(\mid\) —, et le PGCD se trouve être le plus grand dans les deux sens ; (ii) le PGCD se calcule effectivement par l'algorithme d'Euclide, une suite itérée de divisions euclidiennes. On démontre ensuite l'identité centrale du chapitre : l'identité de Bézout \(a \wedge b = a u + b v\) pour certains \(u, v \in \mathbb{Z}\). De là la caractérisation « les diviseurs communs divisent le PGCD » tombe comme corollaire, et le PPCM \(a \vee b\) (ainsi que la formule \((a \wedge b)(a \vee b) = |a b|\)) suivent naturellement.
II.1
Définition du PGCD
On définit le PGCD comme le plus grand diviseur commun au sens de l'ordre naturel sur \(\mathbb{N}^*\).
Définition — Plus grand commun diviseur (PGCD)
Soient \(a, b \in \mathbb{N}\) non tous deux nuls. Le plus grand commun diviseur de \(a\) et \(b\), noté \(a \wedge b\), est le plus grand élément de \(\{d \in \mathbb{N}^* : d \mid a \text{ et } d \mid b\}\) pour l'ordre naturel \(\leq\) sur \(\mathbb{N}^*\). Par convention, \(0 \wedge 0 = 0\).Extension à \(\mathbb{Z}\). Pour \(a, b \in \mathbb{Z}\) non tous deux nuls, on pose \(a \wedge b := |a| \wedge |b|\).
L'ensemble \(\{d \in \mathbb{N}^* : d \mid a \text{ et } d \mid b\}\) est non vide (il contient \(1\)). Il est aussi fini : si \(a\) et \(b\) sont tous deux non nuls, tout diviseur commun est majoré par \(\min(|a|, |b|)\) ; si par exemple \(a = 0\) et \(b \neq 0\), les diviseurs communs positifs sont exactement les diviseurs positifs de \(|b|\), donc sont majorés par \(|b|\). Donc le maximum existe.
Exemple
\(12 \wedge 18 = 6\) : les diviseurs de \(12\) dans \(\mathbb{N}^*\) sont \(\{1, 2, 3, 4, 6, 12\}\), les diviseurs de \(18\) sont \(\{1, 2, 3, 6, 9, 18\}\), les diviseurs communs sont \(\{1, 2, 3, 6\}\), le maximum est \(6\). De plus \(a \wedge 1 = 1\) pour tout \(a \in \mathbb{Z}\), et \(a \wedge 0 = |a|\) pour tout \(a \in \mathbb{Z}^*\). Compétences à pratiquer
- Définition du PGCD
II.2
Algorithme d'Euclide
Le calcul algorithmique du PGCD repose sur une seule observation : quand un entier est réduit modulo l'autre, le PGCD ne change pas. Itérée, cette règle donne l'algorithme d'Euclide, et le PGCD se lit comme le dernier reste non nul.
Proposition — Idée fondamentale
Pour tout \(a \in \mathbb{Z}\) et tout \(b \in \mathbb{N}^*\), si \(a = b q + r\) est la division euclidienne de \(a\) par \(b\), alors $$ \textcolor{colorprop}{a \wedge b = b \wedge r.} $$ Plus généralement, si \(a, b, n \in \mathbb{Z}\) vérifient \(a \equiv b\) modulo \(n\) (c'est-à-dire \(n \mid (a - b)\), voir la section sur les congruences plus bas), alors \(a \wedge n = b \wedge n\).
On montre que l'ensemble des diviseurs communs à \(a\) et \(b\) est égal à l'ensemble des diviseurs communs à \(b\) et \(r\) ; le PGCD, défini comme le maximum de cet ensemble, est donc le même.
- \((\subset)\) Si \(d \mid a\) et \(d \mid b\), alors par combinaison linéaire \(d \mid (a - b q) = r\). Donc \(d\) divise \(b\) et \(r\).
- \((\supset)\) Si \(d \mid b\) et \(d \mid r\), alors \(d \mid (b q + r) = a\). Donc \(d\) divise \(a\) et \(b\).
Théorème — Existence du PGCD par l'algorithme d'Euclide
Soient \(a, b \in \mathbb{N}\) avec \(0 < b \leq a\). Définir une suite de restes par $$ r_0 = a, \quad r_1 = b, \quad r_{k+2} = \text{reste de la division euclidienne de } r_k \text{ par } r_{k+1} \quad \text{tant que } r_{k+1} > 0. $$ La suite s'arrête : il existe \(N \geq 1\) tel que \(r_N = 0\), et le PGCD est le dernier reste non nul : $$ \textcolor{colorprop}{a \wedge b = r_{N - 1}.} $$
Terminaison. Tant que \(r_{k+1} > 0\), la construction donne \(0 \leq r_{k+2} < r_{k+1}\), donc la suite des restes strictement positifs \(r_1, r_2, \dots\) est strictement décroissante dans \(\mathbb{N}^*\). Une suite strictement décroissante dans \(\mathbb{N}\) est finie ; il existe \(N\) tel que \(r_N = 0\).
Correction. Par l'« idée fondamentale » appliquée à chaque étape (division euclidienne de \(r_k\) par \(r_{k+1}\) donne quotient \(q_k\) et reste \(r_{k+2}\), avec \(r_k = r_{k+1} q_k + r_{k+2}\)), \(r_k \wedge r_{k+1} = r_{k+1} \wedge r_{k+2}\) pour tout \(k \in \{0, \dots, N-2\}\). En enchaînant, $$ a \wedge b = r_0 \wedge r_1 = r_1 \wedge r_2 = \cdots = r_{N-1} \wedge r_N = r_{N-1} \wedge 0 = r_{N-1}. $$
Correction. Par l'« idée fondamentale » appliquée à chaque étape (division euclidienne de \(r_k\) par \(r_{k+1}\) donne quotient \(q_k\) et reste \(r_{k+2}\), avec \(r_k = r_{k+1} q_k + r_{k+2}\)), \(r_k \wedge r_{k+1} = r_{k+1} \wedge r_{k+2}\) pour tout \(k \in \{0, \dots, N-2\}\). En enchaînant, $$ a \wedge b = r_0 \wedge r_1 = r_1 \wedge r_2 = \cdots = r_{N-1} \wedge r_N = r_{N-1} \wedge 0 = r_{N-1}. $$
Méthode — Calculer \(a \wedge b\) par l'algorithme d'Euclide
Supposer \(0 < b \leq a\). Tabuler les divisions euclidiennes successives : - Étape 1 : \(a = b \, q_1 + r_2\) avec \(0 \leq r_2 < b\).
- Étape 2 : \(b = r_2 \, q_2 + r_3\) avec \(0 \leq r_3 < r_2\).
- Étape \(k\) : \(r_k = r_{k+1} \, q_{k+1} + r_{k+2}\) avec \(0 \leq r_{k+2} < r_{k+1}\).
- S'arrêter dès qu'un reste est nul. Le dernier reste non nul est \(a \wedge b\).
Exemple
Calculer \(1542 \wedge 58\).
On applique l'algorithme d'Euclide : $$ \begin{aligned} 1542 &= 26 \cdot 58 + 34, \\
58 &= 1 \cdot 34 + 24, \\
34 &= 1 \cdot 24 + 10, \\
24 &= 2 \cdot 10 + 4, \\
10 &= 2 \cdot 4 + 2, \\
4 &= 2 \cdot 2 + 0. \end{aligned} $$ Le dernier reste non nul est \(2\), donc \(1542 \wedge 58 = 2\).
Compétences à pratiquer
- Calculer un PGCD par l'algorithme d'Euclide
II.3
Identité de Bézout
L'identité de Bézout est la face « combinaison linéaire » du PGCD : \(a \wedge b\) s'écrit \(a u + b v\) pour certains \(u, v \in \mathbb{Z}\). La démonstration réutilise la suite d'Euclide : chaque reste \(r_k\) s'écrit comme combinaison \(\mathbb{Z}\)-linéaire de \(a\) et \(b\), par récurrence. En pratique, on déroule l'algorithme d'Euclide vers l'avant puis on remonte par substitution pour extraire un couple \((u, v)\).
Théorème — Identité de Bézout
Pour tout \(a, b \in \mathbb{Z}\), il existe \(u, v \in \mathbb{Z}\) tels que $$ \textcolor{colorprop}{a \wedge b = a u + b v.} $$ Les entiers \(u, v\) ne sont pas uniques. Un couple \((u, v)\) vérifiant cette identité est appelé un couple de coefficients de Bézout de \((a, b)\).
Cas triviaux. Si \(a = b = 0\), alors \(a \wedge b = 0 = 0 \cdot u + 0 \cdot v\) pour tout \(u, v \in \mathbb{Z}\). Si \(b = 0\) et \(a \neq 0\), alors \(a \wedge 0 = |a| = a \cdot \mathrm{sgn}(a) + 0 \cdot 0\). Le cas \(a = 0\), \(b \neq 0\) est symétrique.
Cas général. On suppose désormais \(a\) et \(b\) non nuls. Remplacer \(a, b\) par \(|a|, |b|\) ne change pas le PGCD ; une identité de Bézout pour \(|a|, |b|\) donne alors une identité pour \(a, b\) en multipliant les coefficients par \(\mathrm{sgn}(a), \mathrm{sgn}(b)\). Donc sans perte de généralité \(0 < b \leq a\). On déroule l'algorithme d'Euclide : \(r_0 = a\), \(r_1 = b\), \(r_{k+2} = r_k - q_k r_{k+1}\) pour \(k \in \{0, \dots, N-2\}\), avec \(r_N = 0\) et \(r_{N-1} = a \wedge b\).
Démontrer par récurrence que pour tout \(k \in \{0, 1, \dots, N\}\), \(r_k \in a \mathbb{Z} + b \mathbb{Z}\) (c'est-à-dire s'écrit \(a u_k + b v_k\) pour certains \(u_k, v_k \in \mathbb{Z}\)).
Non-unicité. Si \((u, v)\) convient, alors \((u + b, v - a)\) aussi, puisque \(a (u + b) + b (v - a) = a u + b v\).
Cas général. On suppose désormais \(a\) et \(b\) non nuls. Remplacer \(a, b\) par \(|a|, |b|\) ne change pas le PGCD ; une identité de Bézout pour \(|a|, |b|\) donne alors une identité pour \(a, b\) en multipliant les coefficients par \(\mathrm{sgn}(a), \mathrm{sgn}(b)\). Donc sans perte de généralité \(0 < b \leq a\). On déroule l'algorithme d'Euclide : \(r_0 = a\), \(r_1 = b\), \(r_{k+2} = r_k - q_k r_{k+1}\) pour \(k \in \{0, \dots, N-2\}\), avec \(r_N = 0\) et \(r_{N-1} = a \wedge b\).
Démontrer par récurrence que pour tout \(k \in \{0, 1, \dots, N\}\), \(r_k \in a \mathbb{Z} + b \mathbb{Z}\) (c'est-à-dire s'écrit \(a u_k + b v_k\) pour certains \(u_k, v_k \in \mathbb{Z}\)).
- Initialisation. \(r_0 = a = a \cdot 1 + b \cdot 0\) et \(r_1 = b = a \cdot 0 + b \cdot 1\), donc la propriété est vraie pour \(k = 0, 1\).
- Hérédité. Supposer \(r_k = a u_k + b v_k\) et \(r_{k+1} = a u_{k+1} + b v_{k+1}\). Alors $$ \begin{aligned} r_{k+2} = r_k - q_k r_{k+1} &= a u_k + b v_k - q_k (a u_{k+1} + b v_{k+1}) \\ &= a (u_k - q_k u_{k+1}) + b (v_k - q_k v_{k+1}), \end{aligned} $$ donc \(r_{k+2} \in a \mathbb{Z} + b \mathbb{Z}\).
Non-unicité. Si \((u, v)\) convient, alors \((u + b, v - a)\) aussi, puisque \(a (u + b) + b (v - a) = a u + b v\).
Exemple — Non-unicité des coefficients de Bézout
\(4 \wedge 6 = 2\), et on peut vérifier à la fois $$ 2 = (-1) \cdot 4 + 1 \cdot 6 = 2 \cdot 4 + (-1) \cdot 6, $$ donc \((u, v) = (-1, 1)\) et \((u, v) = (2, -1)\) sont deux couples distincts de coefficients de Bézout. Méthode — Algorithme d'Euclide étendu
Pour calculer un couple de coefficients de Bézout, dérouler l'algorithme d'Euclide vers l'avant, puis remonter par substitution depuis le dernier reste non nul jusqu'aux entiers de départ.Étape 1 (descente). Tabuler \(r_0 = a\), \(r_1 = b\), \(r_{k+2} = r_k - q_k r_{k+1}\) jusqu'à ce qu'un \(r_N = 0\). Le PGCD est \(r_{N-1}\).
Cas particulier \(b \mid a\). Si le premier reste est nul (c'est-à-dire \(a = b q_0\)), alors \(a \wedge b = b\) et une identité de Bézout est immédiate : \(b = 0 \cdot a + 1 \cdot b\). Pas de remontée à effectuer.
Étape 2 (remontée). Sinon (l'algorithme comporte au moins deux divisions non triviales), en partant de \(r_{N-1} = r_{N-3} - q_{N-3} r_{N-2}\), substituer à plusieurs reprises l'équation précédente \(r_{N-2} = r_{N-4} - q_{N-4} r_{N-3}\) pour exprimer \(r_{N-1}\) comme combinaison \(\mathbb{Z}\)-linéaire de \(r_{N-3}\) et \(r_{N-4}\), puis de \(r_{N-5}\) et \(r_{N-4}\), …, jusqu'à atteindre une combinaison de \(r_0 = a\) et \(r_1 = b\).
Exemple
Calculer des coefficients de Bézout de \(3080\) et \(525\).
Étape 1 (descente Euclide). $$ \begin{aligned} 3080 &= 5 \cdot 525 + 455, \\
525 &= 1 \cdot 455 + 70, \\
455 &= 6 \cdot 70 + 35, \\
70 &= 2 \cdot 35 + 0. \end{aligned} $$ Dernier reste non nul : \(35\), donc \(3080 \wedge 525 = 35\).
Étape 2 (remontée). $$ \begin{aligned} 35 &= 455 - 6 \cdot 70 \\ &= 455 - 6 \cdot (525 - 1 \cdot 455) = 7 \cdot 455 - 6 \cdot 525 \\ &= 7 \cdot (3080 - 5 \cdot 525) - 6 \cdot 525 = 7 \cdot 3080 - 41 \cdot 525. \end{aligned} $$ Donc \((u, v) = (7, -41)\) est un couple de coefficients de Bézout : \(35 = 7 \cdot 3080 - 41 \cdot 525\). Vérification : \(7 \cdot 3080 = 21560\), \(41 \cdot 525 = 21525\), \(21560 - 21525 = 35\). \(\checkmark\)
Étape 2 (remontée). $$ \begin{aligned} 35 &= 455 - 6 \cdot 70 \\ &= 455 - 6 \cdot (525 - 1 \cdot 455) = 7 \cdot 455 - 6 \cdot 525 \\ &= 7 \cdot (3080 - 5 \cdot 525) - 6 \cdot 525 = 7 \cdot 3080 - 41 \cdot 525. \end{aligned} $$ Donc \((u, v) = (7, -41)\) est un couple de coefficients de Bézout : \(35 = 7 \cdot 3080 - 41 \cdot 525\). Vérification : \(7 \cdot 3080 = 21560\), \(41 \cdot 525 = 21525\), \(21560 - 21525 = 35\). \(\checkmark\)
Compétences à pratiquer
- Calculer des coefficients de Bézout
II.4
Diviseurs communs et PGCD
Munis de l'identité de Bézout, la caractérisation du PGCD par son ensemble de diviseurs tombe comme un corollaire immédiat.
Proposition — Les diviseurs communs sont les diviseurs du PGCD
Pour tout \(a, b \in \mathbb{Z}\) non tous deux nuls, $$ \textcolor{colorprop}{\operatorname{div}(a) \cap \operatorname{div}(b) = \operatorname{div}(a \wedge b).} $$ De manière équivalente : un entier non nul divise à la fois \(a\) et \(b\) si et seulement s'il divise \(a \wedge b\). En conséquence, \(a \wedge b\) est aussi le plus grand diviseur commun au sens de la divisibilité \(\mid\) : tout diviseur commun de \(a\) et \(b\) divise \(a \wedge b\).
Posons \(d = a \wedge b\). On montre \(\operatorname{div}(a) \cap \operatorname{div}(b) = \operatorname{div}(d)\) par double inclusion.
- \((\supset)\) Comme \(d = a \wedge b\) divise à la fois \(a\) et \(b\) (par définition), tout diviseur de \(d\) divise aussi \(a\) et \(b\) par transitivité, donc appartient à \(\operatorname{div}(a) \cap \operatorname{div}(b)\).
- \((\subset)\) Soit \(\delta \in \operatorname{div}(a) \cap \operatorname{div}(b)\). Par l'identité de Bézout, \(d = a u + b v\) pour certains \(u, v \in \mathbb{Z}\). Comme \(\delta \mid a\) et \(\delta \mid b\), la propriété des combinaisons linéaires donne \(\delta \mid (a u + b v) = d\), donc \(\delta \in \operatorname{div}(d)\).
Compétences à pratiquer
- Diviseurs communs et PGCD
II.5
Généralisation à plusieurs entiers
Le PGCD se généralise à toute famille finie d'entiers — non tous nuls — par associativité, et l'identité de Bézout suit par une courte récurrence.
Définition — PGCD de \(k\) entiers
Soient \(k \geq 2\) et \(a_1, \dots, a_k \in \mathbb{Z}\) non tous nuls. Le plus grand commun diviseur de \(a_1, \dots, a_k\), noté \(a_1 \wedge \dots \wedge a_k\), est le plus grand entier strictement positif divisant tous les \(a_i\) (existence : l'ensemble des diviseurs communs positifs est non vide car il contient \(1\), et fini comme dans le cas à deux entiers). Proposition — Calcul récursif du PGCD
De manière équivalente, le PGCD de \(k\) entiers se calcule récursivement par $$ \textcolor{colorprop}{a_1 \wedge \dots \wedge a_k = (a_1 \wedge \dots \wedge a_{k-1}) \wedge a_k.} $$
Les deux membres valent le plus grand diviseur commun positif de \(a_1, \dots, a_k\). Pour le membre de droite : par la Proposition « Les diviseurs communs sont les diviseurs du PGCD » plus haut, les diviseurs de \((a_1 \wedge \dots \wedge a_{k-1}) \wedge a_k\) sont exactement les diviseurs communs de \(a_1 \wedge \dots \wedge a_{k-1}\) et de \(a_k\), qui par la même proposition sont les diviseurs communs de \(a_1, \dots, a_{k-1}, a_k\).
Proposition — Identité de Bézout pour \(k\) entiers
Pour \(a_1, \dots, a_k \in \mathbb{Z}\) non tous nuls, il existe \(u_1, \dots, u_k \in \mathbb{Z}\) tels que $$ \textcolor{colorprop}{a_1 \wedge \dots \wedge a_k = a_1 u_1 + a_2 u_2 + \dots + a_k u_k.} $$
Par récurrence sur \(k \geq 2\).
- Initialisation \(k = 2\). Déjà fait (Bézout pour deux entiers).
- Hérédité. Supposons le résultat pour \(k - 1\) entiers. Deux cas.
- Si \(a_1 = \dots = a_{k-1} = 0\), alors \(a_1 \wedge \dots \wedge a_k = a_k \wedge 0 = |a_k|\), et l'identité de Bézout \(|a_k| = a_k \cdot \mathrm{sgn}(a_k)\) (avec tous les autres \(u_i = 0\)) est immédiate.
- Sinon, posons \(d' = a_1 \wedge \dots \wedge a_{k-1}\) (bien défini car la famille n'est pas toute nulle) et \(d = d' \wedge a_k = a_1 \wedge \dots \wedge a_k\). Par Bézout à deux entiers, \(d = d' \alpha + a_k \beta\) pour certains \(\alpha, \beta \in \mathbb{Z}\). Par hypothèse de récurrence, \(d' = a_1 u'_1 + \dots + a_{k-1} u'_{k-1}\). En substituant, $$ d = \alpha (a_1 u'_1 + \dots + a_{k-1} u'_{k-1}) + a_k \beta = a_1 (\alpha u'_1) + \dots + a_{k-1} (\alpha u'_{k-1}) + a_k \beta. $$ Poser \(u_i = \alpha u'_i\) pour \(i \leq k-1\) et \(u_k = \beta\).
Proposition — Factorisation d'un PGCD
Pour \(a_1, \dots, a_r \in \mathbb{Z}\) non tous nuls (avec \(r \geq 2\)) et \(\lambda \in \mathbb{Z}^*\), $$ \textcolor{colorprop}{(\lambda a_1) \wedge \dots \wedge (\lambda a_r) = |\lambda| \cdot (a_1 \wedge \dots \wedge a_r).} $$
Posons \(d = a_1 \wedge \dots \wedge a_r\). On montre que \(|\lambda| d\) est un diviseur commun de \(\lambda a_1, \dots, \lambda a_r\), et réciproquement que tout diviseur commun de \(\lambda a_1, \dots, \lambda a_r\) divise \(|\lambda| d\).
- \(|\lambda| d\) divise chaque \(\lambda a_i\) : de \(d \mid a_i\), on obtient \(|\lambda| d \mid |\lambda| a_i\), et \(|\lambda| a_i = \pm \lambda a_i\), donc \(|\lambda| d \mid \lambda a_i\).
- Soit \(\delta\) un diviseur commun de \(\lambda a_1, \dots, \lambda a_r\). Par Bézout pour \(r\) entiers, \(d = a_1 u_1 + \dots + a_r u_r\) pour certains \(u_i \in \mathbb{Z}\). On multiplie par \(\lambda\) : \(\lambda d = (\lambda a_1) u_1 + \dots + (\lambda a_r) u_r\), donc \(\delta \mid \lambda d\), donc \(\delta \mid |\lambda| d\).
Compétences à pratiquer
- Généralisation à plusieurs entiers
II.6
Plus petit commun multiple (PPCM)
Le PPCM \(a \vee b\) est la notion duale du PGCD : plus petit multiple commun au lieu de plus grand diviseur commun. Les deux mêmes caractérisations s'appliquent — plus petit au sens de \(\leq\) sur \(\mathbb{N}^*\) et plus petit au sens de \(\mid\) —, et la relation PGCD-PPCM \((a \wedge b)(a \vee b) = |ab|\) relie les deux. On énonce cette dernière formule ici mais on en repousse la démonstration la plus propre à la section sur la valuation \(p\)-adique plus bas.
Définition — Plus petit commun multiple (PPCM)
Soient \(a, b \in \mathbb{N}^*\). Le plus petit commun multiple de \(a\) et \(b\), noté \(a \vee b\), est le plus petit élément de \(\{m \in \mathbb{N}^* : a \mid m \text{ et } b \mid m\}\) pour l'ordre naturel \(\leq\) sur \(\mathbb{N}^*\). L'ensemble est non vide (il contient \(a b\)).Convention avec zéro. Comme \(0 \mathbb{Z} = \{0\}\), le seul multiple commun de \(0\) et de tout entier est \(0\). On pose donc \(0 \vee b := 0\) pour tout \(b \in \mathbb{N}\).
Extension à \(\mathbb{Z}\). Pour \(a, b \in \mathbb{Z}\), \(a \vee b := |a| \vee |b|\).
Proposition — Les multiples communs sont les multiples du PPCM
Pour tout \(a, b \in \mathbb{N}^*\), $$ \textcolor{colorprop}{a \mathbb{Z} \cap b \mathbb{Z} = (a \vee b) \mathbb{Z}.} $$ De manière équivalente : \(a \mid n\) et \(b \mid n \iff (a \vee b) \mid n\). Donc \(a \vee b\) est aussi le plus petit multiple commun au sens de la divisibilité \(\mid\).Pour \(a, b \in \mathbb{Z}^*\), le même énoncé est valable avec la convention \(a \vee b := |a| \vee |b|\) (puisque \(a \mathbb{Z} = |a| \mathbb{Z}\)).
Posons \(m = a \vee b\).
- \((\supset)\) \(m\) est un multiple commun de \(a\) et \(b\) par définition, donc tout multiple de \(m\) est aussi un multiple commun.
- \((\subset)\) Soit \(n\) un multiple commun de \(a\) et \(b\). Appliquer la division euclidienne de \(n\) par \(m\) : \(n = m q + r\) avec \(0 \leq r < m\). Alors \(r = n - m q\) est combinaison \(\mathbb{Z}\)-linéaire de deux multiples communs de \(a\) et \(b\), donc est un multiple commun de \(a\) et \(b\). Comme \(0 \leq r < m\) et que \(m\) est le plus petit multiple commun strictement positif, \(r\) ne peut être dans \(\mathbb{N}^*\) ; donc \(r = 0\). Donc \(n = m q \in m \mathbb{Z}\).
Proposition — Relation PGCD-PPCM
Pour tout \(a, b \in \mathbb{Z}\), $$ \textcolor{colorprop}{(a \wedge b)(a \vee b) = |a b|.} $$
Cas trivial. Si \(a = 0\) ou \(b = 0\), alors \(a \vee b = 0\) et \(|ab| = 0\), donc la formule s'écrit \(0 = 0\). On suppose désormais \(a, b \neq 0\).
La démonstration la plus propre utilise la décomposition en facteurs premiers. Le résultat suit de l'identité \(\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta\) pour \(\alpha, \beta \in \mathbb{N}\), sommée sur tous les premiers \(p\) via la valuation \(p\)-adique. Démonstration reportée au Théorème « Divisibilité, PGCD, PPCM via valuations » plus bas.
La démonstration la plus propre utilise la décomposition en facteurs premiers. Le résultat suit de l'identité \(\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta\) pour \(\alpha, \beta \in \mathbb{N}\), sommée sur tous les premiers \(p\) via la valuation \(p\)-adique. Démonstration reportée au Théorème « Divisibilité, PGCD, PPCM via valuations » plus bas.
Exemple
\(12 \vee 18 = 36\), et \(12 \cdot 18 = 216 = 6 \cdot 36 = (12 \wedge 18)(12 \vee 18)\). Compétences à pratiquer
- Calculer un PPCM et utiliser la relation PGCD-PPCM
III
Entiers premiers entre eux
Deux entiers sont premiers entre eux quand leur PGCD vaut \(1\), c'est-à-dire que leurs seuls diviseurs communs sont \(\pm 1\). L'identité de Bézout, appliquée à ce cas particulier, devient le célèbre théorème de Bézout — une caractérisation de la coprimitude par une équation linéaire explicite. De là, le lemme de Gauss suit en deux lignes et débloque tous les raisonnements de divisibilité de la suite du chapitre. Les deux notions « premiers entre eux dans leur ensemble » (PGCD = 1) et « premiers entre eux deux à deux » doivent être soigneusement distinguées : « deux à deux » implique « dans leur ensemble », mais la réciproque est fausse (exemple : \(6, 10, 15\)).
III.1
Théorème de Bézout
La condition définissante des entiers premiers entre eux est \(a \wedge b = 1\). Le théorème de Bézout convertit cette définition en outil pratique : \(a\) et \(b\) sont premiers entre eux ssi on peut trouver \(u, v \in \mathbb{Z}\) avec \(a u + b v = 1\). Le sens direct suit immédiatement de l'identité de Bézout démontrée à la section précédente ; le sens réciproque est une application en une ligne de la propriété des combinaisons linéaires.
Définition — Entiers premiers entre eux
Deux entiers \(a, b \in \mathbb{Z}\) sont premiers entre eux si leurs seuls diviseurs communs sont \(\pm 1\), ce qui équivaut à \(a \wedge b = 1\). Théorème — Théorème de Bézout
Pour tout \(a, b \in \mathbb{Z}\), $$ \textcolor{colorprop}{a \wedge b = 1 \iff \exists u, v \in \mathbb{Z}, \; a u + b v = 1.} $$ - \((\Rightarrow)\) Si \(a \wedge b = 1\), l'identité de Bézout (Théorème « Identité de Bézout » plus haut) donne \(u, v \in \mathbb{Z}\) avec \(a u + b v = a \wedge b = 1\).
- \((\Leftarrow)\) Supposons \(a u + b v = 1\) pour certains \(u, v \in \mathbb{Z}\). Soit \(\delta\) un diviseur commun de \(a\) et \(b\). Par la propriété des combinaisons linéaires, \(\delta \mid (a u + b v) = 1\), donc \(\delta \in \{\pm 1\}\). Donc les seuls diviseurs communs sont \(\pm 1\), donc \(a \wedge b = 1\).
Exemple
\(7 \wedge 5 = 1\) car \(3 \cdot 7 - 4 \cdot 5 = 21 - 20 = 1\). (De manière équivalente, le seul diviseur commun positif de \(7\) et \(5\) est \(1\), car \(7\) est premier et \(5\) est premier.) Méthode — Se ramener à la forme première
Soient \(a, b \in \mathbb{Z}\) non tous deux nuls, et \(d = a \wedge b\). Les entiers $$ a' = \frac{a}{d}, \qquad b' = \frac{b}{d} $$ sont premiers entre eux : \(a' \wedge b' = 1\). C'est la forme irréductible d'un rationnel : tout rationnel \(p/q\) (\(p \in \mathbb{Z}\), \(q \in \mathbb{N}^*\)) s'écrit de manière unique \(p'/q'\) avec \(p' \wedge q' = 1\) et \(q' > 0\) (unicité via le lemme de Gauss ci-dessous). Compétences à pratiquer
- Reconnaître des entiers premiers entre eux et utiliser Bézout
III.2
Lemme de Gauss
Le lemme de Gauss est le second moteur de l'arithmétique. Il dit : si \(a\) divise un produit \(b c\) et que \(a\) n'a rien en commun avec \(b\), alors \(a\) divise nécessairement \(c\). La démonstration utilise le théorème de Bézout pour multiplier et isoler \(c\).
Théorème — Lemme de Gauss
Soient \(a, b, c \in \mathbb{Z}\) avec \(a \neq 0\). Si $$ \textcolor{colorprop}{a \mid b c \quad \text{et} \quad a \wedge b = 1, \quad \text{alors} \quad a \mid c.} $$
Par le théorème de Bézout, \(a u + b v = 1\) pour certains \(u, v \in \mathbb{Z}\). On multiplie par \(c\) : $$ a u c + b v c = c. $$ Les deux termes de gauche sont multiples de \(a\) : \(a u c \in a \mathbb{Z}\) trivialement, et \(b v c = (b c) v \in a \mathbb{Z}\) car \(a \mid b c\). Leur somme est donc multiple de \(a\), donc \(a \mid c\).
Proposition — Conséquences du lemme de Gauss
- Diviseurs premiers entre eux. Soient \(a, b \in \mathbb{Z}^*\) et \(n \in \mathbb{Z}\). Si \(a \wedge b = 1\), \(a \mid n\) et \(b \mid n\), alors \(a b \mid n\).
- Premier à un produit. Soient \(a, b, n \in \mathbb{Z}^*\). Si \(a \wedge n = 1\) et \(b \wedge n = 1\), alors \((a b) \wedge n = 1\).
- Diviseurs premiers entre eux. De \(a \mid n\), écrire \(n = a k\) pour un certain \(k \in \mathbb{Z}\). Alors \(b \mid a k\). Comme \(a \wedge b = 1\), le lemme de Gauss donne \(b \mid k\), soit \(k = b k'\), donc \(n = a b k'\), donc \(a b \mid n\).
- Premier à un produit. De \(a \wedge n = 1\), prendre \(a u + n v = 1\). De \(b \wedge n = 1\), prendre \(b u' + n v' = 1\). On multiplie : $$ 1 = (a u + n v)(b u' + n v') = a b (u u') + n (a u v' + b v u' + n v v'). $$ C'est une identité de Bézout pour \(a b\) et \(n\), donc par le théorème de Bézout \((a b) \wedge n = 1\).
Exemple — Contre-exemple sans hypothèse de coprimitude
\(6 \mid 12\) et \(4 \mid 12\), mais \(6 \cdot 4 = 24\) ne divise pas \(12\). L'hypothèse \(a \wedge b = 1\) dans « diviseurs premiers entre eux » est essentielle. Ici \(6 \wedge 4 = 2 \neq 1\). Compétences à pratiquer
- Appliquer le lemme de Gauss
III.3
Premiers entre eux dans leur ensemble vs deux à deux
Pour des familles de \(\geq 3\) entiers, deux notions distinctes de « premiers entre eux » coexistent ; elles ne doivent pas être confondues.
Définition — Premiers entre eux dans leur ensemble, premiers entre eux deux à deux
Soient \(k \geq 2\) et \(a_1, \dots, a_k \in \mathbb{Z}\) non tous nuls. - Les entiers \(a_1, \dots, a_k\) sont premiers entre eux dans leur ensemble si \(a_1 \wedge \dots \wedge a_k = 1\).
- Les entiers \(a_1, \dots, a_k\) sont premiers entre eux deux à deux si pour tout \(i \neq j\), \(a_i \wedge a_j = 1\).
Proposition — Deux à deux \(\Rightarrow\) dans leur ensemble
Premiers entre eux deux à deux \(\Rightarrow\) premiers entre eux dans leur ensemble. La réciproque est fausse en général.
Sens direct. Supposer premiers entre eux deux à deux. Tout diviseur commun \(\delta\) de tous les \(a_i\) est en particulier diviseur commun de \(a_1\) et \(a_2\), donc \(\delta \mid (a_1 \wedge a_2) = 1\), donc \(\delta = \pm 1\). Donc le PGCD de tous les \(a_i\) vaut \(1\).
Contre-exemple à la réciproque. Prendre \(a_1 = 6\), \(a_2 = 10\), \(a_3 = 15\). Alors \(a_1 \wedge a_2 \wedge a_3 = (6 \wedge 10) \wedge 15 = 2 \wedge 15 = 1\), donc ils sont premiers entre eux dans leur ensemble. Mais \(6 \wedge 10 = 2 \neq 1\), \(6 \wedge 15 = 3 \neq 1\), et \(10 \wedge 15 = 5 \neq 1\) — aucune paire n'est première.
Contre-exemple à la réciproque. Prendre \(a_1 = 6\), \(a_2 = 10\), \(a_3 = 15\). Alors \(a_1 \wedge a_2 \wedge a_3 = (6 \wedge 10) \wedge 15 = 2 \wedge 15 = 1\), donc ils sont premiers entre eux dans leur ensemble. Mais \(6 \wedge 10 = 2 \neq 1\), \(6 \wedge 15 = 3 \neq 1\), et \(10 \wedge 15 = 5 \neq 1\) — aucune paire n'est première.
Compétences à pratiquer
- Distinguer dans leur ensemble et deux à deux
IV
Nombres premiers
Les nombres premiers sont les atomes multiplicatifs de \(\mathbb{N}^*\) : tout \(n \geq 2\) se construit à partir des nombres premiers par multiplication, et les briques sont uniques à l'ordre près. On commence par la définition et la preuve classique d'infinitude d'Euclide, on présente le crible d'Ératosthène, puis on utilise Bézout/Gauss pour démontrer le lemme d'Euclide (\(p \mid ab \Rightarrow p \mid a\) ou \(p \mid b\)), l'additivité de la valuation \(p\)-adique, et l'existence et l'unicité de la décomposition en facteurs premiers. La section se clôt par des expressions closes de \(a \mid b\), \(a \wedge b\) et \(a \vee b\) en termes de valuations.
IV.1
Nombres premiers, infinitude, crible
Un nombre premier est un entier \(p \geq 2\) dont les seuls diviseurs sont \(\pm 1\) et \(\pm p\). L'ensemble des nombres premiers, noté \(\mathbb{P}\), est infini (Euclide). Le crible d'Ératosthène est l'algorithme classique pour lister les nombres premiers jusqu'à un seuil \(N\) donné, en utilisant le fait que tout composé \(n \leq N\) admet un diviseur premier \(\leq \sqrt{N}\).
Définition — Nombre premier, nombre composé
Un entier naturel \(p \geq 2\) est dit premier si ses seuls diviseurs dans \(\mathbb{N}^*\) sont \(1\) et \(p\) (de manière équivalente, \(\operatorname{div}(p) = \{\pm 1, \pm p\}\)). On note \(\mathbb{P}\) l'ensemble des nombres premiers.Un entier naturel \(n \geq 2\) qui n'est pas premier est dit composé : il admet un diviseur \(d\) avec \(1 < d < n\).
L'entier \(1\) n'est, par convention, ni premier ni composé.
Exemple
Les premiers nombres premiers sont \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \dots\). L'entier \(4 = 2 \cdot 2\) est composé. L'entier \(1\) n'est ni premier ni composé. (L'exclusion de \(1\) des nombres premiers est nécessaire pour garder l'unicité de la décomposition en facteurs premiers : sinon \(6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3\), etc.) Proposition — Existence d'un diviseur premier
Tout entier \(n \geq 2\) admet au moins un diviseur premier.
L'ensemble \(D = \{d \in \mathbb{N} : d \geq 2 \text{ et } d \mid n\}\) est non vide (il contient \(n\)) et minoré par \(2\), donc admet un plus petit élément \(p_0 \in D\).
Affirmation : \(p_0\) est premier. Si \(p_0\) était composé, il aurait un diviseur \(d\) avec \(1 < d < p_0\). Alors \(d\) divise aussi \(n\) (transitivité), donc \(d \in D\) avec \(d < p_0\) — ce qui contredit la minimalité de \(p_0\).
Donc \(p_0\) est premier, et \(p_0 \mid n\).
Affirmation : \(p_0\) est premier. Si \(p_0\) était composé, il aurait un diviseur \(d\) avec \(1 < d < p_0\). Alors \(d\) divise aussi \(n\) (transitivité), donc \(d \in D\) avec \(d < p_0\) — ce qui contredit la minimalité de \(p_0\).
Donc \(p_0\) est premier, et \(p_0 \mid n\).
Théorème — Infinitude des nombres premiers
L'ensemble \(\mathbb{P}\) des nombres premiers est infini.
Démonstration classique d'Euclide, par l'absurde. Supposons par l'absurde que \(\mathbb{P}\) soit fini, disons \(\mathbb{P} = \{p_1, p_2, \dots, p_r\}\). On considère l'entier $$ N = p_1 \, p_2 \cdots p_r + 1. $$ Comme \(N \geq 2\), par la proposition précédente \(N\) admet un diviseur premier, disons \(p_k\) pour un certain \(k \in \{1, \dots, r\}\). Alors \(p_k\) divise à la fois \(N\) et \(p_1 \cdots p_r\), donc \(p_k\) divise leur différence \(N - p_1 \cdots p_r = 1\). Mais un nombre premier est \(\geq 2\), donc ne peut pas diviser \(1\) — contradiction. Donc \(\mathbb{P}\) est infini.
Méthode — Crible d'Ératosthène
Pour lister tous les nombres premiers \(\leq N\) (pour un \(N \geq 2\) donné) :Étape 1. Écrire les entiers \(2, 3, 4, \dots, N\) dans un tableau.
Étape 2. Prendre le plus petit entier non rayé \(p\). Alors \(p\) est premier ; rayer tous ses multiples propres \(2p, 3p, 4p, \dots \leq N\).
Étape 3. Répéter l'étape 2 jusqu'à \(p > \sqrt{N}\). À ce moment-là, tout entier \(\leq N\) non rayé est premier.
Pourquoi \(\sqrt{N}\) suffit. Si \(n \leq N\) est composé, on écrit \(n = a b\) avec \(a \leq b\). Alors \(a \leq \sqrt{n} \leq \sqrt{N}\), donc \(n\) est rayé par un premier \(\leq a \leq \sqrt{N}\).
Exemple — Premiers \(\leq 30\) par le crible
\(\sqrt{30} < 6\), donc les nombres premiers servant à rayer sont \(2, 3, 5\). - Rayer les multiples de \(2\) : \(4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30\).
- Rayer les multiples de \(3\) (encore présents) : \(9, 15, 21, 27\).
- Rayer les multiples de \(5\) (encore présents) : \(25\).
Compétences à pratiquer
- Lister les nombres premiers par le crible
IV.2
Lemme d'Euclide, décomposition en facteurs premiers
Le pont entre les nombres premiers et le reste du chapitre est le lemme d'Euclide : \(p \mid a b \Rightarrow p \mid a\) ou \(p \mid b\), valable uniquement lorsque \(p\) est premier. De là suivent l'additivité de la valuation \(p\)-adique, puis l'unicité de la décomposition en facteurs premiers (l'existence se fait par récurrence forte).
Proposition — Divisibilité par un premier et coprimitude
Soient \(p\) un nombre premier et \(a \in \mathbb{Z}\). Alors $$ \textcolor{colorprop}{p \nmid a \iff a \wedge p = 1.} $$
Les diviseurs de \(p\) dans \(\mathbb{N}^*\) sont seulement \(1\) et \(p\). Donc \(a \wedge p \in \{1, p\}\).
- Si \(p \mid a\), alors \(p \in \operatorname{div}(a) \cap \operatorname{div}(p)\), donc \(a \wedge p = p\).
- Si \(p \nmid a\), alors \(p \notin \operatorname{div}(a) \cap \operatorname{div}(p)\), donc \(a \wedge p = 1\).
Proposition — Lemme d'Euclide
Soient \(p\) un nombre premier et \(a, b \in \mathbb{Z}\). Alors $$ \textcolor{colorprop}{p \mid a b \iff p \mid a \text{ ou } p \mid b.} $$ En particulier, pour tout \(n \in \mathbb{N}^*\), \(p \mid a^n \iff p \mid a\).
\((\Leftarrow)\) Immédiat par la propriété de divisibilité des produits.
\((\Rightarrow)\) Supposer \(p \mid a b\). Si \(p \mid a\), c'est fait. Sinon \(p \nmid a\), donc par la proposition précédente \(a \wedge p = 1\). Appliquer le lemme de Gauss à \(p \mid a b\) avec \(p \wedge a = 1\) : \(p \mid b\).
\((\Rightarrow)\) Supposer \(p \mid a b\). Si \(p \mid a\), c'est fait. Sinon \(p \nmid a\), donc par la proposition précédente \(a \wedge p = 1\). Appliquer le lemme de Gauss à \(p \mid a b\) avec \(p \wedge a = 1\) : \(p \mid b\).
Théorème — Existence de la décomposition en facteurs premiers
Tout entier \(n \in \mathbb{N}^*\) s'écrit comme produit (éventuellement vide) de nombres premiers : $$ \textcolor{colorprop}{n = p_1 \, p_2 \cdots p_s \quad \text{avec } p_1, \dots, p_s \in \mathbb{P} \text{ (et } s = 0 \text{ pour } n = 1).} $$
Par récurrence forte sur \(n \geq 1\).
- Initialisation \(n = 1\). Le produit vide (avec \(s = 0\)) donne \(1\), donc l'énoncé est vrai.
- Hérédité. Soit \(n \geq 2\), et on suppose l'énoncé vrai pour tout entier \(1 \leq k < n\). Deux cas :
- Si \(n\) est premier, on écrit \(n = n\) (produit à un terme), et c'est fait.
- Si \(n\) est composé, on écrit \(n = a b\) avec \(1 < a, b < n\) (par définition de composé). Par l'hypothèse de récurrence, \(a = q_1 \cdots q_s\) et \(b = q'_1 \cdots q'_t\) sont des produits de nombres premiers. En concaténant, \(n = q_1 \cdots q_s \, q'_1 \cdots q'_t\) est un produit de nombres premiers.
Compétences à pratiquer
- Démontrer des énoncés avec les nombres premiers (lemme d'Euclide)
IV.3
Valuation \(p\)-adique et unicité de la décomposition
La valuation \(p\)-adique \(v_p(n)\) compte combien de fois le nombre premier \(p\) apparaît dans la décomposition de \(n\). Une fois démontrée son additivité (\(v_p(a b) = v_p(a) + v_p(b)\), conséquence facile du lemme d'Euclide), l'unicité de la décomposition en facteurs premiers tombe en deux lignes : les exposants \(\alpha_p\) dans toute décomposition doivent valoir \(v_p(n)\).
Définition — Valuation \(p\)-adique
Soient \(p\) un nombre premier et \(n \in \mathbb{Z}^*\). La valuation \(p\)-adique de \(n\), notée \(v_p(n)\), est le plus grand entier \(k \in \mathbb{N}\) tel que \(p^k \mid n\) : $$ v_p(n) = \max \{ k \in \mathbb{N} : p^k \mid n \}. $$ L'ensemble \(\{k \in \mathbb{N} : p^k \mid n\}\) est non vide (contient \(0\)) et majoré (par \(\log_p |n|\)), donc le max existe.Convention avec zéro. \(v_p(0) = +\infty\) (car \(p^k \mid 0\) pour tout \(k\)).
Remarque. \(v_p(n) = v_p(|n|)\) car \(p^k \mid n \iff p^k \mid -n\).
Exemple
\(60 = 2^2 \cdot 3 \cdot 5\), donc \(v_2(60) = 2\), \(v_3(60) = 1\), \(v_5(60) = 1\), et \(v_p(60) = 0\) pour tout premier \(p \notin \{2, 3, 5\}\). Exemple
Calculer \(v_2(72)\) et \(v_3(72)\). Comme \(72 = 2^3 \cdot 3^2\), \(v_2(72) = 3\) et \(v_3(72) = 2\). Pour un premier \(p \notin \{2, 3\}\), \(v_p(72) = 0\). Proposition — Additivité de \(v_p\)
Pour tout nombre premier \(p\) et tout \(a, b \in \mathbb{Z}^*\), $$ \textcolor{colorprop}{v_p(a b) = v_p(a) + v_p(b).} $$
Posons \(\alpha = v_p(a)\) et \(\beta = v_p(b)\). Par définition, \(a = p^{\alpha} a'\) avec \(p \nmid a'\), et \(b = p^{\beta} b'\) avec \(p \nmid b'\). Alors $$ a b = p^{\alpha + \beta} (a' b'). $$ Par le lemme d'Euclide (contraposée), \(p \nmid a'\) et \(p \nmid b'\) entraînent \(p \nmid a' b'\). Donc la plus grande puissance de \(p\) divisant \(a b\) est exactement \(p^{\alpha + \beta}\), soit \(v_p(a b) = \alpha + \beta = v_p(a) + v_p(b)\).
Théorème — Unicité de la décomposition en facteurs premiers
Tout entier \(n \in \mathbb{N}^*\) s'écrit de manière unique $$ \textcolor{colorprop}{n = \prod_{p \in \mathbb{P}} p^{v_p(n)},} $$ où le produit est fini (seuls un nombre fini des exposants \(v_p(n)\) sont non nuls, à savoir ceux des \(p\) avec \(p \mid n\)). De manière équivalente : si \(n = \prod_p p^{\alpha_p}\) pour une certaine famille \((\alpha_p)_{p \in \mathbb{P}}\) d'entiers naturels à support fini, alors \(\alpha_p = v_p(n)\) pour tout nombre premier \(p\).
Existence. Par le théorème d'existence ci-dessus, \(n = q_1 q_2 \cdots q_s\) est un produit de nombres premiers. Regrouper les premiers égaux : \(n = \prod_p p^{\alpha_p}\) avec \(\alpha_p = \) nombre d'indices \(i\) tels que \(q_i = p\). La famille \((\alpha_p)_{p \in \mathbb{P}}\) est à support fini.
Unicité. Supposons \(n = \prod_p p^{\alpha_p} = \prod_p p^{\beta_p}\) pour deux telles familles. Appliquer \(v_q\) (pour un premier \(q\) quelconque) aux deux membres ; par additivité de \(v_q\), $$ v_q(n) = \sum_p \alpha_p \, v_q(p) = \alpha_q, $$ puisque \(v_q(p) = 1\) si \(p = q\) et \(0\) sinon. Donc \(\alpha_q = v_q(n)\) pour tout premier \(q\), et de même \(\beta_q = v_q(n)\). Donc \(\alpha_q = \beta_q\) pour tout \(q\), soit l'unicité.
Unicité. Supposons \(n = \prod_p p^{\alpha_p} = \prod_p p^{\beta_p}\) pour deux telles familles. Appliquer \(v_q\) (pour un premier \(q\) quelconque) aux deux membres ; par additivité de \(v_q\), $$ v_q(n) = \sum_p \alpha_p \, v_q(p) = \alpha_q, $$ puisque \(v_q(p) = 1\) si \(p = q\) et \(0\) sinon. Donc \(\alpha_q = v_q(n)\) pour tout premier \(q\), et de même \(\beta_q = v_q(n)\). Donc \(\alpha_q = \beta_q\) pour tout \(q\), soit l'unicité.
Compétences à pratiquer
- Calculer décomposition en facteurs premiers et valuations
IV.4
Divisibilité, PGCD, PPCM via les valuations
La valuation \(p\)-adique donne une expression close propre de la divisibilité, du PGCD et du PPCM : \(a\) divise \(b\) ssi tout \(v_p(a) \leq v_p(b)\) ; \(a \wedge b\) a pour exposant \(\min(v_p(a), v_p(b))\) ; \(a \vee b\) a pour exposant \(\max(v_p(a), v_p(b))\). La relation \((a \wedge b)(a \vee b) = |a b|\) tombe immédiatement de \(\min + \max = \alpha + \beta\), complétant la démonstration reportée depuis la section sur le plus petit commun multiple plus haut.
Théorème — Divisibilité, PGCD, PPCM via valuations
Pour tout \(a, b \in \mathbb{Z}^*\), - Divisibilité. \(a \mid b \iff \forall p \in \mathbb{P}, \; v_p(a) \leq v_p(b)\).
- PGCD via valuations. \(a \wedge b = \prod_{p \in \mathbb{P}} p^{\min(v_p(a), v_p(b))}\).
- PPCM via valuations. \(a \vee b = \prod_{p \in \mathbb{P}} p^{\max(v_p(a), v_p(b))}\).
- Relation PGCD-PPCM. \((a \wedge b)(a \vee b) = |a b|\).
Divisibilité. Si \(a \mid b\), alors \(b = a k\) pour un certain \(k \in \mathbb{Z}^*\), donc \(v_p(b) = v_p(a) + v_p(k) \geq v_p(a)\) par additivité. Réciproquement, supposer \(v_p(a) \leq v_p(b)\) pour tout premier \(p\). On écrit $$ |a| = \prod_p p^{\alpha_p}, \qquad |b| = \prod_p p^{\beta_p}, $$ avec \(\alpha_p \leq \beta_p\) pour tout \(p\) par hypothèse. Alors $$ |b| = |a| \cdot \prod_p p^{\beta_p - \alpha_p}, $$ où le produit de droite est un entier de \(\mathbb{N}^*\). Donc \(|a| \mid |b|\), donc \(a \mid b\).
PGCD via valuations. Posons \(d = \prod_p p^{\min(v_p(a), v_p(b))}\).
PPCM via valuations. Argument symétrique avec \(\max\) à la place de \(\min\).
Relation PGCD-PPCM. Pour tout premier \(p\), \(\min(v_p(a), v_p(b)) + \max(v_p(a), v_p(b)) = v_p(a) + v_p(b)\). En multipliant \(a \wedge b\) et \(a \vee b\) puis en prenant \(v_p\) : $$ v_p((a \wedge b)(a \vee b)) = v_p(a) + v_p(b) = v_p(a b) = v_p(|a b|). $$ Les deux membres sont des entiers positifs de mêmes valuations en tout premier, donc par unicité de la décomposition \((a \wedge b)(a \vee b) = |a b|\).
PGCD via valuations. Posons \(d = \prod_p p^{\min(v_p(a), v_p(b))}\).
- \(d \mid a\) : \(v_p(d) = \min(v_p(a), v_p(b)) \leq v_p(a)\) pour tout \(p\), donc \(d \mid a\) par la caractérisation de la divisibilité. De même \(d \mid b\).
- \(d\) est le plus grand : supposer \(\delta \mid a\) et \(\delta \mid b\). Alors \(v_p(\delta) \leq v_p(a)\) et \(v_p(\delta) \leq v_p(b)\) pour tout \(p\), donc \(v_p(\delta) \leq \min(v_p(a), v_p(b)) = v_p(d)\). Donc \(\delta \mid d\), donc \(|\delta| \leq d\).
PPCM via valuations. Argument symétrique avec \(\max\) à la place de \(\min\).
Relation PGCD-PPCM. Pour tout premier \(p\), \(\min(v_p(a), v_p(b)) + \max(v_p(a), v_p(b)) = v_p(a) + v_p(b)\). En multipliant \(a \wedge b\) et \(a \vee b\) puis en prenant \(v_p\) : $$ v_p((a \wedge b)(a \vee b)) = v_p(a) + v_p(b) = v_p(a b) = v_p(|a b|). $$ Les deux membres sont des entiers positifs de mêmes valuations en tout premier, donc par unicité de la décomposition \((a \wedge b)(a \vee b) = |a b|\).
Exemple
Calculer \(600 \wedge 740\) via les valuations. \(600 = 2^3 \cdot 3 \cdot 5^2\) et \(740 = 2^2 \cdot 5 \cdot 37\). Prendre le min des exposants premier par premier : $$ 600 \wedge 740 = 2^{\min(3, 2)} \cdot 3^{\min(1, 0)} \cdot 5^{\min(2, 1)} \cdot 37^{\min(0, 1)} = 2^2 \cdot 5 = 20. $$ Pour le PPCM, prendre le max : \(600 \vee 740 = 2^3 \cdot 3 \cdot 5^2 \cdot 37 = 22\,200\). Vérification : \(20 \cdot 22200 = 444\,000 = 600 \cdot 740\). \(\checkmark\) Méthode — Calculer PGCD / PPCM par décomposition en facteurs premiers
Étape 1. Décomposer \(a\) et \(b\) en facteurs premiers : \(a = \prod p^{\alpha_p}\), \(b = \prod p^{\beta_p}\) (utiliser le même ensemble de premiers en complétant par des exposants nuls).Étape 2. Pour le PGCD : prendre le min des exposants premier par premier, \(a \wedge b = \prod p^{\min(\alpha_p, \beta_p)}\).
Étape 3. Pour le PPCM : prendre le max, \(a \vee b = \prod p^{\max(\alpha_p, \beta_p)}\).
Comparaison avec l'algorithme d'Euclide. Pour les petits entiers (jusqu'à ~5 chiffres), la décomposition en facteurs premiers est plus rapide et plus propre. Pour les grands entiers, l'algorithme d'Euclide gagne (pas besoin de factoriser).
Compétences à pratiquer
- Calculer PGCD / PPCM via les valuations
V
Congruences
La congruence \(a \equiv b \pmod n\) n'est qu'une autre manière d'écrire \(n \mid (a - b)\). Elle empaquette la divisibilité dans une notation compatible avec les sommes et les produits, ce qui transforme l'ensemble du chapitre en un calcul « modulo \(n\) ». On commence par la définition et les opérations de base (rappel : la spécialité de Terminale couvre déjà cela, mais on le réénonce rigoureusement et on utilise désormais toute la machinerie de divisibilité, Bézout, Gauss et décomposition en facteurs premiers développée plus haut) ; on décrit \(\mathbb{Z}/n\mathbb{Z}\) comme l'ensemble des \(n\) classes de résidus (avec le rappel explicite que sa structure d'anneau est hors programme) ; on caractérise ensuite l'inversibilité modulo \(n\) via le théorème de Bézout ; et on conclut par le petit théorème de Fermat, le résultat modulaire central du chapitre.
V.1
Définition et opérations
La spécialité de Terminale donne déjà la définition \(a \equiv b \pmod n\) et la caractérisation « même reste ». On les réénonce rigoureusement et on démontre la compatibilité de \(\equiv\) avec la somme et le produit (programme : « Opérations sur les congruences : somme, produit »).
Définition — Congruence modulo \(n\)
Soit \(n \in \mathbb{N}^*\). Pour \(a, b \in \mathbb{Z}\), on dit que \(a\) est congru à \(b\) modulo \(n\), et on note $$ a \equiv b \pmod n \quad \text{ou simplement} \quad a \equiv b \; [n], $$ si \(n \mid (a - b)\), c'est-à-dire s'il existe \(k \in \mathbb{Z}\) tel que \(a - b = k n\).Pour \(n = 1\), tout couple d'entiers est congru (car \(1\) divise tout). Le cas intéressant est \(n \geq 2\), ce que l'on suppose tacitement par la suite.
Proposition — Relation d'équivalence
Pour tout \(n \in \mathbb{N}^*\), la relation binaire \(\equiv \pmod n\) sur \(\mathbb{Z}\) est une relation d'équivalence : réflexive, symétrique, transitive.
Déjà démontré dans le chapitre Relations binaires. En bref : \(a - a = 0 = n \cdot 0\) (réflexive) ; si \(n \mid (a - b)\) alors \(n \mid (b - a) = -(a - b)\) (symétrique) ; si \(n \mid (a - b)\) et \(n \mid (b - c)\), alors \(n \mid (a - c) = (a - b) + (b - c)\) par combinaison linéaire (transitive).
Proposition — Compatibilité avec somme et produit
Soit \(n \in \mathbb{N}^*\) et \(a, a', b, b' \in \mathbb{Z}\). Si \(a \equiv a' \pmod n\) et \(b \equiv b' \pmod n\), alors $$ \textcolor{colorprop}{a + b \equiv a' + b' \pmod n \quad \text{et} \quad a \, b \equiv a' \, b' \pmod n.} $$ En particulier, \(a^k \equiv (a')^k \pmod n\) pour tout \(k \in \mathbb{N}\).
On écrit \(a = a' + k n\) et \(b = b' + k' n\) pour certains \(k, k' \in \mathbb{Z}\).
Somme. \(a + b = (a' + b') + (k + k') n\), donc \(n \mid (a + b) - (a' + b')\), soit \(a + b \equiv a' + b' \pmod n\).
Produit. $$ a b = (a' + k n)(b' + k' n) = a' b' + (a' k' + b' k + k k' n) \, n, $$ donc \(n \mid (a b - a' b')\), soit \(a b \equiv a' b' \pmod n\).
Puissances. Appliquer la compatibilité produit itérativement (ou par récurrence sur \(k\)).
Somme. \(a + b = (a' + b') + (k + k') n\), donc \(n \mid (a + b) - (a' + b')\), soit \(a + b \equiv a' + b' \pmod n\).
Produit. $$ a b = (a' + k n)(b' + k' n) = a' b' + (a' k' + b' k + k k' n) \, n, $$ donc \(n \mid (a b - a' b')\), soit \(a b \equiv a' b' \pmod n\).
Puissances. Appliquer la compatibilité produit itérativement (ou par récurrence sur \(k\)).
Exemple — Critère de divisibilité par 9
\(10 \equiv 1 \pmod 9\), donc par compatibilité avec les puissances \(10^k \equiv 1^k = 1 \pmod 9\) pour tout \(k \in \mathbb{N}\). Donc pour \(n = a_k 10^k + \dots + a_1 \cdot 10 + a_0 \in \mathbb{N}\) (écriture décimale), $$ n \equiv a_k + a_{k-1} + \dots + a_1 + a_0 \pmod 9. $$ Conséquence : \(n\) est divisible par \(9\) ssi la somme de ses chiffres décimaux l'est. Par exemple \(n = 1234\) : \(1 + 2 + 3 + 4 = 10\), \(1 + 0 = 1\), donc \(1234 \equiv 1 \pmod 9\) et \(9 \nmid 1234\). Méthode — Réduire des puissances modulo \(n\)
Pour calculer \(a^N \pmod n\) pour \(N\) grand :Étape 1. Trouver une petite puissance de \(a\) congrue à \(1\) ou \(-1\) modulo \(n\), si une telle puissance apparaît rapidement (par exemple essayer \(a^2, a^3, a^4, \dots\) jusqu'à obtenir un petit reste).
Étape 2. Écrire \(N = k q + r\) avec \(0 \leq r < k\) (division euclidienne de l'exposant).
Étape 3. Alors \(a^N = (a^k)^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod n\), et \(a^r\) est petit.
Exemple. Calculer \(2^{1000} \pmod 7\). On trouve \(2^3 = 8 \equiv 1 \pmod 7\). Alors \(1000 = 3 \cdot 333 + 1\), donc \(2^{1000} = (2^3)^{333} \cdot 2 \equiv 1 \cdot 2 \equiv 2 \pmod 7\).
Compétences à pratiquer
- Réduire modulo \(n\)
V.2
Classes de résidus et \(\mathbb{Z}/n\mathbb{Z}\) comme ensemble
La division euclidienne par \(n\) partitionne \(\mathbb{Z}\) en \(n\) classes, et l'ensemble de ces classes a pour cardinal \(n\). On mentionne l'ensemble \(\mathbb{Z}/n\mathbb{Z}\) uniquement sous cette forme — les anneaux \(\mathbb{Z}/n\mathbb{Z}\) sont hors programme à ce niveau ; la structure d'anneau (addition et multiplication des classes) appartient au chapitre Structures algébriques.
Proposition — \(n\) classes modulo \(n\)
Soit \(n \in \mathbb{N}^*\). Pour tout \(a \in \mathbb{Z}\), il existe un unique \(r \in \{0, 1, \dots, n-1\}\) tel que $$ \textcolor{colorprop}{a \equiv r \pmod n.} $$ En conséquence, l'ensemble \(\mathbb{Z}/n\mathbb{Z}\) des classes d'équivalence de \(\equiv \pmod n\) a pour cardinal \(n\), avec pour représentants \(\{0, 1, \dots, n-1\}\).
On applique la division euclidienne de \(a\) par \(n\) (Théorème « Division euclidienne » de la section sur la division euclidienne plus haut) : il existe un unique \((q, r) \in \mathbb{Z} \times \mathbb{N}\) avec \(a = n q + r\) et \(0 \leq r < n\). Alors \(a - r = n q\), soit \(a \equiv r \pmod n\), avec \(r \in \{0, 1, \dots, n-1\}\) unique.
Pour \(r, r' \in \{0, 1, \dots, n-1\}\) distincts, \(|r - r'| < n\) donc \(n \nmid (r - r')\), soit \(r \not\equiv r' \pmod n\). Les classes de \(0, 1, \dots, n-1\) sont donc deux à deux distinctes, et elles recouvrent \(\mathbb{Z}\). Donc \(|\mathbb{Z}/n\mathbb{Z}| = n\).
Pour \(r, r' \in \{0, 1, \dots, n-1\}\) distincts, \(|r - r'| < n\) donc \(n \nmid (r - r')\), soit \(r \not\equiv r' \pmod n\). Les classes de \(0, 1, \dots, n-1\) sont donc deux à deux distinctes, et elles recouvrent \(\mathbb{Z}\). Donc \(|\mathbb{Z}/n\mathbb{Z}| = n\).
Remarque importante (programme)
On utilise ici \(\mathbb{Z}/n\mathbb{Z}\) uniquement comme ensemble des classes de congruence modulo \(n\). Sa structure d'anneau est hors programme et sera étudiée plus tard (chapitre Structures algébriques). Dans ce chapitre, on additionne et on multiplie des représentants (entiers), pas des classes.
Compétences à pratiquer
- Classes de résidus et \(\mathbb{Z}/n\mathbb{Z}\) comme ensemble
V.3
Inverse modulo \(n\) et congruences linéaires
La question « quand \(a\) est-il inversible modulo \(n\) ? » est résolue par le théorème de Bézout : ssi \(a \wedge n = 1\). La construction de l'inverse est constructive (Euclide étendu). Une fois munis des inverses, résoudre la congruence linéaire \(a x \equiv b \pmod n\) se ramène à multiplier les deux membres par \(a^{-1}\).
Définition — Inversible modulo \(n\)
Soit \(n \in \mathbb{N}^*\) et \(a \in \mathbb{Z}\). On dit que \(a\) est inversible modulo \(n\) s'il existe \(u \in \mathbb{Z}\) tel que $$ a u \equiv 1 \pmod n. $$ Un tel \(u\) est appelé un inverse de \(a\) modulo \(n\), souvent noté \(a^{-1} \pmod n\). L'inverse, lorsqu'il existe, est unique à congruence modulo \(n\) près. Exemple
Trouver l'inverse de \(3\) modulo \(7\). On cherche \(x\) tel que \(3 x \equiv 1 \pmod{7}\). En essayant \(x = 5\) : \(3 \cdot 5 = 15 = 2 \cdot 7 + 1\), donc \(3 \cdot 5 \equiv 1 \pmod 7\). D'où \(3^{-1} \equiv 5 \pmod 7\). Proposition — Caractérisation de l'inversibilité
Soit \(n \in \mathbb{N}^*\) et \(a \in \mathbb{Z}\). Alors $$ \textcolor{colorprop}{a \text{ est inversible modulo } n \iff a \wedge n = 1.} $$ Lorsque c'est le cas, un inverse \(u\) de \(a\) modulo \(n\) est donné par n'importe quel coefficient de Bézout : \(a u + n v = 1\) pour un certain \(v \in \mathbb{Z}\). - \((\Leftarrow)\) Supposer \(a \wedge n = 1\). Par le théorème de Bézout, \(a u + n v = 1\) pour certains \(u, v \in \mathbb{Z}\). Alors \(a u = 1 - n v \equiv 1 \pmod n\), donc \(u\) est un inverse de \(a\) modulo \(n\).
- \((\Rightarrow)\) Supposer \(a u \equiv 1 \pmod n\), soit \(a u - 1 = n v\) pour un certain \(v\), donc \(a u + n (-v) = 1\). Par la réciproque du théorème de Bézout, \(a \wedge n = 1\).
Méthode — Résoudre une congruence linéaire \(a x \equiv b \pmod n\)
Soit \(n \in \mathbb{N}^*\), \(a, b \in \mathbb{Z}\), avec \(a \wedge n = 1\) (donc \(a\) inversible mod \(n\)).Étape 1. Calculer \(u = a^{-1} \pmod n\) par l'algorithme d'Euclide étendu : trouver \(u, v\) avec \(a u + n v = 1\).
Étape 2. Multiplier les deux membres de \(a x \equiv b\) par \(u\) : $$ x \equiv u \cdot a x \equiv u \cdot b \pmod n. $$ Étape 3. L'unique solution modulo \(n\) est \(x \equiv u b \pmod n\), donc \(x \in u b + n \mathbb{Z}\).
Si \(a \wedge n = d \neq 1\). La congruence \(a x \equiv b \pmod n\) a une solution ssi \(d \mid b\). Dans ce cas, en divisant par \(d\) on se ramène à la congruence équivalente $$ \frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{n}{d}}, $$ où \(a/d\) est maintenant inversible modulo \(n/d\) (puisque \((a/d) \wedge (n/d) = 1\)). On obtient une solution modulo \(n/d\), donc \(d\) classes de résidus modulo \(n\).
Exemple
Résoudre \(3 x \equiv 5 \pmod 7\).
\(3 \wedge 7 = 1\), donc \(3\) est inversible mod \(7\). Trouver un inverse : \(3 \cdot 5 = 15 \equiv 1 \pmod 7\), donc \(3^{-1} \equiv 5 \pmod 7\). Multiplier les deux membres par \(5\) : $$ x \equiv 5 \cdot 5 \equiv 25 \equiv 4 \pmod 7. $$ Les solutions sont \(x \in 4 + 7 \mathbb{Z} = \{\dots, -10, -3, 4, 11, 18, \dots\}\).
Vérification. \(3 \cdot 4 = 12 \equiv 5 \pmod 7\). \(\checkmark\)
Vérification. \(3 \cdot 4 = 12 \equiv 5 \pmod 7\). \(\checkmark\)
Compétences à pratiquer
- Résoudre des congruences linéaires
V.4
Petit théorème de Fermat
Le petit théorème de Fermat empaquette la structure modulaire des nombres premiers : pour \(p\) premier, \(a^p \equiv a \pmod p\) pour tout entier \(a\). La démonstration a trois étapes : (1) \(p\) divise \(\binom{p}{k}\) pour \(1 \leq k \leq p - 1\) ; (2) par développement binomial et récurrence, le résultat sur \(\mathbb{N}\) ; (3) extension à \(\mathbb{Z}\) en réduisant \(a < 0\) à son représentant positif modulo \(p\).
Théorème — Petit théorème de Fermat
Soit \(p\) un nombre premier. Pour tout \(a \in \mathbb{Z}\), $$ \textcolor{colorprop}{a^p \equiv a \pmod p.} $$ De manière équivalente, si \(p \nmid a\), alors \(a^{p-1} \equiv 1 \pmod p\).
Étape 1 : \(p \mid \binom{p}{k}\) pour tout \(k \in \{1, 2, \dots, p - 1\}\).
Par l'identité standard, \(k! \, (p - k)! \, \binom{p}{k} = p!\), donc \(p \mid k! \, (p - k)! \, \binom{p}{k}\). Comme \(1 \leq k \leq p - 1\), tout facteur de \(k! \, (p - k)!\) appartient à \(\{1, 2, \dots, p - 1\}\), donc est non nul modulo \(p\) (c'est-à-dire premier avec \(p\)). Par le lemme d'Euclide appliqué de manière répétée (ou le lemme de Gauss appliqué avec \(p \wedge (k!) = 1\)), on obtient \(p \mid \binom{p}{k}\).
Étape 2 : récurrence sur \(a \in \mathbb{N}\).
Par la proposition « \(n\) classes modulo \(n\) » plus haut (réduction euclidienne), il existe \(m \in \{0, 1, \dots, p - 1\}\) tel que \(a \equiv m \pmod p\). Alors \(m \in \mathbb{N}\), donc par l'étape 2, \(m^p \equiv m \pmod p\). Par compatibilité des puissances (Proposition « Compatibilité avec somme et produit » dans la section sur la définition et les opérations plus haut), \(a^p \equiv m^p \pmod p\). En combinant avec \(m^p \equiv m\) et \(m \equiv a\), la transitivité donne $$ a^p \equiv m^p \equiv m \equiv a \pmod p. $$ Forme équivalente. Si \(p \nmid a\), alors \(a\) est inversible modulo \(p\) (car \(a \wedge p = 1\) par la Proposition « Divisibilité par un premier et coprimitude » dans la section sur le lemme d'Euclide plus haut). On multiplie \(a^p \equiv a\) par un inverse \(a^{-1}\) : \(a^{p - 1} \equiv 1 \pmod p\).
Par l'identité standard, \(k! \, (p - k)! \, \binom{p}{k} = p!\), donc \(p \mid k! \, (p - k)! \, \binom{p}{k}\). Comme \(1 \leq k \leq p - 1\), tout facteur de \(k! \, (p - k)!\) appartient à \(\{1, 2, \dots, p - 1\}\), donc est non nul modulo \(p\) (c'est-à-dire premier avec \(p\)). Par le lemme d'Euclide appliqué de manière répétée (ou le lemme de Gauss appliqué avec \(p \wedge (k!) = 1\)), on obtient \(p \mid \binom{p}{k}\).
Étape 2 : récurrence sur \(a \in \mathbb{N}\).
- Initialisation \(a = 0\). \(0^p = 0 \equiv 0 \pmod p\). (Pour \(p \geq 2\), la convention \(0^p = 0\).)
- Hérédité. Supposer \(a^p \equiv a \pmod p\). On calcule \((a + 1)^p\) par la formule du binôme : $$ (a + 1)^p = \sum_{k = 0}^{p} \binom{p}{k} a^{p - k} = a^p + \sum_{k = 1}^{p - 1} \binom{p}{k} a^{p - k} + 1. $$ Par l'étape 1, tout \(\binom{p}{k}\) pour \(1 \leq k \leq p - 1\) est divisible par \(p\), donc la somme du milieu est \(\equiv 0 \pmod p\). Combinée à l'hypothèse de récurrence \(a^p \equiv a\), $$ (a + 1)^p \equiv a + 1 \pmod p, $$ ce qui est l'étape d'hérédité.
Par la proposition « \(n\) classes modulo \(n\) » plus haut (réduction euclidienne), il existe \(m \in \{0, 1, \dots, p - 1\}\) tel que \(a \equiv m \pmod p\). Alors \(m \in \mathbb{N}\), donc par l'étape 2, \(m^p \equiv m \pmod p\). Par compatibilité des puissances (Proposition « Compatibilité avec somme et produit » dans la section sur la définition et les opérations plus haut), \(a^p \equiv m^p \pmod p\). En combinant avec \(m^p \equiv m\) et \(m \equiv a\), la transitivité donne $$ a^p \equiv m^p \equiv m \equiv a \pmod p. $$ Forme équivalente. Si \(p \nmid a\), alors \(a\) est inversible modulo \(p\) (car \(a \wedge p = 1\) par la Proposition « Divisibilité par un premier et coprimitude » dans la section sur le lemme d'Euclide plus haut). On multiplie \(a^p \equiv a\) par un inverse \(a^{-1}\) : \(a^{p - 1} \equiv 1 \pmod p\).
Exemple
Calculer \(3^{100} \pmod 7\).
\(7\) est premier et \(7 \nmid 3\), donc par le petit théorème de Fermat \(3^{7 - 1} = 3^6 \equiv 1 \pmod 7\). On réduit l'exposant modulo \(6\) : \(100 = 6 \cdot 16 + 4\), donc $$ 3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 3^4 \equiv 81 \equiv 4 \pmod 7 $$ (car \(81 = 7 \cdot 11 + 4\)).
Méthode — Utiliser Fermat pour réduire \(a^k \pmod p\)
Soit \(p\) premier et \(a, k \in \mathbb{Z}\) avec \(p \nmid a\) et \(k \geq 0\).Étape 1. Vérifier que \(p\) est premier et \(p \nmid a\) (sinon Fermat ne s'applique pas directement).
Étape 2. Réduire l'exposant modulo \(p - 1\) : écrire \(k = (p - 1) q + r\) avec \(0 \leq r \leq p - 2\) (division euclidienne de l'exposant).
Étape 3. Par Fermat, \(a^{p - 1} \equiv 1 \pmod p\), donc $$ a^k = (a^{p - 1})^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod p. $$ Étape 4. Calculer \(a^r \pmod p\) directement (l'exposant est maintenant \(\leq p - 2\)).
Compétences à pratiquer
- Appliquer le petit théorème de Fermat
VI
Pour aller plus loin
Compétences à pratiquer
- Problèmes de synthèse mêlant plusieurs sections
Aller à la section