Corrigé des exercices : PGCD, Bézout et nombres premiers en maths sup (MPSI)

---

---

Pour démarrer

Corrigé de l’exercice 1 – Division euclidienne avec un dividende négatif

Idée clé : une égalité \(a = bq + r\) est la division euclidienne seulement si le reste vérifie \(0 \leqslant r < b\).

1. On a \(37 \times 27 = 999\), donc \(1000 = 37 \times 27 + 1\) avec \(0 \leqslant 1 < 37\). Ensuite, \(-217/15 \approx -14{,}5\), dont la partie entière vaut \(-15\). Or \(15 \times (-15) = -225\), et \(-217 – (-225) = 8\). Ainsi, \(1000 = 37 \times 27 + 1\) et \(-217 = 15 \times (-15) + 8\).
2. D’abord, \((n + 2)(n – 2) + 9 = n^2 – 4 + 9 = n^2 + 5\) : l’égalité est toujours vraie. Elle est la division euclidienne par \(n + 2\) si et seulement si \(0 \leqslant 9 < n + 2\), c’est-à-dire \(n > 7\). C’est donc le cas exactement pour \(n \geqslant 8\).
3. Pour \(n = 3\), on a \(n^2 + 5 = 14\) et \(n + 2 = 5\). Or \(14 = 5 \times 2 + 4\). Le reste vaut \(4\), et non \(9\). En effet, \(9 \geqslant 5\) ne peut pas être un reste dans une division par \(5\).

Corrigé de l’exercice 2 – Algorithme d’Euclide pour 3289 et 2717

Idée clé : on enchaîne les divisions euclidiennes jusqu’à un reste nul ; le dernier reste non nul est le PGCD.

1. Les divisions successives sont :

   \[3289 = 1 \times 2717 + 572,\quad 2717 = 4 \times 572 + 429,\quad 572 = 1 \times 429 + 143,\quad 429 = 3 \times 143 + 0.\]

   Donc \(3289 \wedge 2717 = 143\).

2. On divise numérateur et dénominateur par le PGCD : \(2717 = 143 \times 19\) et \(3289 = 143 \times 23\). Les entiers \(19\) et \(23\) sont premiers entre eux, puisque leur PGCD est \(143/143 = 1\). La forme irréductible est \(\dfrac{19}{23}\).
3. Par la relation \((a \wedge b)(a \vee b) = ab\), on obtient \(3289 \vee 2717 = \dfrac{3289 \times 2717}{143} = 3289 \times 19\). Ainsi, \(3289 \vee 2717 = 62491\).

Le découpage du rectangle de côtés \(3289\) et \(2717\) en carrés reproduit exactement les quotients \(1\), \(4\), \(1\) et \(3\).

Corrigé de l’exercice 3 – Coefficients de Bézout pour 97 et 35

Idée clé : on remonte l’algorithme d’Euclide en exprimant chaque reste à l’aide des deux précédents.

1. Le nombre \(97\) est premier : il n’est divisible ni par \(2\), ni par \(3\), \(5\) ou \(7\), et \(11^2 > 97\). Comme \(97\) ne divise pas \(35\), les entiers \(97\) et \(35\) sont premiers entre eux.
2. Les divisions sont \(97 = 2 \times 35 + 27\), \(35 = 1 \times 27 + 8\), \(27 = 3 \times 8 + 3\), \(8 = 2 \times 3 + 2\) et \(3 = 1 \times 2 + 1\). On remonte :

   \[1 = 3 – 2 = 3 – (8 – 2 \times 3) = 3 \times 3 – 8 = 3 \times 27 – 10 \times 8.\]

   Ensuite, avec \(8 = 35 – 27\), on obtient \(1 = 13 \times 27 – 10 \times 35\). Enfin, avec \(27 = 97 – 2 \times 35\), on trouve \(1 = 13 \times 97 – 36 \times 35\). On vérifie : \(1261 – 1260 = 1\). Ainsi, \(u = 13\) et \(v = -36\) conviennent.

