Corrigé des exercices : Z/nZ, idéaux et théorème chinois en maths spé (MP)

---

---

Pour démarrer

Corrigé de l’exercice 1 – Inverse de 7 modulo 23

Idée clé : une relation de Bézout entre \(7\) et \(23\) donne directement l’inverse, puis on multiplie l’équation par cet inverse.

1. Comme \(23\) est premier, \(\mathbb{Z}/23\mathbb{Z}\) est un corps. Or \(7\) n’est pas multiple de \(23\), donc \(\bar{7} \neq \bar{0}\). Par conséquent, \(\bar{7}\) est inversible.
2. On effectue \(23 = 3 \times 7 + 2\), puis \(7 = 3 \times 2 + 1\). En remontant, \(1 = 7 – 3 \times 2 = 7 – 3(23 – 3 \times 7) = 10 \times 7 – 3 \times 23\). Ainsi \(7 \times 10 \equiv 1 \pmod{23}\). Vérification : \(70 = 3 \times 23 + 1\). L’inverse de \(\bar{7}\) est \(\overline{10}\).
3. On multiplie les deux membres par \(\overline{10}\), ce qui est licite car \(\overline{10}\) est inversible. On obtient \(x \equiv 50 \equiv 4 \pmod{23}\). Réciproquement, \(7 \times 4 = 28 = 23 + 5\). Les solutions sont les entiers \(x \equiv 4 \pmod{23}\).

Corrigé de l’exercice 2 – Trois indicatrices d’Euler

Idée clé : on décompose en facteurs premiers, puis on combine la formule \(\varphi(p^\alpha) = p^\alpha – p^{\alpha-1}\) et la multiplicativité sur des facteurs premiers entre eux.

1. On a \(360 = 2^3 \times 3^2 \times 5\). Les facteurs \(8\), \(9\) et \(5\) sont deux à deux premiers entre eux. Donc \(\varphi(360) = \varphi(8)\varphi(9)\varphi(5) = 4 \times 6 \times 4\). Ainsi \(\varphi(360) = 96\).
2. On a \(1\,001 = 7 \times 11 \times 13\), produit de trois premiers distincts. Par conséquent, \(\varphi(1\,001) = 6 \times 10 \times 12\). Ainsi \(\varphi(1\,001) = 720\).
3. Ici \(\varphi(2^5) = 32 – 16 = 16\) et \(\varphi(7^2) = 49 – 7 = 42\). Comme \(2^5 \wedge 7^2 = 1\), on obtient \(16 \times 42\). Ainsi \(\varphi(1\,568) = 672\).

Corrigé de l’exercice 3 – Les inversibles de Z/18Z

Idée clé : les inversibles sont les classes des entiers premiers avec \(18\), c’est-à-dire ni pairs ni multiples de \(3\).

1. Les entiers de \(1\) à \(17\) premiers avec \(18 = 2 \times 3^2\) sont \(1, 5, 7, 11, 13, 17\). D’autre part, \(\varphi(18) = \varphi(2)\varphi(9) = 1 \times 6 = 6\). Donc \((\mathbb{Z}/18\mathbb{Z})^\times = \{\bar{1}, \bar{5}, \bar{7}, \overline{11}, \overline{13}, \overline{17}\}\), de cardinal \(6\).
2. On calcule modulo \(18\) : \(5^2 = 25 \equiv 7\), puis \(5^3 \equiv 35 \equiv 17\), \(5^4 \equiv 85 \equiv 13\), \(5^5 \equiv 65 \equiv 11\) et enfin \(5^6 \equiv 55 \equiv 1\). Les six puissances sont distinctes, donc \(\bar{5}\) est d’ordre \(6\). Le groupe des inversibles, de cardinal \(6\), est cyclique engendré par \(\bar{5}\).
3. Comme \(5^6 \equiv 1\), on a \(5 \times 5^5 \equiv 1\). Donc \(\bar{5}^{-1} = \bar{5}^5\). L’inverse de \(\bar{5}\) est \(\overline{11}\), et en effet \(55 = 3 \times 18 + 1\).

La figure trace le cycle des puissances de \(\bar{5}\) sur le cercle de \(\mathbb{Z}/18\mathbb{Z}\). Il passe une fois par chaque inversible.

Corrigé de l’exercice 4 – Somme et intersection d’idéaux de Z

Idée clé : la somme d’idéaux correspond au PGCD et l’intersection au PPCM ; une combinaison égale à \(1\) prouve qu’un idéal est \(\mathbb{Z}\).

1. On a \(12 = 2^2 \times 3\) et \(42 = 2 \times 3 \times 7\). Donc \(12 \wedge 42 = 6\) et \(12 \vee 42 = 2^2 \times 3 \times 7 = 84\). Ainsi \(d = 6\) et \(m = 84\).
2. D’après la question précédente, la somme vaut \(6\mathbb{Z} + 35\mathbb{Z}\). Or \(6 \wedge 35 = 1\), donc cette somme est \(\mathbb{Z}\). Concrètement, \(6 = 42 – 3 \times 12\) et \(6 \times 6 – 35 = 1\). On en déduit \(1 = 6 \times 42 – 18 \times 12 – 35\). Vérification : \(252 – 216 – 35 = 1\).
3. On calcule \(7(5k + 3) – 5(7k + 4) = 21 – 20 = 1\). Ainsi \(1\) appartient à l’idéal engendré par \(5k + 3\) et \(7k + 4\). Cet idéal contient \(1\), donc il est égal à \(\mathbb{Z}\).

Corrigé de l’exercice 5 – Un premier système de congruences

Idée clé : on écrit \(x = 2 + 5k\) et on reporte dans la seconde congruence.

1. Les modules \(5\) et \(7\) sont premiers entre eux, donc le théorème chinois assure une unique solution modulo \(35\). Avec \(x = 2 + 5k\), la condition devient \(5k \equiv 1 \pmod 7\). Or \(5 \times 3 = 15 \equiv 1\), donc \(k \equiv 3 \pmod 7\). Ainsi \(x = 2 + 5(3 + 7j) = 17 + 35j\). Vérification : \(17 = 3 \times 5 + 2\) et \(17 = 2 \times 7 + 3\). Les solutions sont les \(x \equiv 17 \pmod{35}\).
2. On a \(997 = 17 + 28 \times 35\), qui est inférieur à \(1\,000\). La solution suivante est \(997 + 35\). Le plus petit entier cherché est \(1\,032\).

Corrigé de l’exercice 6 – Inversibles et idempotents d’un produit d’anneaux

Idée clé : tout se calcule composante par composante dans un produit d’anneaux.

1. Si \(e^2 = e\), alors \(e(e – 1) = 0\). Dans un anneau intègre, on en déduit \(e = 0\) ou \(e = 1\). Les idempotents d’un anneau intègre sont \(0\) et \(1\).
2. Le couple \((a, b)\) est idempotent si et seulement si \(a^2 = a\) et \(b^2 = b\). D’après la question 1, \(a \in \{0, 1\}\) et \(b \in \{0, 1\}\). Les idempotents de \(A \times B\) sont \((0, 0)\), \((1, 0)\), \((0, 1)\) et \((1, 1)\).
3. On a \((A \times B)^\times = A^\times \times B^\times\). Or \(\mathbb{Z}^\times = \{-1, 1\}\) et \(\mathbb{F}_5^\times\) a quatre éléments. Ainsi \((\mathbb{Z} \times \mathbb{Z})^\times = \{\pm 1\} \times \{\pm 1\}\) a \(4\) éléments, et \((\mathbb{Z} \times \mathbb{F}_5)^\times = \{\pm 1\} \times \mathbb{F}_5^\times\) en a \(8\).

Pour s’entraîner

Corrigé de l’exercice 7 – Trois congruences simultanées

Idée clé : on résout deux congruences, puis on recolle la troisième, en vérifiant d’abord que les modules sont deux à deux premiers entre eux.

1. Les entiers \(4\), \(9\) et \(5\) sont deux à deux premiers entre eux. Le théorème chinois, étendu à trois facteurs, donne \(\mathbb{Z}/180\mathbb{Z} \simeq \mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/9\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z}\). Les trois conditions déterminent donc \(N\) modulo \(180\).
2. D’abord, on écrit \(N = 5 + 9k\). La condition modulo \(4\) devient \(1 + k \equiv 3\), soit \(k \equiv 2 \pmod 4\). Ainsi \(N \equiv 23 \pmod{36}\). Ensuite, on écrit \(N = 23 + 36j\). Modulo \(5\), on obtient \(3 + j \equiv 2\), donc \(j \equiv 4 \pmod 5\). Par conséquent, \(N \equiv 23 + 144 = 167 \pmod{180}\). Vérification : \(167 = 41 \times 4 + 3 = 18 \times 9 + 5 = 33 \times 5 + 2\). Entre \(1\) et \(500\), les candidats sont \(167\), \(347\) et \(527\), et le dernier est trop grand. Donc \(N = 167\) ou \(N = 347\).

Corrigé de l’exercice 8 – Modules non premiers entre eux

Idée clé : le système est compatible si et seulement si les deux seconds membres coïncident modulo \(12 \wedge 18 = 6\).

1. On a \(11 – 5 = 6\), multiple de \(6\) : le système est compatible. On pose \(x = 5 + 12k\). La seconde condition s’écrit \(12k \equiv 6 \pmod{18}\). En divisant tout par \(6\), elle équivaut à \(2k \equiv 1 \pmod 3\), donc \(k \equiv 2 \pmod 3\). Ainsi \(x = 29 + 36j\). Vérification : \(29 = 2 \times 12 + 5\) et \(29 = 18 + 11\). Les solutions sont les \(x \equiv 29 \pmod{36}\), avec \(36 = 12 \vee 18\).
2. Une solution vérifierait \(x \equiv 5\) et \(x \equiv 8\) modulo \(6\), puisque \(6\) divise \(12\) et \(18\). Or \(5\) et \(8 \equiv 2\) diffèrent modulo \(6\). Le système n’a donc aucune solution.
3. D’après la proposition du cours, le système est compatible si et seulement si \(6\) divise \(b – 5\). C’est le cas exactement lorsque \(b \equiv 5 \pmod 6\).

Corrigé de l’exercice 9 – Les deux derniers chiffres de 3 puissance 2026

Idée clé : comme \(100 = 4 \times 25\) avec \(4 \wedge 25 = 1\), on calcule séparément modulo \(4\) et modulo \(25\), puis on recolle.

1. On a \(3 \equiv -1 \pmod 4\) et \(2026\) est pair. Donc \(3^{2026} \equiv 1 \pmod 4\).
2. On a \(3 \wedge 25 = 1\) et \(\varphi(25) = 20\). Le théorème d’Euler donne \(3^{20} \equiv 1 \pmod{25}\). Or \(2026 = 101 \times 20 + 6\). Donc \(3^{2026} \equiv 3^6 = 729 = 29 \times 25 + 4\). Ainsi \(3^{2026} \equiv 4 \pmod{25}\).
3. On cherche \(x\) avec \(x \equiv 1 \pmod 4\) et \(x \equiv 4 \pmod{25}\). Parmi \(4, 29, 54, 79\), seul \(29\) vaut \(1\) modulo \(4\). Par le théorème chinois, \(3^{2026} \equiv 29 \pmod{100}\). Les deux derniers chiffres sont \(2\) et \(9\).
4. Modulo \(100\), on a \(3^5 = 243 \equiv 43\), puis \(3^{10} \equiv 43^2 = 1\,849 \equiv 49\). Enfin \(3^{20} \equiv 49^2 = 2\,401 \equiv 1\). Comme \(2026 = 101 \times 20 + 6\), on retrouve \(3^{2026} \equiv 3^6 = 729 \equiv 29\). Le résultat est confirmé.

Corrigé de l’exercice 10 – Un morphisme non surjectif vers un produit

Idée clé : le noyau est l’intersection \(6\mathbb{Z} \cap 10\mathbb{Z}\), et le passage au quotient fournit une injection dont on compte l’image.

1. Chaque composante est la surjection canonique, qui est un morphisme d’anneaux. Donc \(f\) est un morphisme d’anneaux. De plus, \(f(k) = (0, 0)\) si et seulement si \(6 \mid k\) et \(10 \mid k\). Ainsi \(\ker f = 6\mathbb{Z} \cap 10\mathbb{Z} = 30\mathbb{Z}\).
2. Par passage au quotient, \(f\) induit un morphisme injectif de \(\mathbb{Z}/30\mathbb{Z}\) dans le produit. Son image est celle de \(f\). L’image a donc \(30\) éléments, alors que le produit en a \(60\) : \(f\) n’est pas surjectif. Ce n’est pas une contradiction, car \(6 \wedge 10 = 2 \neq 1\).
3. D’abord, \(k \bmod 6\) et \(k \bmod 10\) ont tous deux la parité de \(k\). L’image est donc incluse dans l’ensemble \(E\) des couples de même parité. Ensuite, \(E\) contient \(3 \times 5\) couples pairs et \(3 \times 5\) couples impairs, soit \(30\) éléments. Par égalité des cardinaux, l’image de \(f\) est exactement \(E\). La figure de l’énoncé montre ce damier.

