Corrigé des exercices : Divisibilité et congruences en L1 de maths

---

---

Pour démarrer

Corrigé de l’exercice 1 – Divisions euclidiennes de 2026 et de son opposé

Idée clé : on encadre le dividende entre deux multiples consécutifs de 17, en gardant un reste compris entre 0 et 16.

1. On a \(17 \times 119 = 2023\) et \(17 \times 120 = 2040\). Comme \(2023 \leqslant 2026 < 2040\), on obtient \(2026 = 17 \times 119 + 3\). Pour \(-2026\), le plus grand multiple de 17 inférieur ou égal est \(-2040 = 17 \times (-120)\). Ainsi, \(-2026 = 17 \times (-120) + 14\), avec \(0 \leqslant 14 < 17\).
2. Partons de \(a = bq + r\) avec \(0 < r < b\). Alors \(-a = -bq – r = b(-q – 1) + (b – r)\), et \(0 < b – r < b\). Le reste de \(-a\) vaut donc \(b – r\), et le quotient \(-q – 1\). Ici, \(17 – 3 = 14\). Si \(r = 0\), le reste de \(-a\) est aussi nul.
3. On a \(a \equiv 3 \pmod{17}\). Par compatibilité avec le produit, \(a^2 \equiv 9\). Ensuite, \(a^3 \equiv 27 \equiv 10\), car \(27 – 17 = 10\). Enfin, \(5a + 20 \equiv 15 + 20 = 35 \equiv 1\), car \(35 = 2 \times 17 + 1\). Les restes cherchés sont 9, 10 et 1.

Corrigé de l’exercice 2 – Euclide étendu sur 2431 et 1001

Idée clé : on écrit les divisions successives, puis on les remonte en isolant chaque reste.

1. Les divisions successives donnent \[\begin{aligned} 2431 &= 2 \times 1001 + 429, \\ 1001 &= 2 \times 429 + 143, \\ 429 &= 3 \times 143 + 0. \end{aligned}\] Le dernier reste non nul vaut 143. Donc \(2431 \wedge 1001 = 143\).
2. La deuxième ligne donne \(143 = 1001 – 2 \times 429\). La première donne \(429 = 2431 – 2 \times 1001\). En remplaçant, \(143 = 1001 – 2 \times 2431 + 4 \times 1001 = 5 \times 1001 – 2 \times 2431\). On peut prendre \(u = -2\) et \(v = 5\). Vérification : \(5005 – 4862 = 143\).
3. On trouve \(2431 = 11 \times 221 = 11 \times 13 \times 17\) et \(1001 = 7 \times 11 \times 13\). Les premiers communs sont 11 et 13, chacun avec l’exposant 1. On retrouve bien \(11 \times 13 = 143\).

Corrigé de l’exercice 3 – PGCD d’expressions dépendant de n

Idée clé : une combinaison linéaire qui élimine \(n\) borne le PGCD, car tout diviseur commun la divise.

1. On calcule \(3(5n + 3) – 5(3n + 2) = 9 – 10 = -1\). Ainsi, \((5n+3) \times 3 + (3n+2) \times (-5) = -1\), et donc \((5n+3) \times (-3) + (3n+2) \times 5 = 1\). Cette relation de Bézout égale à 1 prouve que \((5n + 3) \wedge (3n + 2) = 1\).
2. Notons \(d = (2n + 1) \wedge (n + 3)\). Il divise \(2(n + 3) – (2n + 1) = 5\). Les seules valeurs positives possibles sont donc 1 et 5.
3. Si \(d = 5\), alors \(5 \mid n + 3\), soit \(n \equiv 2 \pmod{5}\). Réciproquement, si \(n \equiv 2 \pmod{5}\), alors \(5 \mid n + 3\). De plus, \(2n + 1 = 2(n + 3) – 5\) est aussi divisible par 5. Donc \(d = 5\). Le PGCD vaut 5 exactement pour les entiers \(n = 2 + 5k\), \(k \in \mathbf{Z}\). Par exemple, pour \(n = 7\), on obtient \(15 \wedge 10 = 5\).

Corrigé de l’exercice 4 – Restes de grandes puissances

Idée clé : on cherche une petite puissance congrue à 1, puis on divise l’exposant par sa période.

1. Modulo 10, on a \(7^2 = 49 \equiv -1\), donc \(7^4 \equiv 1\). Or \(2026 = 4 \times 506 + 2\). Par conséquent, \(7^{2026} = (7^4)^{506} \times 7^2 \equiv 49 \equiv 9 \pmod{10}\). Le chiffre des unités est 9.
2. Le module 13 est premier et 6 n’en est pas multiple. Fermat fournit donc \(6^{12} \equiv 1 \pmod{13}\). Ensuite, \(100 = 12 \times 8 + 4\), d’où \(6^{100} \equiv 6^4\). Or \(6^2 = 36 \equiv 10\), puis \(6^4 \equiv 100 = 7 \times 13 + 9\). Le reste vaut 9.
3. On a \(4 \equiv 1 \pmod{3}\). Par compatibilité avec les puissances, \(4^n \equiv 1^n = 1\). Ainsi, \(3 \mid 4^n – 1\) pour tout \(n \in \mathbf{N}\).

Corrigé de l’exercice 5 – PGCD et PPCM par les facteurs premiers

Idée clé : le PGCD prend le plus petit exposant de chaque premier, le PPCM le plus grand.

1. On a \(5040 = 7! = 2 \times 3 \times 4 \times 5 \times 6 \times 7\). En regroupant, \(5040 = 2^4 \times 3^2 \times 5 \times 7\). Ensuite, \(1386 = 2 \times 693 = 2 \times 9 \times 77\). Ainsi, \(1386 = 2 \times 3^2 \times 7 \times 11\).
2. Avec les plus petits exposants, \(5040 \wedge 1386 = 2 \times 3^2 \times 7 = 126\). Avec les plus grands, \(5040 \vee 1386 = 2^4 \times 3^2 \times 5 \times 7 \times 11 = 55440\). Vérification : \(126 \times 55440 = 6\,985\,440\). De même, \(5040 \times 1386 = 5\,040\,000 + 1\,945\,440 = 6\,985\,440\).
3. Un diviseur positif de 5040 s’écrit \(2^{\alpha} 3^{\beta} 5^{\gamma} 7^{\delta}\), avec \(0 \leqslant \alpha \leqslant 4\), \(0 \leqslant \beta \leqslant 2\), et \(\gamma, \delta \in \{0, 1\}\). En effet, l’unicité de la décomposition interdit tout autre facteur premier. Chaque choix d’exposants donne un diviseur différent. On obtient \(5 \times 3 \times 2 \times 2 = 60\) diviseurs.

Corrigé de l’exercice 6 – Vrai ou faux sur la divisibilité

Idée clé : chaque énoncé faux tombe sur un module ou un diviseur qui n’est pas premier.

1. Faux. Par exemple, 10 divise \(4 \times 15 = 60\), mais 10 ne divise ni 4 ni 15. L’énoncé devient vrai si \(a\) est premier, par le lemme d’Euclide.
2. Vrai. La congruence est compatible avec le produit. En multipliant \(a \equiv b\) par lui-même, on obtient \(a^2 \equiv b^2 \pmod{n}\).
3. Faux. Prenons \(n = 8\), \(a = 3\) et \(b = 1\). Alors \(a^2 = 9 \equiv 1 = b^2 \pmod{8}\). Pourtant, 3 n’est congru ni à 1 ni à \(-1 \equiv 7\) modulo 8. En revanche, l’énoncé est vrai pour \(n\) premier, car \(n \mid (a – b)(a + b)\).
4. Faux. Prenons \(n = 4\), \(c = 2\), \(a = 3\) et \(b = 1\). Alors \(ac = 6 \equiv 2 = bc \pmod{4}\), et \(c \not\equiv 0\). Pourtant, \(3 \not\equiv 1 \pmod{4}\). La simplification exige \(c \wedge n = 1\).

Pour s’entraîner

Corrigé de l’exercice 7 – Une équation diophantienne à simplifier

Idée clé : on teste la divisibilité par le PGCD, on simplifie, puis le lemme de Gauss décrit toutes les solutions.

1. L’algorithme d’Euclide donne \(51 = 33 + 18\), \(33 = 18 + 15\), \(18 = 15 + 3\) et \(15 = 5 \times 3\). Donc \(51 \wedge 33 = 3\). Or 3 ne divise pas 10. La première équation n’a aucune solution, car le membre de gauche est toujours multiple de 3. En revanche, 3 divise 12, donc la seconde en a.
2. En divisant par 3, l’équation \(51x + 33y = 12\) équivaut à \(17x + 11y = 4\). Ensuite, \(17 = 11 + 6\), \(11 = 6 + 5\) et \(6 = 5 + 1\). En remontant, \(1 = 6 – 5 = 2 \times 6 – 11 = 2 \times 17 – 3 \times 11\). Ainsi, \(17 \times 2 + 11 \times (-3) = 1\).
3. En multipliant par 4, le couple \((8, -12)\) est solution : \(136 – 132 = 4\). Soit \((x, y)\) une solution. Par différence, \(17(x – 8) = -11(y + 12)\). Donc 11 divise \(17(x – 8)\). Comme \(11 \wedge 17 = 1\), le lemme de Gauss donne \(11 \mid x – 8\). Écrivons \(x = 8 + 11k\). En reportant, \(17 \times 11k = -11(y + 12)\), d’où \(y = -12 – 17k\). Réciproquement, \(17(8 + 11k) + 11(-12 – 17k) = 136 – 132 = 4\). Les solutions sont les couples \((8 + 11k, -12 – 17k)\), \(k \in \mathbf{Z}\).
4. On veut \(0 \leqslant 8 + 11k \leqslant 50\), soit \(-\frac{8}{11} \leqslant k \leqslant \frac{42}{11}\). Les entiers possibles sont \(k = 0, 1, 2, 3\). On obtient \((8, -12)\), \((19, -29)\), \((30, -46)\) et \((41, -63)\). Par exemple, \(17 \times 41 – 11 \times 63 = 697 – 693 = 4\).

La figure place ces quatre points sur la droite d’équation \(17x + 11y = 4\), ainsi que la solution voisine obtenue pour \(k = -1\).

Corrigé de l’exercice 8 – Affranchir une lettre avec deux timbres

Idée clé : on résout l’équation dans \(\mathbf{Z}\), puis on traduit les deux contraintes de signe en un encadrement du paramètre.

1. Le problème revient à trouver \(x, y \in \mathbf{N}\) tels que \(7x + 12y = 200\). De plus, \(7 \times (-5) + 12 \times 3 = -35 + 36 = 1\). Ainsi, 7 et 12 sont premiers entre eux, et la relation de Bézout est vérifiée.
2. En multipliant par 200, le couple \((-1000, 600)\) est solution. Pour une solution \((x, y)\), on obtient \(7(x + 1000) = 12(600 – y)\). Donc 12 divise \(7(x + 1000)\). Or \(12 \wedge 7 = 1\), donc \(12 \mid x + 1000\) par Gauss. On pose \(x = -1000 + 12k\). Il vient alors \(y = 600 – 7k\). Réciproquement, ces couples conviennent, car \(7 \times 12k – 12 \times 7k = 0\). Les solutions entières sont \((-1000 + 12k, 600 – 7k)\), \(k \in \mathbf{Z}\).
3. La condition \(x \geqslant 0\) donne \(k \geqslant \frac{1000}{12} \approx 83{,}3\), soit \(k \geqslant 84\). La condition \(y \geqslant 0\) donne \(k \leqslant \frac{600}{7} \approx 85{,}7\), soit \(k \leqslant 85\). Pour \(k = 84\), on trouve \((8, 12)\). Pour \(k = 85\), on trouve \((20, 5)\). Il y a exactement deux façons : 8 timbres à 7 centimes et 12 à 12 centimes, ou 20 timbres à 7 centimes et 5 à 12 centimes. Vérification : \(56 + 144 = 200\) et \(140 + 60 = 200\).

Corrigé de l’exercice 9 – Entiers premiers entre eux et produits

Idée clé : une relation de Bézout égale à 1 se conserve par produit, et les diviseurs communs se conservent par combinaison.

1. Par Bézout, il existe \(u, v, u^{\prime}, w\) avec \(au + bv = 1\) et \(a u^{\prime} + cw = 1\). En multipliant, \[1 = a\left(a u u^{\prime} + u c w + b v u^{\prime}\right) + bc \, (vw).\] C’est une relation de Bézout entre \(a\) et \(bc\), donc \(a \wedge bc = 1\).
2. Par récurrence sur \(k\), la question 1 donne \(a \wedge b^k = 1\) : on l’applique à \(b\) et \(b^{k-1}\). Ensuite, on échange les rôles : \(b^k\) est premier avec \(a\), donc avec \(a^m\), par la même récurrence. Ainsi, \(a^m \wedge b^k = 1\).
3. Un diviseur commun à \(a + kb\) et \(b\) divise \((a + kb) – kb = a\). Inversement, un diviseur commun à \(a\) et \(b\) divise \(a + kb\). Les deux couples ont les mêmes diviseurs communs. Donc \((a + kb) \wedge b = a \wedge b\).
4. Parmi \(n\) et \(n + 1\), l’un est pair, donc \(2 \mid n(n+1)(n+2)\). Ensuite, les trois entiers \(n, n+1, n+2\) ont des restes distincts modulo 3. L’un d’eux est donc multiple de 3, et \(3 \mid n(n+1)(n+2)\). Enfin, \(2 \wedge 3 = 1\). Par le corollaire du lemme de Gauss, \(6 \mid n(n+1)(n+2)\).

Corrigé de l’exercice 10 – Une infinité de premiers congrus à 3 modulo 4

Idée clé : on adapte la preuve d’Euclide en construisant un entier congru à 3 modulo 4, qui doit avoir un facteur premier du même type.

1. Si \(a \equiv 1\) et \(b \equiv 1 \pmod{4}\), alors \(ab \equiv 1\). Par récurrence sur le nombre de facteurs, tout produit de termes congrus à 1 modulo 4 est congru à 1 modulo 4.
2. L’entier \(N\) est impair, donc tous ses facteurs premiers sont impairs. Chacun est donc congru à 1 ou à 3 modulo 4. S’ils étaient tous congrus à 1, leur produit \(N\) serait congru à 1, par la question 1. Or \(N \equiv 3\). Ainsi, \(N\) a au moins un facteur premier congru à 3 modulo 4.
3. La liste n’est pas vide, car 3 lui appartient. Donc \(N = 4 p_1 \cdots p_k – 1 \geqslant 4 \times 3 – 1 = 11\), et \(N \equiv -1 \equiv 3 \pmod{4}\). D’après la question 2, \(N\) a un facteur premier \(p \equiv 3 \pmod{4}\). Ce \(p\) est l’un des \(p_i\), donc il divise \(4 p_1 \cdots p_k\). Il divise alors \(4 p_1 \cdots p_k – N = 1\), contradiction. La liste des premiers de reste 3 modulo 4 ne peut donc pas être finie.

Corrigé de l’exercice 11 – Inverse de 37 modulo 101 et système de congruences

Idée clé : l’inverse modulaire est le coefficient de Bézout ; un système se résout en reportant la première condition dans la seconde.

