Ressources · Terminale · Maths expertes (option Tle)

Congruences

Q: Que veut dire a ≡ b [n] ?

Que n divise a − b, autrement dit que a et b ont le même reste dans la division euclidienne par n. Par exemple 62 ≡ 2 [12], car 62 − 2 = 60 = 12 × 5 : 62 et 2 ont tous deux le reste 2.

Q: Peut-on simplifier une congruence comme une égalité ?

On peut ajouter, soustraire, multiplier et élever à une puissance des congruences de même module. En revanche, on ne divise pas : 4 × 3 ≡ 4 × 0 [12], mais 3 n’est pas congru à 0 modulo 12.

Q: Comment trouver le reste d’une très grande puissance ?

On réduit la base, on cherche la première puissance congrue à 1 (par exemple 2³ = 8 ≡ 1 [7]), puis on divise l’exposant par la longueur du cycle : 2¹⁰⁰ ≡ 2 [7], car 100 = 3 × 33 + 1.

Q: Pourquoi le critère de divisibilité par 9 fonctionne-t-il ?

Parce que 10 ≡ 1 [9] : toute puissance de 10 est congrue à 1, donc un entier est congru modulo 9 à la somme de ses chiffres. Pour 11, la congruence 10 ≡ −1 donne la somme alternée des chiffres.

Q: Comment montrer qu’une équation n’a pas de solution entière ?

On choisit un module n et on dresse le tableau des restes des deux membres. S’ils ne peuvent jamais avoir le même reste, il n’y a pas de solution : un carré n’est jamais congru à 2 modulo 3, donc x² = 3y + 2 est impossible.

Q: Comment résoudre une équation comme 3x ≡ 5 [8] ?

On cherche un inverse de 3 modulo 8 : 3 × 3 = 9 ≡ 1 [8]. En multipliant les deux membres par 3 : x ≡ 15 ≡ 7 [8]. Les solutions sont les entiers 7 + 8k, k entier relatif.

Congruences modulo n et restes, compatibilité avec l’addition, la multiplication et les puissances, restes de grandes puissances, critères de divisibilité démontrés (rappels du collège, 11, 7 et 13), tableaux de congruences, équations ax ≡ b [n] et inverse modulo n.

À propos de cette page

Ce cours de maths expertes de Terminale définit la congruence modulo n à partir de la division euclidienne, puis traite la compatibilité avec l’addition, la multiplication et les puissances, les restes de grandes puissances par les cycles, les critères de divisibilité du collège démontrés et complétés (8, 11), les tableaux de congruences et les équations ax ≡ b [n] avec l’inverse modulo n.

Congruence modulo n

Ce qu’il faut savoir

Rappel : division euclidienne. Pour tout entier relatif $a$ et tout entier naturel $n ⩾ 1$ , il existe un unique couple d’entiers $(q; r)$ tel que $a = n q + r$ et $0 ⩽ r < n$ ; $r$ est le reste, il vaut $0$ , $1$ , …, ou $n - 1$ .

Définition. Soit $n$ un entier naturel supérieur ou égal à $2$ , appelé module, et $a$ , $b$ deux entiers relatifs. On dit que $a$ est congru à $b$ modulo $n$ , et l’on note $a \equiv b [n]$ , lorsque $n$ divise $a - b$ : il existe un entier relatif $k$ tel que $a - b = k n$ , c’est-à-dire $a = b + k n$ .

Caractérisation par les restes. $a \equiv b [n]$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ . En particulier, un entier est congru à son reste : tout entier est congru modulo $n$ à un et un seul des entiers $0$ , $1$ , …, $n - 1$ . Et $a \equiv 0 [n]$ signifie que $n$ divise $a$ .

Règles de calcul. $a \equiv a [n]$ ; si $a \equiv b [n]$ , alors $b \equiv a [n]$ ; si $a \equiv b [n]$ et $b \equiv c [n]$ , alors $a \equiv c [n]$ (transitivité) : on enchaîne les congruences comme des égalités. Enfin, si $a \equiv b [n]$ et si $d ⩾ 2$ divise $n$ , alors $a \equiv b [d]$ .

