Congruences

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 $aequiv b[n]$.

Propriétés 

 

Soient $a$, $b$ et $c$ des entiers relatifs, $n$ et $p$ des entiers supérieurs ou égaux à 2 :

$aequiv a[n].$

Si $aequiv b[n]$ et $bequiv 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 $acequiv bc[n]$.

Si $a equiv b[n]$ alors $a^pequiv 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 = 11times 17$ donc $200$ est congru à $13$ modulo $17$.

On note $200equiv 13[17]$

étape 3 : Avec un peu d’astuce, et en remarquant que $539 = 269times 2 +1$, on a :

$200^{539}= (200^2)^{269} times 200$

On sait que $200equiv 13[17]$ .

Or la congruence est compatible avec les puissances. Ainsi :

$200^2equiv 13^2[17]$

$200^2equiv 169 [17]$

On donne la division euclidienne de $169$ par $17$ : $169 = 9times 17 +16$. Ainsi :

$200^2 equiv 16 [17]$

Ou encore $200^2 equiv (-1) [17]$.

étape 4 : On utilise les résultats précédents et on essaie d’aboutir à une congruence positive.

On a : $200^2 equiv (-1) [17]$ et $539 = 2 times 269 +1$.

Ainsi $200^{539}=(200^2)^{269}times 200$ et en utilisant les résultats précédents :

$200^{539} equiv(-1)^{269} times 13 [17]$

$200^{539} equiv(-1) times 13 [17]$

$200^{539} equiv -13 [17]$

$200^{539} equiv 4 [17]$

Conclusion : Le reste de la division euclidienne de $200^{539}$ par 17 vaut 4

Congruences - Exercice 1

Exercice

 

Trouver le reste de la division euclidienne par 17 de (200^{539}).

 

Étape 1 : On pose la division euclidienne de 200 par 17.

Étape 2 : On utilise la définition de la congruence pour trouver une première congruence.

Étape 3 : On utilise les propriétés de la congruence pour l’écrire plus simplement.

Étape 4 : Avec un peu d’astuce, on réécrit (200^{539}) par ((200^2)^{269} times 200 [17]).

Étape 5 : On utilise les résultats précédents et on essaie d’aboutir à une congruence positive.