1. Le nombre 101 est premier et ne divise pas 37, donc \(37 \wedge 101 = 1\) : 37 est inversible modulo 101. Les divisions successives donnent \[\begin{aligned} 101 &= 2 \times 37 + 27, \quad 37 = 27 + 10, \\ 27 &= 2 \times 10 + 7, \quad 10 = 7 + 3, \quad 7 = 2 \times 3 + 1. \end{aligned}\] En remontant : \(1 = 7 – 2 \times 3 = 3 \times 7 – 2 \times 10 = 3 \times 27 – 8 \times 10\). Puis \(1 = 11 \times 27 – 8 \times 37 = 11 \times 101 – 30 \times 37\). Donc \(37 \times (-30) \equiv 1\). Un inverse de 37 modulo 101 est \(-30 \equiv 71\). Vérification : \(37 \times 71 = 2627 = 26 \times 101 + 1\).
2. On multiplie les deux membres par 71 : \(x \equiv 5 \times 71 = 355 \equiv 355 – 303 = 52 \pmod{101}\). Réciproquement, \(37 \times 52 = 1924 = 19 \times 101 + 5\). Les solutions sont les entiers \(52 + 101k\), \(k \in \mathbf{Z}\).
3. La première condition s’écrit \(x = 3 + 8k\). La seconde devient \(3 + 8k \equiv 5 \pmod{9}\), soit \(8k \equiv 2\). Or \(8 \equiv -1 \pmod{9}\), donc \(-k \equiv 2\), puis \(k \equiv 7 \pmod{9}\). En posant \(k = 7 + 9j\), on obtient \(x = 59 + 72j\). Réciproquement, \(59 = 7 \times 8 + 3\) et \(59 = 6 \times 9 + 5\), et ajouter 72 ne change aucun des deux restes. Enfin, deux solutions diffèrent d’un multiple de 8 et de 9, donc de 72, puisque \(8 \wedge 9 = 1\). Les solutions forment la classe de 59 modulo 72.

Corrigé de l’exercice 12 – Un multiple de 2730 pour tout entier n

Idée clé : Fermat traite chaque facteur premier de 2730 à part ; les cinq divisibilités se combinent ensuite par Gauss.

1. On divise successivement : \(2730 = 2 \times 1365 = 2 \times 3 \times 455 = 2 \times 3 \times 5 \times 91\). Ainsi, \(2730 = 2 \times 3 \times 5 \times 7 \times 13\).
2. Si \(p \mid n\), les deux membres sont congrus à 0 modulo \(p\). Dans le cas contraire, \(n^{p-1} \equiv 1\) d’après Fermat. Posons \(12 = (p – 1) m\). Alors \(n^{12} = (n^{p-1})^m \equiv 1\), puis \(n^{13} \equiv n\). Dans les deux cas, \(n^{13} \equiv n \pmod{p}\).
3. Pour \(p \in \{2, 3, 5, 7, 13\}\), le nombre \(p – 1\) vaut 1, 2, 4, 6 ou 12. Il divise donc 12. Par la question 2, chacun de ces cinq premiers divise \(n^{13} – n\). Ils sont distincts, donc premiers entre eux deux à deux. En appliquant plusieurs fois le corollaire du lemme de Gauss, leur produit divise \(n^{13} – n\). Par conséquent, \(2730 \mid n^{13} – n\) pour tout entier \(n\).

Corrigé de l’exercice 13 – Tester à la main la division par 9 et par 11

Idée clé : on réduit la base 10 modulo le diviseur : \(10 \equiv 1 \pmod{9}\) et \(10 \equiv -1 \pmod{11}\).

1. Comme \(10 \equiv 1 \pmod{9}\), on a \(10^k \equiv 1\) pour tout \(k\). On remplace chaque puissance de 10 par 1 dans l’écriture de \(N\), ce qui donne \(N \equiv \sum c_k \pmod{9}\). Un entier est donc congru modulo 9 à la somme de ses chiffres.
2. De même, \(10 \equiv -1 \pmod{11}\), donc \(10^k \equiv (-1)^k\). On obtient \(N \equiv \sum (-1)^k c_k \pmod{11}\), la somme alternée commençant par le chiffre des unités.
3. La somme des chiffres de 2 026 189 vaut \(2 + 0 + 2 + 6 + 1 + 8 + 9 = 28\), et \(28 \equiv 1 \pmod{9}\). Le reste par 9 vaut 1. La somme alternée, depuis les unités, vaut \(9 – 8 + 1 – 6 + 2 – 0 + 2 = 0\). Le nombre est donc divisible par 11 ; en effet, \(2\,026\,189 = 11 \times 184\,199\).
4. Les chiffres, depuis les unités, sont 2, 5, \(x\), 1 et 3. La somme alternée vaut \(2 – 5 + x – 1 + 3 = x – 1\). Il faut donc \(x \equiv 1 \pmod{11}\). Comme \(x\) est un chiffre, \(x = 1\). Vérification : \(31\,152 = 11 \times 2832\).

Corrigé de l’exercice 14 – Sommes de carrés et restes modulo 4 et 8