En Python, pour $n ⩾ 2$ , a % n renvoie le reste de $a$ dans la division par $n$ , même si $a$ est négatif, et (a - b) % n == 0 teste si $a \equiv b [n]$ .

Exemples

Avec la définition. $47 \equiv 5 [7]$ , car $47 - 5 = 42 = 7 \times 6$ . $- 23 \equiv 4 [9]$ , car $- 23 - 4 = - 27 = 9 \times (- 3)$ . En revanche, $50 ≢ 5 [7]$ : la différence $45$ est strictement comprise entre $42$ et $49$ , deux multiples consécutifs de $7$ .

Démonstration de la caractérisation. Écrivons $a = n q + r$ et $b = n q' + r'$ avec $0 ⩽ r < n$ et $0 ⩽ r' < n$ . Alors $a - b = n (q - q') + (r - r')$ . Si $r = r'$ , $a - b = n (q - q')$ est un multiple de $n$ . Réciproquement, si $n$ divise $a - b$ , il divise la combinaison $(a - b) - n (q - q') = r - r'$ ; or $- n < r - r' < n$ , et le seul multiple de $n$ strictement compris entre $- n$ et $n$ est $0$ : $r = r'$ .

Reste d’un entier négatif. $- 23 = 9 \times (- 3) + 4$ avec $0 ⩽ 4 < 9$ : le reste de $- 23$ par $9$ vaut $4$ , ce qui confirme $- 23 \equiv 4 [9]$ . En Python, -23 % 9 renvoie $4$ .

Choisir un représentant commode. Modulo $7$ : $13 \equiv 6 \equiv - 1$ . Modulo $12$ : $35 \equiv 11 \equiv - 1$ et $- 5 \equiv 7$ . Un petit représentant, même négatif, simplifie tous les calculs qui suivent.

Changer de module. Si $a \equiv 17 [20]$ , alors $20$ divise $a - 17$ , donc $5$ aussi : $a \equiv 17 [5]$ . Comme $17 \equiv 2 [5]$ , le reste de $a$ par $5$ vaut $2$ .

Réflexe — Pour prouver $a \equiv b [n]$ , j’écris $a - b = k n$ avec $k$ entier. Pour trouver le reste de $a$ modulo $n$ , j’ajoute ou je retire des multiples de $n$ jusqu’à tomber entre $0$ et $n - 1$ .

Attention — $a \equiv b [n]$ ne dit pas que $b$ est le reste : $47 \equiv 26 [7]$ est vrai ( $47 - 26 = 21$ ), mais le reste de $47$ par $7$ vaut $5$ . Et un reste n’est jamais négatif : on écrit $- 4 \equiv 7 [11]$ , jamais « le reste vaut $- 4$ ».

1 / 6

Compatibilité avec les opérations

Ce qu’il faut savoir

Compatibilité avec les opérations. Soit $n ⩾ 2$ et $a$ , $b$ , $c$ , $d$ des entiers relatifs tels que $a \equiv b [n]$ et $c \equiv d [n]$ . Alors :

$a + c \equiv b + d [n]$ et $a - c \equiv b - d [n]$ ;
$a c \equiv b d [n]$ ; en particulier $k a \equiv k b [n]$ pour tout entier $k$ ;
$a^{m} \equiv b^{m} [n]$ pour tout entier naturel $m$ .

Conséquence pratique. Dans une expression faite de sommes, de différences, de produits et de puissances, on peut remplacer chaque nombre par un entier qui lui est congru (son reste, ou un représentant négatif) : le résultat reste congru modulo $n$ .

Ce qui est interdit. Diviser : $k a \equiv k b [n]$ n’entraîne pas $a \equiv b [n]$ . Prendre une racine : $a^{2} \equiv b^{2} [n]$ n’entraîne pas $a \equiv b [n]$ . Réduire un exposant modulo $n$ : seule la base se réduit.

Exemples

Démonstration (classique ; le programme ne l’impose pas). Il existe des entiers $k$ et $k'$ tels que $a - b = k n$ et $c - d = k' n$ . Somme : $(a + c) - (b + d) = (k + k') n$ . Produit : $a c - b d$ $= a c - b c + b c - b d$ $= c (a - b) + b (c - d)$ $= n (c k + b k')$ , et $c k + b k'$ est un entier. Puissances, par récurrence sur $m$ : $a^{0} = b^{0} = 1$ , et si $a^{m} \equiv b^{m} [n]$ , le produit de cette congruence par $a \equiv b [n]$ donne $a^{m + 1} \equiv b^{m + 1} [n]$ .

Le reste d’un produit sans le calculer. $38 \equiv 3 [5]$ et $27 \equiv 2 [5]$ , donc $38 \times 27 \equiv 3 \times 2 = 6 \equiv 1 [5]$ . Contrôle : $38 \times 27 = 1 026 = 5 \times 205 + 1$ .

Une expression en $n$ . Si $n \equiv 3 [7]$ , alors $n^{2} + 2 n + 5$ $\equiv 9 + 6 + 5$ $= 20 \equiv 6 [7]$ : le reste de $n^{2} + 2 n + 5$ par $7$ vaut $6$ .

Une divisibilité pour tout $n$ . Pour tout entier naturel $n$ , $5^{n} - 1$ est divisible par $4$ : $5 \equiv 1 [4]$ , donc $5^{n} \equiv 1^{n} = 1 [4]$ , et $5^{n} - 1 \equiv 0 [4]$ .

Trois contre-exemples. $6 \times 2 \equiv 6 \times 7 [15]$ car $42 - 12 = 30$ , mais $2 ≢ 7 [15]$ . $3^{2} \equiv 4^{2} [7]$ car $9$ et $16$ ont tous deux le reste $2$ , mais $3 ≢ 4 [7]$ . $5 \equiv 0 [5]$ , mais $2^{5} = 32 \equiv 2 [5]$ alors que $2^{0} = 1$ .

Réflexe — Avant de calculer, je remplace chaque nombre par son reste ou par un petit représentant ( $- 1$ , $- 2$ …), je calcule, puis je ramène le résultat entre $0$ et $n - 1$ . À chaque ligne, j’écris le module.

Attention — Pour « simplifier » $k a \equiv k b [n]$ , il faut une justification : on ne divise jamais une congruence comme une égalité. On verra au dernier cas qu’on peut multiplier par un inverse de $k$ modulo $n$ , quand il existe.

2 / 6

Restes des puissances

Ce qu’il faut savoir

Propriété des cycles. Soit $a$ un entier et $n ⩾ 2$ . S’il existe un entier $k ⩾ 1$ tel que $a^{k} \equiv 1 [n]$ , alors, pour tout entier naturel $m$ de division euclidienne $m = k q + r$ par $k$ ( $0 ⩽ r < k$ ) : $a^{m} \equiv a^{r} [n] .$ Les restes des puissances de $a$ se répètent avec la période $k$ .

Méthode. 1. Je réduis la base modulo $n$ . 2. Je calcule les restes de $a^{1}$ , $a^{2}$ , $a^{3}$ … jusqu’au premier égal à $1$ : son exposant $k$ est la longueur du cycle. 3. Je divise l’exposant $m$ par $k$ . 4. Je conclus : $a^{m} \equiv a^{r} [n]$ .

Base congrue à $- 1$ . Si $a \equiv - 1 [n]$ , alors $a^{m} \equiv (- 1)^{m} [n]$ : le reste vaut $1$ si $m$ est pair, $n - 1$ si $m$ est impair.

Derniers chiffres. Le chiffre des unités d’un entier naturel est son reste modulo $10$ ; le nombre formé par ses deux derniers chiffres est son reste modulo $100$ .

Exemples

Démonstration de la propriété. $a^{m} = a^{k q + r} = (a^{k})^{q} \times a^{r}$ . Comme $a^{k} \equiv 1 [n]$ , la compatibilité avec les puissances donne $(a^{k})^{q} \equiv 1^{q} = 1 [n]$ , puis la compatibilité avec le produit $a^{m} \equiv 1 \times a^{r} = a^{r} [n]$ .

Le cycle de $3$ modulo $7$ . On passe d’une colonne à la suivante en multipliant le reste par $3$ ( $6 \times 3 = 18 \equiv 4$ , puis $4 \times 3 = 12 \equiv 5$ …) :

$m$	$1$	$2$	$3$	$4$	$5$	$6$
$3^{m}$ modulo $7$	$3$	$2$	$6$	$4$	$5$	$1$

Le premier reste égal à $1$ est celui de $3^{6}$ : le cycle a pour longueur $6$ .

Réponse rédigée : reste de $7^{2026}$ modulo $5$ . $7 \equiv 2 [5]$ , donc $7^{2026} \equiv 2^{2026} [5]$ . Or $2^{4} = 16 \equiv 1 [5]$ et $2 026 = 4 \times 506 + 2$ , donc $2^{2026}$ $= (2^{4})^{506} \times 2^{2}$ $\equiv 1 \times 4 = 4 [5]$ . Le reste de $7^{2026}$ dans la division par $5$ est $4$ .

Une base congrue à $- 1$ . $8 \equiv - 1 [9]$ , donc $8^{75} \equiv (- 1)^{75} = - 1 \equiv 8 [9]$ , car $75$ est impair.

Chiffre des unités de $3^{2027}$ . $3^{4} = 81 \equiv 1 [10]$ et $2 027 = 4 \times 506 + 3$ , donc $3^{2027} \equiv 3^{3} = 27 \equiv 7 [10]$ : $3^{2027}$ se termine par $7$ .

Réflexe — Je ne calcule jamais la puissance : je cherche la première puissance congrue à $1$ (ou à $- 1$ , qui donne $1$ une fois élevée au carré), je divise l’exposant par la longueur du cycle et je garde le reste.

Attention — On réduit la base modulo $n$ , jamais l’exposant : $2^{12}$ n’est pas congru à $2^{2}$ modulo $10$ , car $4 096$ se termine par $6$ . Et si la base et le module ont un diviseur commun autre que $1$ , le reste $1$ n’apparaît jamais : modulo $12$ , les puissances de $2$ valent $2$ , $4$ , $8$ , $4$ , $8$ … On s’appuie alors sur la première répétition, $2^{4} \equiv 2^{2} [12]$ : pour $m ⩾ 2$ , $2^{m}$ est congru à $4$ si $m$ est pair, à $8$ si $m$ est impair.

3 / 6

Critères de divisibilité

Ce qu’il faut savoir

Rappels du collège. Un entier est divisible par $2$ , $5$ ou $10$ selon son chiffre des unités ; par $4$ lorsque le nombre formé par ses deux derniers chiffres est un multiple de $4$ ; par $3$ (ou par $9$ ) lorsque la somme de ses chiffres est un multiple de $3$ (ou de $9$ ). Les congruences démontrent ces critères et donnent davantage : le reste.

Le principe. Un entier naturel $N$ dont les chiffres sont, de droite à gauche, $a_{0}$ (unités), $a_{1}$ (dizaines), …, $a_{p}$ s’écrit $N = a_{p} \times 10^{p} + \dots + a_{1} \times 10 + a_{0}$ . On réduit $10$ , ou une puissance de $10$ , modulo le diviseur :

Diviseur	Clé	$N$ a le même reste que…
$2$ , $5$ , $10$	$10 \equiv 0$	son chiffre des unités
$4$ , $25$	$100 \equiv 0$	le nombre formé par ses deux derniers chiffres
$8$	$1 000 \equiv 0$	le nombre formé par ses trois derniers chiffres
$3$ , $9$	$10 \equiv 1$	la somme de ses chiffres
$11$	$10 \equiv - 1$	la somme alternée $a_{0} - a_{1} + a_{2} - \dots$ , en partant des unités
$7$ , $11$ , $13$	$1 000 \equiv - 1$	la somme alternée de ses tranches de trois chiffres, en partant de la droite (car $1 001 = 7 \times 11 \times 13$ )

Exemples

Démonstration pour $9$ et $3$ . $10 \equiv 1 [9]$ , donc $10^{k} \equiv 1^{k} = 1 [9]$ pour tout entier naturel $k$ , et $a_{k} \times 10^{k} \equiv a_{k} [9]$ . En ajoutant ces congruences : $N \equiv a_{p} + \dots + a_{1} + a_{0} [9]$ . Le même calcul vaut modulo $3$ , car $10 \equiv 1 [3]$ . Un entier et la somme de ses chiffres ayant le même reste, l’un est divisible par $9$ si et seulement si l’autre l’est.

Démonstration pour $4$ et $25$ . $100 = 4 \times 25$ , donc $100 \equiv 0$ modulo $4$ et modulo $25$ , et pour $k ⩾ 2$ , $10^{k} = 100 \times 10^{k - 2} \equiv 0$ . Il reste $N \equiv 10 a_{1} + a_{0}$ .

Démonstration pour $11$ . $10 \equiv - 1 [11]$ donne $10^{k} \equiv (- 1)^{k} [11]$ : les chiffres de rang pair ( $a_{0}$ , $a_{2}$ …) sont comptés avec le signe $+$ , ceux de rang impair avec le signe $-$ .

Des restes en une ligne. $58 214$ : $5 + 8 + 2 + 1 + 4 = 20$ et $20 \equiv 2 [9]$ , donc $58 214 \equiv 2 [9]$ . $8 305$ : $5 - 0 + 3 - 8 = 0$ , donc $8 305$ est divisible par $11$ ( $8 305 = 11 \times 755$ ). $6 172$ : $2 - 7 + 1 - 6 = - 10 \equiv 1 [11]$ . $31 716$ : $16$ est un multiple de $4$ , donc $31 716$ aussi ; $716 = 8 \times 89 + 4$ , donc $31 716 \equiv 4 [8]$ .

Réflexe — J’écris $N$ avec les puissances de $10$ et je réduis $10$ modulo le diviseur : le critère et le reste apparaissent seuls. Pour $11$ , je pars toujours du chiffre des unités, compté avec le signe $+$ .

Attention — Pour $11$ , partir de la gauche peut changer le signe : pour $6 172$ , $6 - 1 + 7 - 2 = 10$ donne un faux reste ( $10$ au lieu de $1$ ). Et la somme des chiffres n’est pas le reste : $58 214$ a pour somme des chiffres $20$ , mais son reste modulo $9$ vaut $2$ .

4 / 6

Raisonner selon le reste : tableaux de congruences

Ce qu’il faut savoir

Le principe. Tout entier $x$ est congru modulo $n$ à un et un seul des restes $0$ , $1$ , …, $n - 1$ . Si $x \equiv r [n]$ , la compatibilité donne $P (x) \equiv P (r) [n]$ pour toute expression $P$ construite avec des sommes, des produits et des puissances d’exposant entier naturel. On étudie donc les $n$ cas possibles dans un tableau de congruences : une colonne par reste.

Ce qu’on en tire.

une divisibilité vraie pour tout entier : la ligne étudiée ne contient que des $0$ ;
les restes possibles d’un carré, d’un cube… ;
une condition sur le reste de $x$ : les colonnes où l’expression vaut $0$ ;
l’impossibilité d’une équation en nombres entiers : si, modulo un $n$ bien choisi, les deux membres ne peuvent jamais avoir le même reste, il n’y a pas de solution.

Représentants symétriques. On peut prendre comme colonnes n’importe quels représentants des $n$ restes, par exemple $- 2$ , $- 1$ , $0$ , $1$ , $2$ modulo $5$ : les calculs sont plus courts.

Exemples

Réponse rédigée : $2 n^{2} + n + 3$ n’est jamais divisible par $5$ . Soit $n$ un entier ; il est congru modulo $5$ à l’un des restes $0$ à $4$ , et par compatibilité :

$n$ modulo $5$	$0$	$1$	$2$	$3$	$4$
$2 n^{2} + n + 3$ modulo $5$	$3$	$1$	$3$	$4$	$4$

Par exemple, pour $n \equiv 3 [5]$ : $2 \times 9 + 3 + 3 = 24 \equiv 4 [5]$ . Le reste $0$ n’apparaît jamais : $2 n^{2} + n + 3$ n’est divisible par $5$ pour aucun entier $n$ .

Les carrés modulo $5$ . Avec les représentants $- 2$ , $- 1$ , $0$ , $1$ , $2$ : $(\pm 2)^{2} = 4$ , $(\pm 1)^{2} = 1$ et $0^{2} = 0$ . Un carré est congru à $0$ , $1$ ou $4$ modulo $5$ , jamais à $2$ ni à $3$ .

Une équation sans solution. L’équation $x^{2} - 5 y^{2} = 3$ , d’inconnues $x$ et $y$ entières, n’a pas de solution. En effet, si $(x; y)$ était solution, on aurait $x^{2} = 5 y^{2} + 3 \equiv 3 [5]$ , ce qui est impossible pour un carré.

Une condition sur le reste. $n^{2} + 1$ est divisible par $5$ si et seulement si $n^{2} \equiv - 1 \equiv 4 [5]$ , c’est-à-dire, d’après les carrés modulo $5$ , si et seulement si $n \equiv 2$ ou $n \equiv 3 [5]$ .

Réflexe — Quand l’énoncé dit « pour tout entier $n$ » et parle d’un diviseur, je dresse le tableau de congruences modulo ce diviseur. Pour une équation en entiers, je choisis un module où les carrés (ou les cubes) ont peu de restes : $3$ , $4$ , $5$ , $7$ , $8$ , $9$ .

Attention — Le tableau doit contenir tous les restes, sans en oublier. Et des restes compatibles ne prouvent pas qu’une équation a une solution : ils montrent seulement que ce module ne permet pas de conclure.

5 / 6

Équations ax ≡ b [n] et inverse modulo n

Ce qu’il faut savoir

Résoudre $a x \equiv b [n]$ (inconnue $x$ entière), c’est trouver tous les entiers qui la vérifient. Comme $a x$ ne dépend, modulo $n$ , que du reste de $x$ , la réponse se donne par classes : « $x \equiv c [n]$ », c’est-à-dire $x = c + k n$ avec $k \in ℤ$ , ou plusieurs classes, ou « aucune solution ».

Inverse modulo $n$ . Un entier $u$ est un inverse de $a$ modulo $n$ lorsque $a u \equiv 1 [n]$ . On le cherche en testant $u = 1$ , $2$ , …, $n - 1$ , ou bien en cherchant un multiple de $a$ parmi $n + 1$ , $2 n + 1$ , $3 n + 1$ … : si ce multiple vaut $a u$ , alors $u$ est un inverse. Si $pgcd (a; n) \neq 1$ , $a$ n’a pas d’inverse modulo $n$ . Si $pgcd (a; n) = 1$ , il en a un : c’est une conséquence du théorème de Bézout, qui permet aussi de le calculer pour un grand module (voir Théorèmes de Bézout et de Gauss).

Théorème. Si $u$ est un inverse de $a$ modulo $n$ , alors pour tout entier $x$ : $a x \equiv b [n] ⟺ x \equiv u b [n] .$ Il y a une seule classe de solutions.

Sans inverse. Si un entier $d ⩾ 2$ divise $a$ , $b$ et $n$ , l’équation équivaut à $\frac{a}{d} x \equiv \frac{b}{d} [\frac{n}{d}]$ . Si $d$ divise $a$ et $n$ mais pas $b$ , elle n’a aucune solution. Pour un petit module, le tableau des restes de $a x$ donne directement toutes les classes solutions.

Exemples

Démonstration du théorème. Si $a x \equiv b [n]$ , on multiplie par $u$ : $u a x \equiv u b [n]$ , et $u a \equiv 1 [n]$ donne $x \equiv u b [n]$ . Réciproquement, si $x \equiv u b [n]$ , alors $a x \equiv a u b \equiv 1 \times b = b [n]$ .

Démonstration : pas d’inverse si $pgcd (a; n) = d ⩾ 2$ . Si l’on avait $a u \equiv 1 [n]$ , il existerait un entier $k$ tel que $a u - k n = 1$ ; or $d$ divise $a$ et $n$ , donc il divise la combinaison linéaire $a u - k n$ , c’est-à-dire $1$ : impossible. De même, si $d$ divise $a$ et $n$ , toute solution de $a x \equiv b [n]$ donne $b = a x - k n$ , multiple de $d$ .

Réponse rédigée : $5 x \equiv 3 [12]$ . Cherchons un inverse de $5$ modulo $12$ : $5 \times 5 = 25 = 2 \times 12 + 1$ , donc $5$ est son propre inverse. En multipliant les deux membres par $5$ : $x \equiv 5 \times 3 = 15 \equiv 3 [12]$ . Les solutions sont les entiers $x = 3 + 12 k$ , $k \in ℤ$ . Vérification avec $x = 27$ : $5 \times 27 = 135 = 11 \times 12 + 3$ .

Un inverse par les multiples du module augmentés de 1. Inverse de $4$ modulo $9$ : parmi $10$ , $19$ , $28$ , le premier multiple de $4$ est $28 = 4 \times 7$ . Donc $4 \times 7 \equiv 1 [9]$ : l’inverse de $4$ modulo $9$ est $7$ .

Plusieurs classes, ou aucune. Tableau des restes de $6 x$ modulo $9$ :

$x$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$6 x$	$0$	$6$	$3$	$0$	$6$	$3$	$0$	$6$	$3$

$6 x \equiv 3 [9]$ a trois classes de solutions modulo $9$ , $x \equiv 2$ , $5$ ou $8$ , c’est-à-dire $x \equiv 2 [3]$ : c’est ce que donne aussi la simplification par $3$ , $2 x \equiv 1 [3]$ . En revanche, $6 x \equiv 1 [9]$ n’a aucune solution : $3$ divise $6$ et $9$ , mais pas $1$ .

Réflexe — Je cherche d’abord un inverse de $a$ (multiples de $n$ augmentés de $1$ ) ; s’il existe, je multiplie les deux membres par lui et je donne une classe. Sinon, je simplifie par le diviseur commun à $a$ , $b$ et $n$ , ou je conclus qu’il n’y a pas de solution. Je vérifie toujours sur un représentant.

Attention — La réponse est une classe, pas un entier : écrire « $x = 3$ » pour $5 x \equiv 3 [12]$ oublie $15$ , $- 9$ … Et diviser sans précaution fait perdre des solutions : $2 x \equiv 4 [6]$ a pour solutions $x \equiv 2$ et $x \equiv 5 [6]$ , pas seulement $x \equiv 2 [6]$ .

6 / 6

Pour aller plus loin

Petit théorème de Fermat. Si $p$ est un nombre premier qui ne divise pas l’entier $a$ , alors $a^{p - 1} \equiv 1 [p]$ (et, pour tout entier $a$ , $a^{p} \equiv a [p]$ ). Il fournit directement un exposant $k = p - 1$ tel que $a^{k} \equiv 1 [p]$ : par exemple $3^{6} \equiv 1 [7]$ , ce que le cycle des puissances de $3$ modulo $7$ confirme. Ce théorème, ses hypothèses et ses applications sont traités dans Nombres premiers.

Inverse modulo $n$ et théorème de Bézout. $a$ admet un inverse modulo $n$ si et seulement si $pgcd (a; n) = 1$ . Pour un grand module, on calcule cet inverse en remontant l’algorithme d’Euclide, et l’équation $a x \equiv b [n]$ équivaut à l’équation $a x - n y = b$ d’inconnues entières $x$ et $y$ : voir Théorèmes de Bézout et de Gauss.

Division euclidienne et PGCD. Les restes, la division d’un entier négatif et les combinaisons linéaires utilisés ici sont détaillés dans Divisibilité, division euclidienne et PGCD.

À retenir

$a \equiv b [n]$ : $n$ divise $a - b$ , ce qui revient à dire que $a$ et $b$ ont le même reste dans la division par $n$ ; tout entier est congru à son reste.
On additionne, on multiplie et on élève à une puissance des congruences de même module ; on ne divise pas et on ne réduit jamais l’exposant.
Si $a^{k} \equiv 1 [n]$ et $m = k q + r$ , alors $a^{m} \equiv a^{r} [n]$ ; si $a \equiv - 1 [n]$ , $a^{m} \equiv (- 1)^{m} [n]$ .
$10 \equiv 1 [9]$ , $10 \equiv - 1 [11]$ , $100 \equiv 0 [4]$ : un entier a le même reste que la somme de ses chiffres modulo $9$ , que leur somme alternée modulo $11$ .
Tableau de congruences : une colonne par reste ; il prouve une divisibilité pour tout entier, donne les restes des carrés et des cubes, montre qu’une équation n’a pas de solution entière.
Si $a u \equiv 1 [n]$ , alors $a x \equiv b [n]$ équivaut à $x \equiv u b [n]$ ; sans inverse, on simplifie par le diviseur commun ou il n’y a pas de solution.

Questions fréquentes

Que veut dire a ≡ b [n] ?

Que n divise a − b, autrement dit que a et b ont le même reste dans la division euclidienne par n. Par exemple 62 ≡ 2 [12], car 62 − 2 = 60 = 12 × 5 : 62 et 2 ont tous deux le reste 2.

Peut-on simplifier une congruence comme une égalité ?

On peut ajouter, soustraire, multiplier et élever à une puissance des congruences de même module. En revanche, on ne divise pas : 4 × 3 ≡ 4 × 0 [12], mais 3 n’est pas congru à 0 modulo 12.

Comment trouver le reste d’une très grande puissance ?

On réduit la base, on cherche la première puissance congrue à 1 (par exemple 2³ = 8 ≡ 1 [7]), puis on divise l’exposant par la longueur du cycle : 2¹⁰⁰ ≡ 2 [7], car 100 = 3 × 33 + 1.

Pourquoi le critère de divisibilité par 9 fonctionne-t-il ?

Parce que 10 ≡ 1 [9] : toute puissance de 10 est congrue à 1, donc un entier est congru modulo 9 à la somme de ses chiffres. Pour 11, la congruence 10 ≡ −1 donne la somme alternée des chiffres.

Comment montrer qu’une équation n’a pas de solution entière ?

On choisit un module n et on dresse le tableau des restes des deux membres. S’ils ne peuvent jamais avoir le même reste, il n’y a pas de solution : un carré n’est jamais congru à 2 modulo 3, donc x² = 3y + 2 est impossible.

Comment résoudre une équation comme 3x ≡ 5 [8] ?

On cherche un inverse de 3 modulo 8 : 3 × 3 = 9 ≡ 1 [8]. En multipliant les deux membres par 3 : x ≡ 15 ≡ 7 [8]. Les solutions sont les entiers 7 + 8k, k entier relatif.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs