Niveau : du facile au difficile (supérieur). Durée estimée : 90 min. 10 exercices avec corrections détaillées.
Rappel des notions clés
Une congruence $x \equiv a \pmod{n}$ signifie que $n$ divise $x - a$. Pour résoudre un système de deux congruences, tu écris la première sous la forme $x = a_1 + n_1 k$, tu la reportes dans la seconde, puis tu isoles $k$ en multipliant par un inverse modulo $n_2$ (un inverse de $a$ modulo $n$ est un entier $u$ tel que $au \equiv 1 \pmod{n}$). Exemple : si $x \equiv 3 \pmod{4}$ et $x \equiv 1 \pmod{5}$, alors $x = 3 + 4k$ et $4k \equiv -2 \equiv 3 \pmod{5}$ ; comme $4 \times 4 = 16 \equiv 1 \pmod{5}$, tu multiplies par $4$ : $k \equiv 12 \equiv 2 \pmod{5}$, donc $x = 11 + 20j$, soit $x \equiv 11 \pmod{20}$.
Les congruences s'additionnent et se multiplient membre à membre. Un inverse de $a$ modulo $n$ existe si et seulement si $a$ et $n$ sont premiers entre eux, c'est-à-dire de pgcd (plus grand commun diviseur) égal à $1$, ce qu'on note aussi $a \wedge n = 1$ en prépa. L'algorithme d'Euclide étendu le fournit à partir d'une relation de Bézout $au + nv = 1$.
Formules à retenir :
- Équation $ax \equiv b \pmod{n}$, avec $d = \operatorname{pgcd}(a, n)$ : elle a des solutions si et seulement si $d$ divise $b$. On divise alors $a$, $b$ et $n$ par $d$ : une solution unique modulo $n/d$, soit $d$ solutions modulo $n$.
- Théorème chinois : si $n_1, \dots, n_k$ sont premiers entre eux deux à deux (chaque paire a un pgcd égal à $1$) et $N = n_1 n_2 \cdots n_k$, le système $x \equiv a_i \pmod{n_i}$ a une solution unique modulo $N$ : $$x \equiv \sum_{i=1}^{k} a_i N_i y_i \pmod{N}$$ avec $N_i = N/n_i$ et $y_i$ un inverse de $N_i$ modulo $n_i$.
- Modules quelconques : $x \equiv a_1 \pmod{n_1}$ et $x \equiv a_2 \pmod{n_2}$ ont des solutions communes si et seulement si $a_1 \equiv a_2 \pmod{\operatorname{pgcd}(n_1, n_2)}$ ; elles sont alors uniques modulo $\operatorname{ppcm}(n_1, n_2)$, le plus petit commun multiple.
Piège classique : diviser une congruence comme une égalité. $2x \equiv 2 \pmod{6}$ n'entraîne pas $x \equiv 1 \pmod{6}$ : $x = 4$ convient aussi. Si tu simplifies par $2$, divise aussi le module : $x \equiv 1 \pmod{3}$.
Exercices : niveau facile
Exercice 1 : Soient $a, b, c, d$ des entiers et $n \geqslant 1$ un entier, avec $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$. Démontre que $a + c \equiv b + d \pmod{n}$ et que $ac \equiv bd \pmod{n}$.
Correction :
On revient à la définition : $a - b = nk$ et $c - d = n\ell$, avec $k, \ell \in \mathbb{Z}$.
Pour la somme, $(a + c) - (b + d) = n(k + \ell)$. Pour le produit, on fait apparaître les deux différences : $ac - bd = a(c - d) + d(a - b) = n(a\ell + dk)$.
Les deux différences sont des multiples de $n$, donc $a + c \equiv b + d \pmod{n}$ et $ac \equiv bd \pmod{n}$. En répétant le produit, tu obtiens aussi $a^p \equiv b^p \pmod{n}$ pour tout $p \in \mathbb{N}$.
Exercice 2 : Trouve un inverse de $5$ modulo $7$ avec l'algorithme d'Euclide étendu, puis résous dans $\mathbb{Z}$ l'équation $5x \equiv 3 \pmod{7}$.
Correction :
Méthode : une relation de Bézout entre $5$ et $7$ donne l'inverse, puis on multiplie l'équation par cet inverse.
$7 = 1 \times 5 + 2$ et $5 = 2 \times 2 + 1$. En remontant : $1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7$. Donc $3 \times 5 \equiv 1 \pmod{7}$ : $3$ est un inverse de $5$ modulo $7$.
En multipliant par $3$ : $x \equiv 9 \equiv 2 \pmod{7}$. Vérification : $5 \times 2 = 10 \equiv 3 \pmod{7}$. Les solutions sont les entiers $x = 2 + 7k$, avec $k \in \mathbb{Z}$.
Exercice 3 : Résous dans $\mathbb{Z}$ le système $$\begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 2 \pmod{5} \end{cases}$$
Correction :
Méthode : la substitution du rappel.
La première congruence donne $x = 1 + 3k$, et la seconde devient $3k \equiv 1 \pmod{5}$. Comme $3 \times 2 = 6 \equiv 1 \pmod{5}$, on multiplie par $2$ : $k \equiv 2 \pmod{5}$, donc $k = 2 + 5j$ et $x = 1 + 3(2 + 5j) = 7 + 15j$.
Vérification : $7 - 1 = 6$ et $7 - 2 = 5$. Les solutions sont les entiers $x \equiv 7 \pmod{15}$.
Exercices : niveau moyen
Exercice 4 : Résous dans $\mathbb{Z}$ : a) $6x \equiv 4 \pmod{10}$ ; b) $6x \equiv 5 \pmod{10}$.
Correction :
Méthode : calcule $d = \operatorname{pgcd}(6, 10) = 2$ et regarde s'il divise le second membre.
a) $2$ divise $4$. On divise tout par $2$, module compris : $3x \equiv 2 \pmod{5}$. Comme $2$ est un inverse de $3$ modulo $5$, $x \equiv 4 \pmod{5}$, ce qui donne deux solutions modulo $10$ : $x \equiv 4$ ou $x \equiv 9 \pmod{10}$. Vérification : $6 \times 4 = 24$ et $6 \times 9 = 54$ se terminent par $4$.
b) $6x - 5$ est impair, donc jamais multiple de $10$ : aucune solution.
Erreur à éviter : écrire $3x \equiv 2 \pmod{10}$ sans diviser le module. On trouve alors seulement $x \equiv 4 \pmod{10}$ et on perd la moitié des solutions.
Exercice 5 : Soient $n_1, n_2 \geqslant 2$ deux entiers premiers entre eux et $a_1, a_2$ deux entiers. On note $y_1$ un inverse de $n_2$ modulo $n_1$, et $y_2$ un inverse de $n_1$ modulo $n_2$.
a) Montre que $x_0 = a_1 n_2 y_1 + a_2 n_1 y_2$ vérifie $x_0 \equiv a_1 \pmod{n_1}$ et $x_0 \equiv a_2 \pmod{n_2}$.
b) Montre qu'un entier $x$ vérifie ces deux congruences si et seulement si $x \equiv x_0 \pmod{n_1 n_2}$.
Correction :
Méthode : réduire $x_0$ modulo chaque module, puis utiliser le lemme de Gauss.
a) Modulo $n_1$, $a_2 n_1 y_2 \equiv 0$ et $n_2 y_1 \equiv 1$, donc $x_0 \equiv a_1 \pmod{n_1}$. Le même calcul modulo $n_2$ donne $x_0 \equiv a_2 \pmod{n_2}$.
b) Si $x \equiv x_0 \pmod{n_1 n_2}$, la congruence reste vraie modulo $n_1$ et modulo $n_2$. Réciproquement, si $x$ est solution, $n_1$ et $n_2$ divisent $x - x_0$. On écrit $x - x_0 = n_1 q$ : $n_2$ divise $n_1 q$ et il est premier avec $n_1$, donc il divise $q$ (lemme de Gauss), et $n_1 n_2$ divise $x - x_0$.
Les solutions sont donc exactement les entiers $x \equiv x_0 \pmod{n_1 n_2}$ : c'est le théorème chinois pour deux modules.
Exercice 6 : Résous ce système avec la formule du théorème chinois, sans substitution : $$\begin{cases} x \equiv 1 \pmod{3} \\ x \equiv 2 \pmod{5} \\ x \equiv 3 \pmod{7} \end{cases}$$
Correction :
Méthode : calculer chaque $N_i$, puis son inverse $y_i$ modulo $n_i$.
Ici $N = 105$. $N_1 = 35 \equiv 2 \pmod{3}$ et $2 \times 2 \equiv 1 \pmod{3}$, donc $y_1 = 2$. $N_2 = 21 \equiv 1 \pmod{5}$ et $N_3 = 15 \equiv 1 \pmod{7}$, donc $y_2 = y_3 = 1$.
La formule donne $x \equiv 1 \times 35 \times 2 + 2 \times 21 \times 1 + 3 \times 15 \times 1 \equiv 157 \pmod{105}$, soit $x \equiv 52 \pmod{105}$. Vérification : $52 - 1 = 51 = 3 \times 17$, $52 - 2 = 50$ et $52 - 3 = 49 = 7 \times 7$.
Exercices : niveau difficile
Exercice 7 : On considère le système $$\begin{cases} x \equiv 7 \pmod{10} \\ x \equiv 3 \pmod{6} \end{cases}$$ Le théorème chinois s'applique-t-il tel quel ? Résous le système et donne le module de la solution.
Correction :
Méthode : tester la compatibilité, puis substituer.
Non, car $\operatorname{pgcd}(10, 6) = 2$. Mais $7 \equiv 3 \pmod{2}$ : le système est compatible.
Avec $x = 7 + 10k$, la seconde congruence donne $1 + 4k \equiv 3 \pmod{6}$, soit $4k \equiv 2 \pmod{6}$. On divise tout par $2$, module compris : $2k \equiv 1 \pmod{3}$, donc $k \equiv 2 \pmod{3}$ et $x = 7 + 10(2 + 3j) = 27 + 30j$.
Solution : $x \equiv 27 \pmod{30}$, avec $30 = \operatorname{ppcm}(10, 6)$ et non $60$. Vérification : $27 - 7 = 20$ et $27 - 3 = 24$.
Exercice 8 : Le système $$\begin{cases} x \equiv 5 \pmod{8} \\ x \equiv 2 \pmod{6} \end{cases}$$ a-t-il des solutions ? Justifie.
Correction :
Méthode : tester la compatibilité modulo $\operatorname{pgcd}(8, 6) = 2$.
$5 - 2 = 3$ n'est pas pair. Concrètement, la première congruence impose $x$ impair ($x = 5 + 8k$) et la seconde $x$ pair ($x = 2 + 6j$).
Le système n'a aucune solution. Erreur à éviter : lancer la formule du théorème chinois sans regarder les modules ; ici, $6$ n'a même pas d'inverse modulo $8$.
Exercice 9 : Dans le chiffrement RSA, on prend deux nombres premiers $p$ et $q$, on pose $n = pq$, et on choisit $e$ et $d$ tels que $ed \equiv 1 \pmod{(p-1)(q-1)}$. Un message $m$ se chiffre en $c \equiv m^e \pmod{n}$ et se déchiffre en calculant $c^d$ modulo $n$. On prend une clé d'école, bien trop petite pour un vrai usage : $p = 3$, $q = 11$, $e = 3$, $d = 7$.
a) Vérifie que $e$ et $d$ conviennent. b) Chiffre le message $m = 5$. c) Déchiffre le résultat : calcule $c^7$ modulo $3$ et modulo $11$, puis recolle avec le théorème chinois.
Correction :
Méthode : réduire la base avant d'élever à la puissance, puis recoller les deux restes.
a) $(p-1)(q-1) = 20$ et $ed = 21 \equiv 1 \pmod{20}$ : la clé est valable.
b) $5^3 = 125 = 3 \times 33 + 26$, donc $c = 26$.
c) Modulo $3$ : $26 \equiv -1$, donc $26^7 \equiv -1 \equiv 2$. Modulo $11$ : $26 \equiv 4$, $4^3 = 64 \equiv 9$, $4^6 \equiv 81 \equiv 4$, donc $4^7 \equiv 16 \equiv 5$. Il reste $m \equiv 2 \pmod{3}$ et $m \equiv 5 \pmod{11}$ : $5$ convient, et le théorème chinois assure que c'est la seule solution modulo $33$.
On retrouve $m = 5$. Travailler modulo $3$ et $11$ plutôt que modulo $33$ garde des nombres petits : c'est l'intérêt du théorème chinois ici.
Exercice 10 : Trois machines redémarrent à intervalles réguliers : A tous les 4 jours, B tous les 6 jours, C tous les 10 jours. Le jour $0$, A redémarre ; B a redémarré 2 jours plus tôt et C 4 jours plus tôt.
a) Au bout de combien de jours les trois redémarreront-elles ensemble pour la première fois ? b) Ensuite, tous les combien de jours cela se reproduira-t-il ? Justifie.
Correction :
Méthode : traduire chaque machine par une congruence, vérifier la compatibilité, puis substituer.
Les jours de redémarrage communs vérifient $x \equiv 0 \pmod{4}$, $x \equiv -2 \equiv 4 \pmod{6}$ et $x \equiv -4 \equiv 6 \pmod{10}$. Les modules ont deux à deux un pgcd égal à $2$, et les trois restes sont pairs : le système est compatible.
Avec $x = 6 + 10k$, la deuxième congruence donne $4k \equiv 4 \pmod{6}$, donc $2k \equiv 2 \pmod{3}$, $k \equiv 1 \pmod{3}$ et $x = 16 + 30j$. La première donne alors $2j \equiv 0 \pmod{4}$ : $j$ est pair et $x = 16 + 60i$.
a) Au bout de 16 jours. Vérification : $16 = 4 \times 4$, $16 + 2 = 18 = 3 \times 6$ et $16 + 4 = 20 = 2 \times 10$.
b) Tous les 60 jours, car $60 = \operatorname{ppcm}(4, 6, 10)$. Erreur à éviter : répondre $4 \times 6 \times 10 = 240$ ; le produit ne vaut que pour des modules premiers entre eux deux à deux.
Bilan et conseils
Ce qu'il faut retenir : avant tout calcul, regarde les pgcd. Pour $ax \equiv b \pmod{n}$, le pgcd $d$ de $a$ et $n$ dit s'il y a zéro ou $d$ solutions modulo $n$. Pour un système, les pgcd des modules disent si le théorème chinois s'applique tel quel ou s'il faut d'abord tester la compatibilité. Termine toujours en remplaçant ta solution dans chaque congruence.
En classe préparatoire, le théorème chinois est au programme de deuxième année MP et MPI, dans la partie sur les anneaux $\mathbb{Z}/n\mathbb{Z}$, avec application aux systèmes de congruences (programme officiel de mathématiques MP et MPI). Les exercices de cette page en sont la version calculatoire.
Sources
Ministère de l'Enseignement supérieur, de la Recherche et de l'Innovation, programme de mathématiques des classes préparatoires MP et MPI (annexe 1, 2021), partie « Structures algébriques usuelles », paragraphe « Anneaux $\mathbb{Z}/n\mathbb{Z}$ ».