Idée clé : les carrés n’occupent que peu de restes ; il suffit d’énumérer les sommes possibles.

1. Si \(n = 2m\), alors \(n^2 = 4m^2 \equiv 0 \pmod{4}\). Si \(n = 2m + 1\), alors \(n^2 = 4(m^2 + m) + 1 \equiv 1\). Un carré est donc congru à 0 ou 1 modulo 4. Par suite, une somme de deux carrés est congrue à 0, 1 ou 2. Or \(2027 = 4 \times 506 + 3\). Ainsi, 2027 n’est pas somme de deux carrés.
2. Pour \(n = 2m + 1\), on a \(n^2 = 4m(m + 1) + 1\). Comme \(m(m+1)\) est pair, \(n^2 \equiv 1 \pmod{8}\). Pour \(n = 2m\), on a \(n^2 = 4m^2\). Si \(m\) est pair, c’est un multiple de 16, donc congru à 0. Si \(m\) est impair, \(m^2 \equiv 1 \pmod{2}\), donc \(4m^2 \equiv 4 \pmod{8}\). Un carré est donc congru à 0, 1 ou 4 modulo 8, comme le montre le diagramme de l’énoncé.
3. Énumérons les sommes de trois termes pris dans \(\{0, 1, 4\}\). Sans terme 4, on obtient 0, 1, 2 ou 3. Avec un seul 4, on obtient 4, 5 ou 6. Avec deux, 8, 9 ou 10, soit 0, 1 ou 2 modulo 8. Avec trois, 12, soit 4. Le reste 7 n’apparaît jamais. Aucun entier congru à 7 modulo 8 n’est somme de trois carrés. Par exemple, \(2023 = 8 \times 252 + 7\) ne l’est pas.

Corrigé de l’exercice 15 – Nombres de Mersenne et exposant premier

Idée clé : une factorisation de l’exposant fournit une factorisation du nombre.

1. Posons \(y = x^a\). L’identité \(y^b – 1 = (y – 1)(1 + y + \dots + y^{b-1})\) donne \(x^{ab} – 1 = (x^a – 1)\left(1 + x^a + x^{2a} + \dots + x^{(b-1)a}\right)\). En particulier, \(x^a – 1\) divise \(x^{ab} – 1\).
2. Raisonnons par contraposée. Supposons \(n\) non premier : \(n = ab\) avec \(2 \leqslant a < n\). Par la question 1 avec \(x = 2\), \(M_a\) divise \(M_n\). Or \(M_a \geqslant 2^2 – 1 = 3\) et \(M_a < M_n\). Donc \(M_n\) a un diviseur strict supérieur à 1. Ainsi, si \(M_n\) est premier, alors \(n\) est premier.
3. On calcule modulo 23 : \(2^5 = 32 \equiv 9\), puis \(2^{10} \equiv 81 \equiv 12\), et \(2^{11} \equiv 24 \equiv 1\). Donc \(23 \mid M_{11}\). En effet, \(M_{11} = 2047 = 23 \times 89\). La réciproque est fausse : 11 est premier, mais \(M_{11}\) ne l’est pas.

Pour approfondir

Corrigé de l’exercice 16 – PGCD de deux nombres de Mersenne

Idée clé : l’algorithme d’Euclide sur les nombres \(M_k\) suit pas à pas l’algorithme d’Euclide sur les exposants.

1. Comme \(2^n \equiv 1 \pmod{M_n}\), on obtient \(2^m = (2^n)^q \, 2^r \equiv 2^r\). En retranchant 1, \(M_m \equiv M_r \pmod{M_n}\).
2. La question 1 donne \(M_m = M_r + t M_n\) pour un entier \(t\). Les diviseurs communs à \(M_m\) et \(M_n\) sont donc ceux de \(M_n\) et \(M_r\). Ainsi, \(M_m \wedge M_n = M_n \wedge M_r\). Raisonnons maintenant par récurrence forte sur \(n\). Si \(r = 0\), alors \(n \mid m\), \(m \wedge n = n\), et \(M_n \wedge M_0 = M_n \wedge 0 = M_n\). Si \(r \geqslant 1\), l’hypothèse de récurrence appliquée au couple \((n, r)\), avec \(r < n\), donne \(M_n \wedge M_r = M_{n \wedge r}\). Or \(n \wedge r = m \wedge n\) par le lemme d’Euclide. Finalement, \(M_m \wedge M_n = M_{m \wedge n}\).
3. On a \(36 \wedge 24 = 12\). Donc \((2^{36} – 1) \wedge (2^{24} – 1) = 2^{12} – 1 = 4095\).
4. Le PGCD est égal à 1 lorsque \(2^{m \wedge n} = 2\), donc lorsque \(m \wedge n = 1\), et seulement dans ce cas. Les nombres \(M_m\) et \(M_n\) sont premiers entre eux exactement quand \(m\) et \(n\) le sont.

