Chapitre 21 — raisonner non plus sur les entiers, mais sur leurs restes modulo $n$. Le langage de l'arithmétique modulaire, et comment s'en servir pour calculer.
Naviguez avec les flèches ← → du clavier, ou via le Sommaire.
Trouver le reste de très grandes puissances, et résoudre les équations $ax\equiv b\ [n]$.
Soient $n\in\mathbb{N}^*$ et $a,b\in\mathbb{Z}$. On dit que $a$ et $b$ sont congrus modulo $n$ lorsqu'ils ont le même reste dans la division euclidienne par $n$.
$n$ est le modulo. On ne regarde plus les nombres eux-mêmes, mais ce qu'ils laissent comme reste : c'est tout l'esprit de l'arithmétique modulaire.
Pour $n\in\mathbb{N}^*$ et $a,b\in\mathbb{Z}$ :
En pratique, c'est cette équivalence qu'on utilise : « être congru » se traduit par « diviser une différence ».
$a\equiv r\ [n]$ avec $0\leqslant r\lt n$ signifie exactement que $r$ est le reste de la division de $a$ par $n$.
$n\mid a \iff a\equiv 0\ [n].$ Être divisible par $n$, c'est être congru à $0$.
La condition $0\leqslant r\lt n$ est indispensable : $52\equiv 45\ [7]$ est vrai, mais $45$ n'est pas le reste de $52$ par $7$.
Tout entier est congru à l'un des restes $0,1,\dots,n-1$ modulo $n$ : cela partage $\mathbb{Z}$ en $n$ familles.
La classe de $r$ est $\widetilde{r}=\{x\in\mathbb{Z}\mid x\equiv r\ [n]\}$, et $\mathbb{Z}_n=\{\widetilde{0},\widetilde{1},\dots,\widetilde{n-1}\}$. Modulo $2$ : $\widetilde{0}$ = les pairs, $\widetilde{1}$ = les impairs.
La congruence modulo $n$ est réflexive, symétrique et transitive :
La transitivité est l'outil qui permet d'enchaîner : on remplace un nombre par un autre qui lui est congru, puis on poursuit le calcul.
Si $a\equiv c\ [n]$ et $b\equiv d\ [n]$, alors :
On peut multiplier, mais pas simplifier un facteur ! Contre-exemple :
… et pourtant $9\not\equiv 8\ [3]$.
Modulo $n$, un produit de deux nombres non nuls peut être nul : $2\times 4\equiv 0\ [8]$. On dit que $2$ et $4$ sont des diviseurs de $0$ modulo $8$.
Pour $p\geqslant 2$ : $\ a\equiv b\ [n]\implies a^{p}\equiv b^{p}\ [n].$ (Réciproque fausse : $5^2\equiv 4^2\ [3]$ mais $5\not\equiv 4\ [3]$.)
Pour les très grandes puissances, on cherche à se ramener à une congruence égale à $1$ ou $-1$ : alors $1^p=1$ et $(-1)^p=\pm1$ rendent le calcul immédiat.
Conclusion : $2022^{2021}\equiv 2\ [5]$, le reste vaut $\boxed{2}$.
$2021\equiv 1\ [5]$ donne aussitôt $2021^{2022}\equiv 1\ [5]$.
Impossible de diviser : on teste donc tous les restes modulo $n$ (disjonction). Pour $5x\equiv 1\ [3]$ :
D'où $5x\equiv 1\ [3]\iff x\equiv 2\ [3]$, soit $S=\{2+3k\mid k\in\mathbb{Z}\}$.
$10x+2\equiv 3\ [5]$ : le tableau donne toujours $10x+2\equiv 2\ [5]$, jamais $3$. L'équation n'a pas de solution.