Corrigé de l’exercice 11 – Générateurs d’idéaux de R[X]

Idée clé : dans \(\mathbb{R}[X]\), une somme d’idéaux est engendrée par le PGCD et une intersection par le PPCM ; un idéal défini par des annulations est un noyau.

1. On a \(X^3 – 1 = (X – 1)(X^2 + X + 1)\) et \(X^2 – 1 = (X – 1)(X + 1)\). Le facteur \(X^2 + X + 1\) n’a pas de racine réelle et ne s’annule pas en \(-1\). Donc le PGCD vaut \(X – 1\). Ainsi \(I_1 = (X – 1)\,\mathbb{R}[X]\).
2. Le PPCM unitaire vaut \((X – 1)(X + 1)(X^2 + X + 1) = (X^3 – 1)(X + 1)\). Ainsi \(I_2\) est engendré par \(X^4 + X^3 – X – 1\).
3. L’application \(P \mapsto (P(1), P^{\prime}(1))\) est linéaire. De plus, si \(P \in I_3\) et \(A \in \mathbb{R}[X]\), alors \((AP)^{\prime}(1) = A^{\prime}(1)P(1) + A(1)P^{\prime}(1) = 0\). Donc \(I_3\) est un idéal. Or \(1\) est racine au moins double de \(P\) si et seulement si \((X – 1)^2\) divise \(P\). Ainsi \(I_3 = (X – 1)^2\,\mathbb{R}[X]\).
4. L’ensemble \(I_4\) est le noyau du morphisme \(P \mapsto P(\mathrm{i})\) de \(\mathbb{R}[X]\) dans \(\mathbb{C}\), donc un idéal. Si \(P\) est réel et \(P(\mathrm{i}) = 0\), alors \(P(-\mathrm{i}) = \overline{P(\mathrm{i})} = 0\). Donc \(X^2 + 1\) divise \(P\). Réciproquement, \(X^2 + 1\) s’annule en \(\mathrm{i}\). Ainsi \(I_4 = (X^2 + 1)\,\mathbb{R}[X]\).

Corrigé de l’exercice 12 – Équation linéaire modulo 40

Idée clé : on divise l’équation par \(d = 15 \wedge 40 = 5\), puis on inverse le nouveau coefficient.

1. L’équation équivaut à \(40 \mid 15x – 25\), soit \(8 \mid 3x – 5\). Or \(3 \times 3 = 9 \equiv 1 \pmod 8\). Donc \(x \equiv 15 \equiv 7 \pmod 8\). Vérification : \(15 \times 7 = 105 = 2 \times 40 + 25\). Les solutions forment les cinq classes \(\bar{7}, \overline{15}, \overline{23}, \overline{31}, \overline{39}\) modulo \(40\).
2. Si \(15x \equiv 22 \pmod{40}\), alors \(22 = 15x – 40k\) serait multiple de \(5\). C’est faux, donc il n’y a aucune solution.
3. Si \(x\) est solution, \(b = ax – nk\) est multiple de \(d\). Réciproquement, supposons \(d \mid b\) et posons \(a = da^{\prime}\), \(n = dn^{\prime}\), \(b = db^{\prime}\). L’équation équivaut à \(a^{\prime}x \equiv b^{\prime} \pmod{n^{\prime}}\), avec \(a^{\prime} \wedge n^{\prime} = 1\). Elle a donc une unique solution \(x_0\) modulo \(n^{\prime}\). Les solutions modulo \(n\) sont \(x_0 + jn^{\prime}\) pour \(0 \leqslant j < d\), soit \(d\) classes.

Corrigé de l’exercice 13 – Racines carrées de 1 dans F_p et théorème de Wilson

Idée clé : dans le produit de tous les inversibles, chaque élément se simplifie avec son inverse, sauf ceux qui sont leur propre inverse.