Corrigé de l’exercice 17 – Le théorème de Wilson

Idée clé : dans le produit \((p-1)!\), chaque facteur se simplifie avec son inverse, sauf 1 et \(p – 1\).

1. On a \(x^2 – 1 = (x – 1)(x + 1)\). Si \(p\) divise ce produit, le lemme d’Euclide donne \(p \mid x – 1\) ou \(p \mid x + 1\). La réciproque est immédiate. Ainsi, \(x^2 \equiv 1\) équivaut à \(x \equiv \pm 1 \pmod{p}\).
2. Soit \(a \in \{2, \dots, p – 2\}\). Comme \(p\) est premier et ne divise pas \(a\), l’entier \(a\) a un unique inverse \(b\) dans \(\{1, \dots, p – 1\}\). Si \(b = 1\), alors \(a \equiv 1\), ce qui est exclu. Si \(b = p – 1\), alors \(-a \equiv 1\), soit \(a \equiv -1\), exclu aussi. Enfin, \(b = a\) donnerait \(a^2 \equiv 1\), donc \(a \equiv \pm 1\) par la question 1. L’inverse \(b\) est donc dans \(\{2, \dots, p – 2\}\) et distinct de \(a\).
3. Les éléments de \(\{2, \dots, p – 2\}\) se répartissent en paires \(\{a, a^{-1}\}\), de produit congru à 1. Leur produit total est donc congru à 1. Il reste les facteurs 1 et \(p – 1\). Par conséquent, \((p – 1)! \equiv 1 \times (p – 1) \equiv -1 \pmod{p}\). Pour \(p = 2\), on a \(1! = 1 \equiv -1 \pmod{2}\). Le théorème de Wilson est démontré. La figure illustre les paires pour \(p = 13\) : seuls 1 et 12 sont leurs propres inverses.
4. Supposons \(n\) non premier, et soit \(d\) un diviseur avec \(1 < d < n\). Alors \(d \leqslant n – 1\), donc \(d \mid (n – 1)!\). Par hypothèse, \(n\) divise \((n – 1)! + 1\), donc \(d\) aussi. Ainsi, \(d\) divise la différence, qui vaut 1. C’est absurde. Donc \(n\) est premier.

Corrigé de l’exercice 18 – Zéros terminaux de 2026 factorielle

Idée clé : on compte chaque facteur \(p\) autant de fois qu’il apparaît, en regroupant les entiers selon la plus grande puissance de \(p\) qui les divise.

1. Les multiples de \(p^k\) dans \(\{1, \dots, n\}\) sont les \(j p^k\) avec \(1 \leqslant j \leqslant n / p^k\). Il y en a \(\lfloor n / p^k \rfloor\).
2. L’exposant de \(p\) dans un produit est la somme des exposants des facteurs, d’où \(v_p(n!) = \sum_{m \leqslant n} v_p(m)\). Chaque \(v_p(m)\) compte les puissances \(p, p^2, p^3, \dots\) qui divisent \(m\). Comptons autrement : pour chaque \(k\), on dénombre les \(m \leqslant n\) multiples de \(p^k\), et l’on additionne. La question 1 donne alors la formule de Legendre. Seuls les \(k\) avec \(p^k \leqslant n\) apportent une contribution non nulle.
3. Pour \(p = 5\) : \(\lfloor 2026/5 \rfloor = 405\), \(\lfloor 2026/25 \rfloor = 81\), \(\lfloor 2026/125 \rfloor = 16\), \(\lfloor 2026/625 \rfloor = 3\), et les suivants sont nuls. Donc \(v_5(2026!) = 505\). Pour \(p = 2\), on additionne \(1013 + 506 + 253 + 126 + 63 + 31 + 15 + 7 + 3 + 1\). On trouve \(v_2(2026!) = 2018\).
4. L’écriture décimale se termine par \(j\) zéros exactement quand \(10^j\) divise le nombre, sans que \(10^{j+1}\) le divise. Or \(10^j = 2^j 5^j\) divise \(2026!\) si et seulement si \(j \leqslant v_2\) et \(j \leqslant v_5\). Le nombre de zéros vaut donc \(\min(2018, 505)\). L’écriture de \(2026!\) se termine par 505 zéros.