3. En réduisant modulo \(97\), on obtient \(35 \times (-36) \equiv 1\;[97]\). Or \(-36 \equiv 61\;[97]\). Un inverse de \(35\) modulo \(97\) est donc \(61\) ; on vérifie que \(35 \times 61 = 2135 = 22 \times 97 + 1\).
4. Soit \((u, v)\) une solution. Par soustraction avec la solution trouvée, \(97(u – 13) = -35(v + 36)\). Ainsi, \(35\) divise \(97(u – 13)\) et \(35 \wedge 97 = 1\). Par le lemme de Gauss, \(u = 13 + 35k\) avec \(k \in \mathbb{Z}\), puis \(v = -36 – 97k\). On constate inversement que chacun de ces couples vérifie l’égalité. L’ensemble des solutions est formé des \((13 + 35k,\; -36 – 97k)\), \(k \in \mathbb{Z}\).

Corrigé de l’exercice 4 – Diviseurs de 7560 et valuations

Idée clé : un diviseur positif est déterminé par ses valuations, qu’on choisit indépendamment pour chaque premier.

1. On divise successivement : \(7560 = 2^3 \times 945\), puis \(945 = 3^3 \times 35\). De même, \(4410 = 2 \times 2205 = 2 \times 3^2 \times 245\), et \(245 = 5 \times 7^2\). Ainsi, \(7560 = 2^3 \times 3^3 \times 5 \times 7\) et \(4410 = 2 \times 3^2 \times 5 \times 7^2\).
2. Un diviseur positif de \(7560\) s’écrit \(2^\alpha 3^\beta 5^\gamma 7^\delta\) avec \(0 \leqslant \alpha \leqslant 3\), \(0 \leqslant \beta \leqslant 3\), \(\gamma, \delta \in \{0, 1\}\). Ces choix sont indépendants. Il y a donc \(4 \times 4 \times 2 \times 2 = 64\) diviseurs positifs.
3. On prend les minimums d’exposants pour le PGCD et les maximums pour le PPCM. On obtient \(7560 \wedge 4410 = 2 \times 3^2 \times 5 \times 7 = 630\) et \(7560 \vee 4410 = 2^3 \times 3^3 \times 5 \times 7^2 = 52920\). Enfin, \(630 \times 52920 = 33339600\), qui est bien égal à \(7560 \times 4410\).

Corrigé de l’exercice 5 – Inverse de 17 modulo 60

Idée clé : l’inverse se lit dans une relation de Bézout entre \(17\) et \(60\).

1. L’algorithme donne \(60 = 3 \times 17 + 9\), \(17 = 1 \times 9 + 8\) et \(9 = 1 \times 8 + 1\). Donc \(17 \wedge 60 = 1\), et \(17\) est inversible modulo \(60\). On remonte : \(1 = 9 – 8 = 2 \times 9 – 17 = 2 \times 60 – 7 \times 17\). Ainsi, \(17 \times (-7) \equiv 1\;[60]\). L’inverse cherché est \(-7 + 60 = 53\).
2. On multiplie la congruence par \(53\) : \(x \equiv 5 \times 53 = 265\;[60]\). Or \(265 = 4 \times 60 + 25\). Les solutions sont les entiers \(x \equiv 25\;[60]\). On vérifie : \(17 \times 25 = 425\), et \(425 – 5 = 420\) est un multiple de \(60\).

Corrigé de l’exercice 6 – Restes de puissances modulo 13

Idée clé : on réduit l’exposant modulo \(12\) grâce au petit théorème de Fermat, après avoir vérifié son hypothèse.

1. Comme \(13\) est premier et que \(5\) n’en est pas un multiple, Fermat s’applique. On obtient \(5^{12} \equiv 1\;[13]\).
2. On a \(2026 = 12 \times 168 + 10\). Donc \(5^{2026} = (5^{12})^{168} \times 5^{10} \equiv 5^{10}\;[13]\). Ensuite, \(5^2 = 25 \equiv -1\;[13]\), d’où \(5^{10} = (5^2)^5 \equiv -1\;[13]\). Le reste vaut \(12\), et \(13\) divise \(5^{2026} + 1\).
3. De même, \(13 \nmid 3\), donc \(3^{12} \equiv 1\;[13]\). Comme \(100 = 12 \times 8 + 4\), on a \(3^{100} \equiv 3^4 = 81 = 6 \times 13 + 3\). Le reste de \(3^{100}\) modulo \(13\) est \(3\).