1. L’équation s’écrit \((x – \bar{1})(x + \bar{1}) = \bar{0}\). Or \(\mathbb{F}_p\) est un corps, donc intègre. Ainsi \(x = \bar{1}\) ou \(x = -\bar{1}\), et ces deux valeurs sont distinctes car \(p \neq 2\). Les seules racines carrées de \(\bar{1}\) sont \(\pm \bar{1}\).
2. Un élément est son propre inverse si et seulement si \(x^2 = \bar{1}\), donc si \(x = \pm \bar{1}\). Les \(p – 3\) autres éléments de \(\mathbb{F}_p^\times\) s’apparient chacun avec son inverse, et chaque paire apporte un facteur \(\bar{1}\). Il reste donc, dans le produit total, \(\bar{1} \times (-\bar{1}) = -\bar{1}\). Ainsi \((p – 1)! \equiv -1 \pmod p\).
3. On a \(10! = 3\,628\,800\) et \(11 \times 329\,891 = 3\,628\,801\). Donc \(10! \equiv -1 \pmod{11}\).
4. Si \(n = ab\) avec \(1 < a < b < n\), alors \(a\) et \(b\) sont deux facteurs distincts de \((n – 1)!\), donc \(n \mid (n – 1)!\). Sinon, \(n = p^2\) avec \(p\) premier, et \(p \geqslant 3\) car \(n \geqslant 6\). Alors \(p < 2p < p^2\), donc \(p\) et \(2p\) figurent dans \((n – 1)!\), et \(2p^2\) divise ce produit. Dans tous les cas, \((n – 1)! \equiv 0 \pmod n\).

Corrigé de l’exercice 14 – Divisibilité dans les entiers de Gauss

Idée clé : la norme \(N\) est multiplicative et à valeurs entières, ce qui transforme une divisibilité dans \(\mathbb{Z}[\mathrm{i}]\) en divisibilité dans \(\mathbb{N}\).

1. L’ensemble contient \(1\), est stable par différence et par produit, car \((a + b\mathrm{i})(c + d\mathrm{i}) = (ac – bd) + (ad + bc)\mathrm{i}\). C’est donc un sous-anneau de \(\mathbb{C}\), intègre comme \(\mathbb{C}\). Enfin, \(N(zw) = |zw|^2 = |z|^2|w|^2\). La norme est multiplicative.
2. Si \(zw = 1\), alors \(N(z)N(w) = 1\) avec des entiers naturels, donc \(N(z) = 1\). Réciproquement, si \(N(z) = z\bar{z} = 1\), alors \(\bar{z} \in \mathbb{Z}[\mathrm{i}]\) est un inverse. Enfin, \(a^2 + b^2 = 1\) impose \((a, b) \in \{(\pm 1, 0), (0, \pm 1)\}\). Les inversibles sont \(1, -1, \mathrm{i}, -\mathrm{i}\).
3. On a \((1 + \mathrm{i})^2 = 2\mathrm{i}\), donc \(2 = -\mathrm{i}(1 + \mathrm{i})^2\) avec \(-\mathrm{i}\) inversible. Ainsi \(2\) et \((1 + \mathrm{i})^2\) sont associés. Si \(1 + \mathrm{i}\) divisait \(3\), alors \(N(1 + \mathrm{i}) = 2\) diviserait \(N(3) = 9\). C’est faux, donc \(1 + \mathrm{i}\) ne divise pas \(3\).

Corrigé de l’exercice 15 – Antécédents de 12 par l’indicatrice d’Euler

Idée clé : les facteurs premiers possibles de \(n\) sont limités par la condition \(p – 1 \mid 12\), et l’on examine ensuite chaque cas.

