Congruences

Définition :
soient a et b deux entiers relatifs et n entier naturel, n > 2

On dit que « a est congru à b modulo n » ou que « a et b sont congrus modulo n » si :
a et b ont le même reste dans la division euclidienne par n.
On note

3) Cette notion de congruence a déjà été rencontrée en trigonométrie, où l’on
 parle d’angles égaux modulo

De part sa définition, la relation de congruence présente trois propriétés évidentes :

a  a[n] (réflexivité)
Si a b[n] alors b a[n] (symétrie)
Si a b[n] et b c[n] (transivité)

Si on ajoute 3 à 5 alors la division euclidienne devient :

5 + 3 = 3 x 1 + 2 +3
8 = 3 x (1+1) + 2

Le reste de la division est inchangé donc 8 5[3]
Et l’on peut faire pareil avec le nombre trouvé.

Le résultat est également le même si au lieu d’ajouter 3, on enlève 3.
Comme tous ces nombres sont congrus à 5 modulo 3, par tansitivité,
ils sont congrus deux à deux modulo 3.

On peut remarquer que la différence entre deux de ces nombres est un multiple de 3.

Propriété :
soient a et b deux entiers relatifs et n entier naturel,  n > 2

a b [n] ⇔ n divise (a-b)

Sens direct :

Soient a et b congrus modulo n.
Il existe q et r entiers relatifs tels que : a = n x q + r avec 0 < r < n
b ayant le même reste, il existe q’ entier relatif tel que : b = n x q’ + r

D’où a - b = n x q - nq’ = n x (q - q’)
Donc n divise (a-b)

Sens réciproque :

Supposons que n divise (a-b). Alors il existe k entier relatif tel que : a-b = nk.

Soit r le reste dans la division euclidienne de a par n :
a = n x q + r avec 0 < r < n

Alors : b = a - nk = n x (q - k) + r
Avec 0 < r < n et q-k entier relatif
donc r est le reste dans la division euclidienne de b par n.

a et b ont le même reste donc : a b[n]

Conséquences  :

a0[n] ⇔ n divise a

ab[n] ⇔ n divise (a-b) ⇔ a - b 0[n]

Si ab[n] et d divise n alors ab[d]

Démonstration  :

donc n divise (a-b) Or par transitivité : si d divise n alors d divise (a-b).
Par conséquent : ab[d]

En trigonométrie où il est question d’angles égaux modulo , on parle de mesure principale,
comprise par exemple entre 0 et exclu.
Cette idée de choisir un représentant pour un ensemble de nombres égaux modulo est transposable au cas modulo n.

Propriété  :
soient a entier relatif et n entier naturel, n > 2

Si r est le reste dans la division euclidienne de a par n alors ar[n]

il existe q entier relatif tel que : a = n x q + r avec 0 < r < n
Donc n divise (a-r) et par conséquent a est congru à r modulo n.

Si a r[n] et 0 < r < n alors r est le reste dans la division euclidienne de a par n.

Démonstration :
Si a et r sont congrus modulo n alors n divise (a-r) et il existe donc k entier relatif tel que : a - r = n x k  

D’où a = n x k + r 
Or 0 < r < n
Donc il s’agit de la division euclidienne de a par n et r en est le reste.

Les restes possibles étant  : 0, 1, …, n-1 ;  peut donc être découpé en n classes, modulo n.

Ces classes forment une partition de .
C’est à dire que leur union est égale à , et que leurs intersections, deux à deux, sont vides.

Donc quel que soit a entier relatif :
* Soit a 0[2] , ce qui est équivalent à 2 divise a ( a pair )
* Soit a 1[2] , ce qui est équivalent à 2 ne divise pas a. ( a impair )

Les démonstrations des propriétés qui suivent peuvent faire l’objet d’un R.O.C.
Soient a, b, a’ et b’ quatre entiers relatifs et n entier naturel, n > 2

Conséquence  :


Conséquences  :

La congruence est compatible avec la multiplication.

Conséquences :

Conséquence de 1 et 4 :

Les démonstrations des propriétés 1 et 3 s’appuient sur l’équivalence ab[n] ⇔ n divise (a-b).
La propriété 4 peut être montrée par récurrence et les déductions 2 et 5 utilisent le fait que : cc[n]