La figure de l’énoncé montre que \(5^4 \equiv 1\;[13]\) : l’exposant \(12\) donné par Fermat n’est donc pas le plus petit possible. Ce constat ne change rien au résultat, puisque \(4\) divise \(12\).

Corrigé de l’exercice 7 – Entiers premiers entre eux par Bézout

Idée clé : on élimine \(n\) par une combinaison bien choisie ; si l’on obtient \(\pm 1\), le théorème de Bézout conclut.

1. On calcule \(3(2n + 1) – 2(3n + 2) = 6n + 3 – 6n – 4 = -1\). Ainsi, \((-3)(2n + 1) + 2(3n + 2) = 1\). Par le théorème de Bézout, \((2n + 1) \wedge (3n + 2) = 1\). La fraction est donc irréductible pour tout \(n \in \mathbb{Z}\). Elle est d’ailleurs bien définie, car \(3n + 2 \neq 0\) pour \(n\) entier.
2. On remarque que \(n^2 + n + 1 = n(n + 1) + 1\). Donc \(1 \times (n^2 + n + 1) + (-n)(n + 1) = 1\). Par le théorème de Bézout, \(n^2 + n + 1\) et \(n + 1\) sont premiers entre eux.

Corrigé de l’exercice 8 – Nombres premiers entre 100 et 130

Idée clé : un entier composé \(n\) possède un diviseur premier \(p\) tel que \(p^2 \leqslant n\).

1. Si \(n \leqslant 130\) n’est pas premier, son plus petit diviseur premier \(p\) vérifie \(p^2 \leqslant n \leqslant 130\). Or \(13^2 = 169 > 130\), donc \(p \leqslant 11\). Il suffit de tester \(2\), \(3\), \(5\), \(7\) et \(11\).
2. On écarte d’abord les nombres pairs. Parmi les impairs de \(101\) à \(129\), on retire les multiples de \(3\) (\(105\), \(111\), \(117\), \(123\), \(129\)), ceux de \(5\) (\(115\), \(125\)), puis \(119 = 7 \times 17\) et \(121 = 11^2\). Il reste \(101\), \(103\), \(107\), \(109\), \(113\) et \(127\).
3. On teste les petits premiers : \(1001 = 7 \times 143\), puis \(143 = 11 \times 13\). Ainsi, \(1001 = 7 \times 11 \times 13\).

Pour s’entraîner

Corrigé de l’exercice 9 – Équation diophantienne 39x + 24y = 15

Idée clé : on divise par le PGCD, on trouve une solution particulière, puis le lemme de Gauss donne toutes les autres.

1. D’abord, \(39 = 1 \times 24 + 15\), \(24 = 1 \times 15 + 9\), \(15 = 1 \times 9 + 6\), \(9 = 1 \times 6 + 3\) et \(6 = 2 \times 3\). Donc \(39 \wedge 24 = 3\), qui divise \(15\). L’équation équivaut à \(13x + 8y = 5\). Ensuite, \((1, -1)\) est solution, car \(13 – 8 = 5\). Par soustraction, \(13(x – 1) = -8(y + 1)\). Comme \(8 \wedge 13 = 1\), le lemme de Gauss donne \(8 \mid x – 1\), donc \(x = 1 + 8k\), puis \(y = -1 – 13k\). Réciproquement, \(13(1 + 8k) + 8(-1 – 13k) = 5\). Les solutions sont les couples \((1 + 8k,\; -1 – 13k)\), \(k \in \mathbb{Z}\).
2. Le PGCD \(3\) divise \(39x + 24y\) pour tous entiers \(x\), \(y\). Or \(3\) ne divise pas \(20\). Cette équation n’a donc aucune solution entière.

Corrigé de l’exercice 10 – Stylos à 7 euros et cahiers à 11 euros

Idée clé : on réduit l’équation modulo \(11\) pour obtenir \(x\), puis la positivité limite les solutions à un nombre fini.