1. Écrivons \(n = p^\alpha m\) avec \(p \nmid m\). Alors \(\varphi(n) = p^{\alpha – 1}(p – 1)\varphi(m)\). Donc \(p – 1\) divise \(\varphi(n)\).
2. Si \(n\) a un facteur premier impair \(p\), alors \(p – 1\), pair, divise \(\varphi(n)\). Sinon \(n = 2^\alpha\) avec \(\alpha \geqslant 2\), et \(\varphi(n) = 2^{\alpha – 1}\) est pair. Ainsi \(\varphi(n)\) est pair pour \(n \geqslant 3\).
3. Les premiers \(p\) avec \(p – 1 \mid 12\) sont \(2, 3, 5, 7, 13\). On distingue alors plusieurs cas.
   • Si \(13 \mid n\), alors \(169 \nmid n\) car \(\varphi(169) = 156\), donc \(n = 13m\) avec \(\varphi(m) = 1\), soit \(n \in \{13, 26\}\).
   • Si \(7 \mid n\) et \(13 \nmid n\), alors \(n = 7m\) avec \(7 \nmid m\), car \(\varphi(49) = 42\), et \(\varphi(m) = 2\), soit \(m \in \{3, 4, 6\}\) et \(n \in \{21, 28, 42\}\).
   • Si \(5 \mid n\), alors \(n = 5m\) avec \(\varphi(m) = 3\), ce qui est impossible par la question 2 ; et \(25 \nmid n\) car \(\varphi(25) = 20\).
   • Reste le cas \(n = 2^a 3^b\). Il faut \(b \geqslant 1\), sinon \(\varphi(n)\) serait une puissance de \(2\). Si \(a = 0\), alors \(\varphi(n) = 2 \times 3^{b-1} \neq 12\). Si \(a \geqslant 1\), alors \(\varphi(n) = 2^a 3^{b-1} = 12\), d’où \(a = 2\), \(b = 2\) et \(n = 36\).

   Finalement, \(\varphi(n) = 12\) si et seulement si \(n \in \{13, 21, 26, 28, 36, 42\}\).

Corrigé de l’exercice 16 – Les idéaux de Z/12Z

Idée clé : l’image réciproque par \(\pi\) transporte les idéaux de \(\mathbb{Z}/12\mathbb{Z}\) vers ceux de \(\mathbb{Z}\) qui contiennent \(12\mathbb{Z}\).

1. L’image réciproque d’un sous-groupe par un morphisme de groupes est un sous-groupe. De plus, si \(k \in \pi^{-1}(J)\) et \(a \in \mathbb{Z}\), alors \(\pi(ak) = \pi(a)\pi(k) \in J\). Enfin, \(\pi^{-1}(J)\) contient \(\pi^{-1}(\{\bar{0}\}) = 12\mathbb{Z}\). C’est un idéal de \(\mathbb{Z}\) contenant \(12\mathbb{Z}\).
2. On a \(\pi^{-1}(J) = d\mathbb{Z}\) avec \(d \geqslant 1\), et \(12 \in d\mathbb{Z}\) donne \(d \mid 12\). Comme \(\pi\) est surjective, \(J = \pi(\pi^{-1}(J)) = \pi(d\mathbb{Z})\). Cet ensemble est formé des classes de \(0, d, 2d, \dots, 12 – d\). Ainsi \(J\) a \(12/d\) éléments.
3. On obtient un idéal par diviseur \(d \in \{1, 2, 3, 4, 6, 12\}\), de cardinaux respectifs \(12, 6, 4, 3, 2, 1\). L’idéal associé à \(d\) contient celui associé à \(d^{\prime}\) si et seulement si \(d \mid d^{\prime}\). Il y a donc six idéaux, ordonnés comme le montre la figure.

Pour approfondir

Corrigé de l’exercice 17 – Les huit idempotents de Z/60Z

Idée clé : par le théorème chinois, un idempotent de \(\mathbb{Z}/n\mathbb{Z}\) se lit comme un choix de \(0\) ou \(1\) modulo chaque \(p^\alpha\).

1. Si \(e^2 \equiv e \pmod{p^\alpha}\), alors \(p^\alpha \mid e(e – 1)\). Or \(e\) et \(e – 1\) sont premiers entre eux, donc \(p\) ne divise que l’un des deux. Par conséquent, \(p^\alpha\) divise \(e\) ou divise \(e – 1\). Les idempotents de \(\mathbb{Z}/p^\alpha\mathbb{Z}\) sont \(\bar{0}\) et \(\bar{1}\).
2. Écrivons \(n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}\). Le théorème chinois fournit un isomorphisme d’anneaux entre \(\mathbb{Z}/n\mathbb{Z}\) et le produit des \(\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}\). Or un isomorphisme d’anneaux conserve les idempotents. Dans le produit, un élément est idempotent si et seulement si chaque composante l’est. Il y a donc \(2^r\) idempotents.

Application au module 60