Corrigé de l’exercice 19 – Problème sur un chiffrement RSA miniature

Idée clé : Fermat donne \(m^{ed} \equiv m\) modulo chacun des deux premiers, et le lemme de Gauss recolle le résultat modulo leur produit.

1. On a \(\varphi = 10 \times 16 = 160 = 2^5 \times 5\). Le nombre premier 7 ne divise pas 160. Donc \(7 \wedge 160 = 1\).
2. On écrit \(160 = 22 \times 7 + 6\), puis \(7 = 6 + 1\). En remontant, \(1 = 7 – 6 = 7 – (160 – 22 \times 7) = 23 \times 7 – 160\). Ainsi, \(d = 23\), et l’on vérifie \(7 \times 23 = 161 = 160 + 1\).
3. On calcule modulo 187. D’abord, \(5^2 = 25\). Ensuite, \(5^4 = 625 = 3 \times 187 + 64\), donc \(5^4 \equiv 64\). Puis \(5^6 \equiv 64 \times 25 = 1600 = 8 \times 187 + 104\). Enfin, \(5^7 \equiv 104 \times 5 = 520 = 2 \times 187 + 146\). Le message chiffré est \(c = 146\).
4. On a \(ed = 1 + 160t\) avec \(t \in \mathbf{N}\). Si \(p = 11\) ne divise pas \(m\), Fermat donne \(m^{10} \equiv 1\), donc \(m^{160t} = (m^{10})^{16t} \equiv 1\), puis \(m^{ed} \equiv m \pmod{11}\). Si 11 divise \(m\), les deux membres sont nuls modulo 11. De même, modulo \(q = 17\), on écrit \(160t = 16 \times 10t\) et l’on utilise \(m^{16} \equiv 1\). Dans tous les cas, \(m^{ed} \equiv m\) modulo 11 et modulo 17.
5. Ainsi, 11 et 17 divisent \(m^{ed} – m\). Ils sont premiers distincts, donc premiers entre eux. Par le corollaire du lemme de Gauss, 187 divise \(m^{ed} – m\). Ensuite, \(c^d \equiv (m^e)^d = m^{ed} \equiv m \pmod{187}\). Puisque \(m\) est compris entre 0 et 186, on le récupère en réduisant \(c^d\) modulo 187.
6. Modulo 11, on a \(146 = 13 \times 11 + 3\), donc \(c \equiv 3\). Or \(3^5 = 243 = 22 \times 11 + 1\), donc \(3^{23} = (3^5)^4 \times 3^3 \equiv 27 \equiv 5\). Modulo 17, on a \(146 = 8 \times 17 + 10\), donc \(c \equiv 10\). Par Fermat, \(10^{23} \equiv 10^7\). Puis \(10^2 \equiv -2\), \(10^4 \equiv 4\), \(10^6 \equiv -8\) et \(10^7 \equiv -80 \equiv 5\). Ainsi, \(c^{23} – 5\) est divisible par 11 et par 17, donc par 187. On retrouve bien le message \(m = 5\).

Pour aller plus loin

Télécharger puis imprimer cette fiche en PDF.

Télécharger ou imprimer cette fiche «corrigé des exercices : Divisibilité et congruences en L1 de maths» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

 Maths PDF c'est 16 224 776 cours et exercices de maths téléchargés en PDF et 4 250 exercices.