1. On a \(7 \times 8 = 56 = 5 \times 11 + 1\). Un inverse de \(7\) modulo \(11\) est donc \(8\).
2. Si \(7x + 11y = 200\), alors \(7x \equiv 200\;[11]\). Or \(200 = 18 \times 11 + 2\), donc \(7x \equiv 2\;[11]\). En multipliant par \(8\), on obtient \(x \equiv 16\;[11]\). Ainsi, \(x \equiv 5\;[11]\).
3. On écrit \(x = 5 + 11k\) avec \(k \in \mathbb{Z}\). Alors \(11y = 200 – 35 – 77k = 165 – 77k\), donc \(y = 15 – 7k\). Réciproquement, ces couples vérifient l’équation. Ensuite, les conditions \(x \geqslant 0\) et \(y \geqslant 0\) imposent \(k \geqslant 0\) et \(k \leqslant 15/7\), soit \(k \in \{0, 1, 2\}\). Les achats possibles sont \((5, 15)\), \((16, 8)\) et \((27, 1)\), en nombre de stylos et de cahiers.

La figure place ces trois solutions sur le segment de droite de l’énoncé.

Corrigé de l’exercice 11 – Quand n + 3 divise n² + 10

Idée clé : on élimine \(n\) du dividende ; \(n + 3\) doit alors diviser une constante.

1. On calcule \((n + 3)(n – 3) = n^2 – 9\). Donc \(n^2 + 10 = (n + 3)(n – 3) + 19\).
2. Si \(n + 3\) divise \(n^2 + 10\), il divise aussi \(n^2 + 10 – (n + 3)(n – 3) = 19\). Réciproquement, si \(n + 3\) divise \(19\), il divise la somme \((n + 3)(n – 3) + 19\). La condition équivaut donc à \(n + 3 \in \{-19, -1, 1, 19\}\), puisque \(19\) est premier. Les solutions sont \(n = -22\), \(n = -4\), \(n = -2\) et \(n = 16\). Par exemple, pour \(n = 16\), on a \(266 = 19 \times 14\).

Corrigé de l’exercice 12 – Racines rationnelles d’un polynôme à coefficients entiers

Idée clé : on chasse les dénominateurs, puis on isole un terme pour faire apparaître une divisibilité ; le lemme de Gauss conclut.

1. L’égalité \(P(p/q) = 0\), multipliée par \(q^3\), donne \(6p^3 – 5p^2q – 2pq^2 + q^3 = 0\). Ainsi, \(q^3 = -p(6p^2 – 5pq – 2q^2)\), donc \(p\) divise \(q^3\). Or \(p \wedge q = 1\), donc \(p \wedge q^3 = 1\) par applications répétées du lemme de Gauss. Par conséquent, \(p\) divise \(1\). De même, \(6p^3 = q(5p^2 + 2pq – q^2)\), donc \(q\) divise \(6p^3\). Comme \(q \wedge p^3 = 1\), le lemme de Gauss donne \(q \mid 6\). Ainsi, \(p \mid 1\) et \(q \mid 6\).
2. On a donc \(p = \pm 1\) et \(q \in \{1, 2, 3, 6\}\). Les candidats sont \(\pm 1\), \(\pm 1/2\), \(\pm 1/3\) et \(\pm 1/6\).
3. On teste : \(P(1) = 6 – 5 – 2 + 1 = 0\). Ensuite, \(P(1/3) = \frac{2}{9} – \frac{5}{9} – \frac{6}{9} + \frac{9}{9} = 0\). Enfin, \(P(-1/2) = -\frac{3}{4} – \frac{5}{4} + 1 + 1 = 0\). Un polynôme de degré \(3\) a au plus trois racines. Les racines sont \(1\), \(1/3\) et \(-1/2\), et \(P(x) = (x – 1)(3x – 1)(2x + 1)\). On vérifie en développant : \((3x – 1)(2x + 1) = 6x^2 + x – 1\), puis le produit par \(x – 1\) redonne \(P\).

Corrigé de l’exercice 13 – PGCD égal à 12 et PPCM égal à 360

Idée clé : on factorise par le PGCD ; les quotients sont premiers entre eux et leur produit est imposé par le PPCM.