3. On a \(60 = 4 \times 3 \times 5\), donc \(r = 3\) et huit idempotents. On cherche d’abord les trois idempotents « élémentaires ». L’entier valant \(1\) modulo \(4\) et \(0\) modulo \(15\) est \(45\). L’entier valant \(1\) modulo \(3\) et \(0\) modulo \(20\) est \(40\). L’entier valant \(1\) modulo \(5\) et \(0\) modulo \(12\) est \(36\). Les autres sont des sommes, réduites modulo \(60\) : \(45 + 40 \equiv 25\), \(45 + 36 \equiv 21\), \(40 + 36 \equiv 16\) et \(45 + 40 + 36 \equiv 1\). Vérification : \(16^2 = 256 = 4 \times 60 + 16\) et \(21^2 = 441 = 7 \times 60 + 21\). Les idempotents sont \(\bar{0}, \bar{1}, \overline{16}, \overline{21}, \overline{25}, \overline{36}, \overline{40}, \overline{45}\).

Corrigé de l’exercice 18 – Le nombre de Carmichael 561

Idée clé : on applique le petit théorème de Fermat modulo chaque facteur premier, puis on recolle par le théorème chinois.

1. On a \(561 = 3 \times 187 = 3 \times 11 \times 17\). Donc \(\varphi(561) = 2 \times 10 \times 16 = 320\).
2. Soit \(a\) premier avec \(561\). Il est premier avec \(3\), \(11\) et \(17\). Par Fermat, \(a^2 \equiv 1 \pmod 3\), \(a^{10} \equiv 1 \pmod{11}\) et \(a^{16} \equiv 1 \pmod{17}\). Or \(560 = 2 \times 280 = 10 \times 56 = 16 \times 35\). Donc \(a^{560} – 1\) est divisible par \(3\), par \(11\) et par \(17\). Comme ces trois premiers sont distincts, leur produit divise aussi \(a^{560} – 1\). Ainsi \(a^{560} \equiv 1 \pmod{561}\).
3. Soit \(p \in \{3, 11, 17\}\). Si \(p \mid a\), alors \(a^{561} \equiv 0 \equiv a \pmod p\). Sinon, la question 2 donne \(a^{560} \equiv 1\), puis \(a^{561} \equiv a \pmod p\). On recolle à nouveau. Donc \(a^{561} \equiv a \pmod{561}\) pour tout entier \(a\). Ce résultat est surprenant : \(561\) n’est pas premier, mais il vérifie la conclusion du petit théorème de Fermat. Ainsi, ce test ne suffit pas à prouver la primalité.

Corrigé de l’exercice 19 – Problème – Racines carrées de -1 modulo n

Idée clé : l’ordre d’un élément divise le cardinal du groupe, et le théorème de Wilson fournit une racine carrée explicite de \(-1\).

1. On a \(\bar{x}^2 = -\bar{1} \neq \bar{1}\) car \(p\) est impair, et \(\bar{x}^4 = \bar{1}\). L’ordre de \(\bar{x}\) divise \(4\) sans diviser \(2\). Donc il vaut \(4\). D’après Lagrange, \(4\) divise le cardinal \(p – 1\) de \(\mathbb{F}_p^\times\). Ainsi \(p \equiv 1 \pmod 4\).
2. On regroupe \(k\) et \(p – k\) dans \((p – 1)!\), pour \(1 \leqslant k \leqslant \frac{p-1}{2}\). Comme \(p – k \equiv -k\), on obtient :
   \[(p – 1)! \equiv \prod_{k=1}^{(p-1)/2} \left(-k^2\right) = (-1)^{(p-1)/2}\, y^2 \pmod p.\]
   Or \(\frac{p-1}{2}\) est pair, puisque \(p \equiv 1 \pmod 4\). Par Wilson, \((p – 1)! \equiv -1\). Donc \(y^2 \equiv -1 \pmod p\).
3. Le polynôme \(X^2 + \bar{1}\) a au plus deux racines dans le corps \(\mathbb{F}_p\). Or \(\bar{y}\) et \(-\bar{y}\) sont racines, et elles sont distinctes car \(\bar{y} \neq \bar{0}\) et \(p\) est impair. Il y a exactement deux solutions modulo \(p\).

Calculs modulo 65 et modulo 39