Grâce à ces propriétés nous allons pouvoir manipuler la congruence de façon assez intuitive
mais attention :
La congruence n’est pas compatible avec la division !


En particulier parce que la congruence est une notion qui s’applique à des nombres relatifs
et que le rapport de deux relatifs n’est pas toujours un relatif.

Et même si les rapports sont des entiers, il faudra se méfier des simplifications abusives
en particulier lors de la résolution d’équations modulo n.

45[3]

Or : 7-5 = 2 qui n’est pas un multiple de 3 et donc : 7 5[3]

Exemples de manipulations de la congruence :
Exercice n° 1 :
Montrer que le produit de deux nombres impairs est un nombre impair.
Soit n et m deux nombres impairs.
n impair ⇔ n1[2] et m impair ⇔ m1[2]
Comme la congruence est compatible avec la multiplication : n x m 1 x 1[2]
n x m1[2] donc nxm est impair.

Exercice n° 2 : Déterminer le reste dans la division euclidienne de :

a ) 54¹⁶ par 3
b ) 21¹⁷ par 4
c ) 23² par 4
d ) (-39)³ par 7
e ) 120¹³par 11

a ) 54¹⁶ par 3
Ce cas est extrêmement simple : 5+4 = 9 donc 3 divise 54.

D’où 540[3]

Et comme la congruence est compatible avec la puissance : 54¹⁶ 0¹⁶[3]

D’où : 54¹⁶ 0¹⁶[3] , le reste dans la division euclidienne de  54¹⁶ par 3 est donc 0.

b ) 21¹⁷ par 4
21 = 4 x 5 + 1 Donc : 21 1[4]

D’où : 27¹⁷1¹⁷[4]
D’où : 27¹⁷1¹⁷[4] , le reste dans la division euclidienne de  27¹⁷ par 4 est donc 1.

c ) 23² par 4
23 = 4 x 5 + 3 

Donc 233[4]
D’où : 23²3²[4]

Soit : 23²9[4]

Or : 9 4 x 2 + 1
Donc : 91[4]
23²1[4]Le reste dans la division euclidienne de 23² par 4 est donc 1.

d ) (-39)³ par 7
La division euclidienne est plus difficile à manipuler dans que dans .

Cherchons donc plutôt un multiple de 7 proche de (-39).

-39 = -42 + 3 
-42 est un multiple de 7 donc : -393[7]

D’où : (-39)³27[7]
Or : 27 = 3 x 7 + 6
Donc : (-39)³6[7]

e ) 120¹³ par 11
120 = 11 x 10 + 10

Donc : 12010[11]

Mais mettre 10 à la puissance 13 ne va pas faciliter la résolution du problème.
Il est donc ici plus judicieux d’utiliser un autre représentant de la classe :
en enlevant 11 à 10, on obtient que : 10-1[11]

D’où : 120¹³(-1)¹³[11]
Soit 120¹³-1[11]

6/ Petit théorème de Fermat

Petit théorème de Fermat :

Soient p un nombre premier et a un entier naturel non nul.
Si pgcd (a ; p) = 1 alors a^p-11[p]

3) Rappel : si p est premier alors « a est premier avec p » si et seulement si « p ne divise pas a ».

Corollaire du petit théorème de Fermat  :

Soient p un nombre premier,
quel que soit a entier naturel : apa[p]

Démonstration  :

* Si a est un entier naturel non nul et si p ne divise pas a alors a et p sont premiers entre eux et d’après le petit théorème de Fermat :

a^p-11[p] D’où : a x a^p-1a x 1[p] Et donc : a^pa[p]

* Si a est un entier naturel non nul et si p divise a alors : a0[p]

Donc : a^p0[p]  D’où a^pa[p]

* Si a vaut 0 , 00[p] donc a0[p]

On retombe alors sur le cas précédent.
Quel que soit a, on a donc bien : a^pa[p]

quel que soit n entier naturel : n³ n[3]
D’où : n³- n0[3]
Par conséquent : 3 divise n3 - n , pour tout n entier naturel.