1. Supposons \(a \wedge b = 12\). On écrit \(a = 12\alpha \) et \(b = 12\beta \), avec \(\alpha \wedge \beta = 1\). Ensuite, \(a \vee b = ab/(a \wedge b) = 144\alpha \beta /12 = 12\alpha \beta \). La condition \(a \vee b = 360\) donne alors \(\alpha \beta = 30\). Réciproquement, si \(a = 12\alpha \), \(b = 12\beta \), \(\alpha \beta = 30\) et \(\alpha \wedge \beta = 1\), alors \(a \wedge b = 12(\alpha \wedge \beta ) = 12\) et \(a \vee b = 12\alpha \beta = 360\). L’équivalence est démontrée.
2. Les décompositions \(30 = \alpha \beta \) avec \(\alpha \leqslant \beta \) sont \(1 \times 30\), \(2 \times 15\), \(3 \times 10\) et \(5 \times 6\). Chacune est formée d’entiers premiers entre eux, car \(30\) n’a pas de facteur carré. Les couples sont \((12, 360)\), \((24, 180)\), \((36, 120)\) et \((60, 72)\).

Corrigé de l’exercice 14 – Zéros terminaux de 250!

Idée clé : un zéro final correspond à un facteur \(10 = 2 \times 5\), donc on compte le facteur le plus rare.

1. On a \(v_p(n!) = \sum_{j \geqslant 1}\lfloor n/p^j \rfloor\). En effet, \(\lfloor n/p^j \rfloor\) est le nombre d’entiers de \([1, n]\) divisibles par \(p^j\). Un entier \(k\) de valuation \(v_p(k) = m\) est divisible par \(p, p^2, \ldots, p^m\), mais pas par \(p^{m+1}\). Il est donc compté exactement \(m\) fois dans la somme.
2. On calcule les quotients entiers. Pour \(p = 2\) : \(125 + 62 + 31 + 15 + 7 + 3 + 1 = 244\). Pour \(p = 3\) : \(83 + 27 + 9 + 3 + 1 = 123\). Pour \(p = 5\) : \(50 + 10 + 2 = 62\). Ainsi, \(v_2(250!) = 244\), \(v_3(250!) = 123\) et \(v_5(250!) = 62\).
3. Le nombre de zéros finaux est la valuation de \(250!\) en \(10\), c’est-à-dire le plus grand \(k\) tel que \(2^k 5^k\) divise \(250!\). Il vaut \(\min(244, 62)\). L’écriture de \(250!\) se termine par \(62\) zéros.
4. De même, \(6^k = 2^k 3^k\) divise \(250!\) si et seulement si \(k \leqslant 244\) et \(k \leqslant 123\). Le plus grand entier \(k\) est \(123\).

La figure détaille la contribution de chaque puissance de \(2\) et de \(5\) à ces valuations.

Corrigé de l’exercice 15 – Produit de deux entiers premiers entre eux qui est un carré

Idée clé : pour un entier \(n \geqslant 1\), être un carré revient à n’avoir que des exposants pairs dans sa décomposition.

1. Si \(a^2 \mid b^2\), alors pour tout premier \(p\), \(v_p(a^2) \leqslant v_p(b^2)\), soit \(2v_p(a) \leqslant 2v_p(b)\). On divise par \(2\) : \(v_p(a) \leqslant v_p(b)\) pour tout \(p\). Par conséquent, \(a\) divise \(b\).
2. Soit \(p\) un premier. Comme \(a \wedge b = 1\), il ne divise pas à la fois \(a\) et \(b\) : l’une des deux valuations est nulle. Ainsi, \(v_p(a)\) vaut \(0\) ou \(v_p(ab)\), et ce dernier est pair puisque \(ab\) est un carré. Toutes les valuations de \(a\) sont donc paires, et de même pour \(b\). On écrit alors \(a = \prod p^{2k_p} = \left(\prod p^{k_p}\right)^2\). Ainsi, \(a\) et \(b\) sont des carrés parfaits.
3. Pour \(n = 0\), le produit vaut \(0 = 0^2\). Soit ensuite \(n \geqslant 1\) tel que \(n(n + 1)\) soit un carré. Comme \(n \wedge (n + 1) = 1\), la question 2 donne \(n = s^2\) et \(n + 1 = t^2\), avec \(t > s \geqslant 1\). Alors \((t – s)(t + s) = 1\), ce qui impose \(t + s = 1\). C’est impossible, puisque \(t + s \geqslant 3\). Seul \(n = 0\) convient.

Corrigé de l’exercice 16 – Congruences linéaires modulo 35

Idée clé : si le coefficient est inversible, on multiplie par l’inverse ; sinon, on divise tout par le PGCD, à condition qu’il divise le second membre.

1. On a \(8 \wedge 35 = 1\), et \(8 \times 22 = 176 = 5 \times 35 + 1\) : l’inverse de \(8\) est \(22\). On multiplie par \(22\) : \(x \equiv 132\;[35]\), et \(132 = 3 \times 35 + 27\). Les solutions sont les \(x \equiv 27\;[35]\). On vérifie : \(8 \times 27 = 216 = 6 \times 35 + 6\).
2. Ici \(21 \wedge 35 = 7\). La congruence signifie \(35 \mid 21x – 14\), c’est-à-dire \(7 \times 5 \mid 7(3x – 2)\), soit \(5 \mid 3x – 2\). Or \(2\) est l’inverse de \(3\) modulo \(5\), donc \(x \equiv 4\;[5]\). Les solutions sont les entiers \(x \equiv 4\;[5]\), soit sept classes modulo \(35\) : \(4\), \(9\), \(14\), \(19\), \(24\), \(29\) et \(34\).
3. Si \(21x \equiv 10\;[35]\), il existe \(k\) tel que \(21x – 35k = 10\). Or \(7\) divise le premier membre, mais pas \(10\). Il n’y a donc aucune solution.

Corrigé de l’exercice 17 – Divisibilité de n⁷ − n par 42

Idée clé : on décompose \(42 = 2 \times 3 \times 7\), on traite chaque premier par Fermat, puis on recolle grâce au lemme de Gauss.

1. Le nombre \(7\) est premier. La forme \(a^p \equiv a\;[p]\) du petit théorème de Fermat donne \(n^7 \equiv n\;[7]\) pour tout entier \(n\), sans hypothèse sur \(n\).
2. De même, \(n^3 \equiv n\;[3]\). Ainsi, \(n^7 = n^3 \times n^3 \times n \equiv n \times n \times n = n^3 \equiv n\;[3]\). Ensuite, \(n^2 \equiv n\;[2]\), puisque \(n^2 – n = n(n – 1)\) est pair. Par récurrence, \(n^k \equiv n\;[2]\) pour tout \(k \geqslant 1\). Donc \(n^7 \equiv n\;[3]\) et \(n^7 \equiv n\;[2]\).
3. Notons \(m = n^7 – n\). Les entiers \(2\) et \(3\) divisent \(m\) et sont premiers entre eux, donc \(6 \mid m\). Ensuite, \(7 \mid m\) et \(6 \wedge 7 = 1\), donc \(42 \mid m\). Ainsi, \(42\) divise \(n^7 – n\) pour tout entier \(n\).

Corrigé de l’exercice 18 – Relation de Bézout pour trois entiers

Idée clé : on traite d’abord deux entiers, puis on combine la relation obtenue avec le troisième.

1. D’abord, \(140 = 1 \times 84 + 56\), \(84 = 1 \times 56 + 28\) et \(56 = 2 \times 28\), donc \(84 \wedge 140 = 28\). Ensuite, \(210 = 7 \times 28 + 14\) et \(28 = 2 \times 14\), donc \(28 \wedge 210 = 14\). Ainsi, \(d = 14\).
2. On remonte : \(28 = 84 – 56 = 84 – (140 – 84) = 2 \times 84 – 140\). Puis \(14 = 210 – 7 \times 28 = 210 – 14 \times 84 + 7 \times 140\). On vérifie : \(-1176 + 980 + 210 = 14\). Les entiers \(u = -14\), \(v = 7\) et \(w = 1\) conviennent.
3. Les quotients sont \(6\), \(10\) et \(15\). Leur PGCD vaut \(1\), mais \(6 \wedge 10 = 2\). Ils ne sont donc pas premiers entre eux deux à deux.

Pour approfondir

Corrigé de l’exercice 19 – PGCD de 2^a − 1 et 2^b − 1

Idée clé : l’algorithme d’Euclide sur les exposants se transporte sur les nombres \(2^a – 1\), grâce au lemme \(x \wedge y = y \wedge (x – ky)\).

1. Posons \(x = 2^b\). Si \(q \geqslant 1\), la factorisation \(x^q – 1 = (x – 1)(x^{q-1} + \cdots + x + 1)\) montre que \(2^b – 1\) divise \(2^{bq} – 1\). Si \(q = 0\), alors \(2^{bq} – 1 = 0\), qui est divisible par tout entier. Dans tous les cas, \(2^b – 1 \mid 2^{bq} – 1\).
2. On développe : \(2^r(2^{bq} – 1) + 2^r – 1 = 2^{r + bq} – 1 = 2^a – 1\). Écrivons \(2^{bq} – 1 = K(2^b – 1)\) avec \(K\) entier, d’après la question 1. Alors \(2^a – 1 = 2^rK(2^b – 1) + (2^r – 1)\). Le lemme d’Euclide s’applique avec le quotient \(2^rK\). Ainsi, \((2^a – 1) \wedge (2^b – 1) = (2^b – 1) \wedge (2^r – 1)\).
3. On raisonne par récurrence forte sur \(b \in \mathbb{N}\), pour tout \(a \in \mathbb{N}\). Si \(b = 0\), alors \(2^b – 1 = 0\), et \((2^a – 1) \wedge 0 = 2^a – 1 = 2^{a \wedge 0} – 1\). Ensuite, soit \(b \geqslant 1\), et supposons le résultat vrai pour tout second exposant strictement inférieur à \(b\). Avec \(a = bq + r\) et \(0 \leqslant r < b\), la question 2 et l’hypothèse de récurrence donnent \((2^a – 1) \wedge (2^b – 1) = 2^{b \wedge r} – 1\). Or \(b \wedge r = a \wedge b\) par le lemme d’Euclide. Donc \((2^a – 1) \wedge (2^b – 1) = 2^{a \wedge b} – 1\).
4. On a \(84 = 1 \times 60 + 24\), \(60 = 2 \times 24 + 12\) et \(24 = 2 \times 12\). Donc \(84 \wedge 60 = 12\). Le PGCD cherché vaut \(2^{12} – 1 = 4095\).
5. Supposons \(n\) non premier. Si \(n = 1\), alors \(2^n – 1 = 1\) n’est pas premier. Sinon, \(n = de\) avec \(1 < d < n\). Par la question 1, \(2^d – 1\) divise \(2^n – 1\), et \(1 < 2^d – 1 < 2^n – 1\). Ainsi, \(2^n – 1\) a un diviseur strict non trivial. Par contraposée, si \(2^n – 1\) est premier, alors \(n\) est premier.

La réciproque de la question 5 est fausse : \(11\) est premier, mais \(2^{11} – 1 = 2047 = 23 \times 89\). Les nombres premiers de la forme \(2^p – 1\) sont rares et très recherchés.

Corrigé de l’exercice 20 – Problème : une infinité de premiers congrus à 5 modulo 6

Idée clé : on adapte la preuve d’Euclide, en construisant un entier congru à \(5\) modulo \(6\) qui échappe à la liste supposée complète.