4. Modulo \(5\), on a \(2^2 = 4 \equiv -1\). Modulo \(13\), on a \(5^2 = 25 \equiv -1\). Les solutions sont \(x \equiv \pm 2 \pmod 5\) et \(x \equiv \pm 5 \pmod{13}\).
5. Par le théorème chinois, \(x^2 \equiv -1 \pmod{65}\) équivaut à \(x^2 \equiv -1\) modulo \(5\) et modulo \(13\). On combine les deux choix de signe de chaque côté. Avec \(x \equiv 2 \pmod 5\) et \(x \equiv 5 \pmod{13}\), on écrit \(x = 5 + 13k\) et \(3k \equiv 2 \pmod 5\), soit \(k \equiv 4\) : \(x = 57\). Avec \(x \equiv 2 \pmod 5\) et \(x \equiv 8 \pmod{13}\), on trouve de même \(x = 47\). Les deux autres sont les opposés \(65 – 57 = 8\) et \(65 – 47 = 18\). Vérification : \(57^2 = 3\,249 = 50 \times 65 – 1\) et \(18^2 = 324 = 5 \times 65 – 1\). Les quatre solutions sont \(8, 18, 47, 57\).
6. Une solution modulo \(39\) serait solution modulo \(3\). Or \(3 \equiv 3 \pmod 4\), et la question 1 interdit alors toute solution modulo \(3\). On le vérifie aussi directement : les carrés modulo \(3\) sont \(0\) et \(1\), jamais \(2\). L’équation n’a pas de solution modulo \(39\).

La figure place les quatre solutions dans la grille des couples (reste modulo \(5\), reste modulo \(13\)).

Corrigé de l’exercice 20 – Problème – Un chiffrement RSA miniature

Idée clé : l’exposant \(ed\) vaut \(1\) modulo \(p – 1\) et modulo \(q – 1\), ce qui permet d’appliquer Fermat dans chaque facteur avant de recoller.

1. On a \(n = 11 \times 17 = 187\) et \(\varphi(n) = 10 \times 16 = 160 = 2^5 \times 5\). Comme \(7\) ne divise pas \(160\), on a \(n = 187\), \(\varphi(n) = 160\) et \(7 \wedge 160 = 1\).
2. On a \(160 = 22 \times 7 + 6\) et \(7 = 6 + 1\). Donc \(1 = 7 – 6 = 7 – (160 – 22 \times 7) = 23 \times 7 – 160\). Ainsi \(d = 23\), et en effet \(7 \times 23 = 161\).
3. On a \(ed = 161 = 1 + 16 \times 10\). Si \(p \mid m\), alors les deux membres sont nuls modulo \(p\). Sinon, Fermat donne \(m^{10} \equiv 1 \pmod{11}\), donc \(m^{161} = m \times (m^{10})^{16} \equiv m\). Dans tous les cas, \(m^{ed} \equiv m \pmod{11}\).
4. De même, \(161 = 1 + 10 \times 16\) et le raisonnement modulo \(17\) donne \(m^{ed} \equiv m \pmod{17}\). Comme \(11 \wedge 17 = 1\), le théorème chinois permet de conclure. Pour tout entier \(m\), on a \(m^{ed} \equiv m \pmod{187}\).

Chiffrement et déchiffrement du message 5

5. Modulo \(187\), on a \(5^2 = 25\), puis \(5^4 = 625 = 3 \times 187 + 64\). Ensuite \(5^7 = 5^4 \times 5^2 \times 5 \equiv 64 \times 125 = 8\,000\). Or \(8\,000 = 42 \times 187 + 146\). Le message chiffré est \(c = 146\).
6. Modulo \(11\), on a \(146 = 13 \times 11 + 3\) et \(23 \equiv 3 \pmod{10}\). Donc \(c^{23} \equiv 3^3 = 27 \equiv 5\). Modulo \(17\), on a \(146 = 8 \times 17 + 10\) et \(23 \equiv 7 \pmod{16}\). Puis \(10^2 = 100 \equiv -2\), \(10^4 \equiv 4\) et \(10^6 \equiv -8\). Ainsi \(10^7 \equiv -80 \equiv 5\). Dans les deux cas, on retrouve \(c^d \equiv 5\), ce qui confirme le déchiffrement.

Pour aller plus loin

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

Télécharger ou imprimer cette fiche «corrigé des exercices : Z/nZ, idéaux et théorème chinois en maths spé (MP)» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

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