Fiche de cours
Congruences dans $\mathbb{Z}$
Définition
Soit un entier $n$ supérieur à 2 et soient $a$ et $b$, deux entiers relatifs.
On dit que $a$ est congru à $b$ modulo $n$ si et seulement si $b-a$ est divisible par $n$.
On écrit $a\equiv b[n]$.
Propriétés
Soient $a$, $b$ et $c$ des entiers relatifs, $n$ et $p$ des entiers supérieurs ou égaux à 2 :
$a\equiv a[n].$
Si $a\equiv b[n]$ et $b\equiv c [n]$ alors $a \equiv c[n]$.
Si $a \equiv b[n]$ alors $a+c \equiv b+c[n]$.
Si $a \equiv b[n]$ alors $ac\equiv bc[n]$.
Si $a \equiv b[n]$ alors $a^p\equiv b^p[n]$.
Exemple
Trouver le reste de la division euclidienne de $200^{539}$ par 17
étape 1 : On pose la division euclidienne de 200 par 17.
$200= 11 \times 17 +13$
étape 2 : On utilise la définition de la congruence.
$200-13 = 11\times 17$ donc $200$ est congru à $13$ modulo $17$.
On note $200\equiv 13[17]$
étape 3 : Avec un peu d'astuce, et en remarquant que $539 = 269\times 2 +1$, on a :
$200^{539}= (200^2)^{269} \times 200$
On sait que $200\equiv 13[17]$ .
Or la congruence est compatible avec les puissa