1. Soit \(p \geqslant 5\) premier et \(r\) son reste modulo \(6\). Si \(r \in \{0, 2, 4\}\), alors \(p\) est pair, donc \(p = 2\) : exclu. Si \(r = 3\), alors \(3 \mid p\), donc \(p = 3\) : exclu. Ainsi, \(p \equiv 1\;[6]\) ou \(p \equiv 5\;[6]\).
2. La congruence est compatible avec la multiplication. Si \(a_1 \equiv \cdots \equiv a_k \equiv 1\;[6]\), alors \(a_1 \cdots a_k \equiv 1^k = 1\;[6]\). Le produit est donc congru à \(1\) modulo \(6\).
3. La liste contient \(5\), donc \(r \geqslant 1\) et \(N \geqslant 29\). Ensuite, \(N \equiv -1 \equiv 5\;[6]\) : \(N\) est impair et n’est pas multiple de \(3\). Enfin, si \(p_i\) divisait \(N\), il diviserait \(6p_1 \cdots p_r – N = 1\), ce qui est absurde. Ainsi, \(N\) n’est divisible ni par \(2\), ni par \(3\), ni par aucun \(p_i\).
4. Les facteurs premiers de \(N\) sont donc au moins égaux à \(5\). Par la question 1, chacun est congru à \(1\) ou \(5\) modulo \(6\). Or aucun n’est congru à \(5\), car ce serait l’un des \(p_i\). Tous sont donc congrus à \(1\), et la question 2 donne \(N \equiv 1\;[6]\). Cela contredit \(N \equiv 5\;[6]\). Il existe donc une infinité de nombres premiers congrus à \(5\) modulo \(6\).
5. L’argument repose sur le fait qu’un entier congru à \(5\) modulo \(6\) possède forcément un facteur premier congru à \(5\). En revanche, un entier congru à \(1\) peut n’avoir que des facteurs congrus à \(5\). Par exemple, \(25 = 5 \times 5 \equiv 1\;[6]\). La contradiction disparaît, et la méthode échoue.

Corrigé de l’exercice 21 – Problème : un chiffrement par puissances modulo 55

Idée clé : l’exposant \(81 = 3 \times 27\) vaut \(1\) plus un multiple de \(4\) et de \(10\), ce qui permet d’appliquer Fermat modulo \(5\) et modulo \(11\).

1. On a \(55 = 5 \times 11\), avec \(5\) et \(11\) premiers. Ensuite, \(3 \times 27 – 1 = 80 = 4 \times 20 = 10 \times 8\). Le nombre \(80\) est bien un multiple de \(4\) et de \(10\).
2. Si \(5 \mid m\), les deux membres sont congrus à \(0\) modulo \(5\). Sinon, le petit théorème de Fermat donne \(m^4 \equiv 1\;[5]\). Alors \(m^{80} = (m^4)^{20} \equiv 1\;[5]\), puis \(m^{81} \equiv m\;[5]\). Dans tous les cas, \(m^{81} \equiv m\;[5]\).
3. De même, si \(11 \nmid m\), alors \(m^{10} \equiv 1\;[11]\), donc \(m^{80} = (m^{10})^8 \equiv 1\) et \(m^{81} \equiv m\;[11]\). Le cas \(11 \mid m\) est immédiat. Ensuite, \(5\) et \(11\) divisent \(m^{81} – m\) et sont premiers entre eux. Par le corollaire du lemme de Gauss, \(55\) divise \(m^{81} – m\).
4. Le destinataire calcule le reste de \(c^{27}\) modulo \(55\). Or \(c \equiv m^3\;[55]\), donc \(c^{27} \equiv m^{81} \equiv m\;[55]\). Comme \(m \in \{0, \ldots, 54\}\), ce reste est exactement \(m\). Le déchiffrement redonne toujours le message.
5. On a \(7^3 = 343 = 6 \times 55 + 13\), donc le chiffré est \(c = 13\). Ensuite, \(13^2 = 169 \equiv 4\), \(13^4 \equiv 16\), \(13^8 \equiv 256 \equiv 36\) et \(13^{16} \equiv 36^2 = 1296 \equiv 31\;[55]\). Comme \(27 = 16 + 8 + 2 + 1\), on calcule \(31 \times 36 = 1116 \equiv 16\), puis \(16 \times 4 = 64 \equiv 9\), enfin \(9 \times 13 = 117 \equiv 7\;[55]\). On retrouve bien le message \(m = 7\).

Ce mécanisme est une version miniature des chiffrements à clé publique. Sa sécurité repose sur la difficulté de factoriser le module : ici, \(55 = 5 \times 11\) se factorise de tête, si bien que le chiffrement n’offre aucune protection réelle. Avec des premiers de plusieurs centaines de chiffres, la situation change complètement.

Pour aller plus loin

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

Télécharger ou imprimer cette fiche «corrigé des exercices : PGCD, Bézout et nombres premiers en maths sup (MPSI)» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

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