Cours maths Terminale S

Congruences

Dans ce module, étude de la notion de congruence. La congruence modulo n de deux entiers relatifs est tout d’abord définie, ensuite la notion de classe et de représentant d’une classe, modulo n. Le cours de termine par le petit théorème de Fermat et son corollaire.

 

1/ Division euclidienne

Division euclidienne dans ℕ:

Soient a ∈ ℕ et b ∈ ℕ *
Il existe un unique couple ( q , r ) d’entiers naturels tels que :
a = b x q + r avec 0 ≤ r

q est le quotient, r> le reste, b le diviseur et a le dividende.

Propriétés

« b divise a » si et seulement si « le reste de la division euclidienne de a par b est nul ».
Division euclidienne dans ℤ:

Soient a ∈ ℤ et b ∈ ℤ *
Il existe un unique couple ( q , r ) d’entiers relatifs tels que :
a = b x q + r avec 0 ≤ r

q est le quotient, r> le reste, b le diviseur et a le dividende.

Remarques :

1) si a et b sont des naturels, le couple obtenu dans les deux divisions est le même
2) dans tous les cas, r est un entier naturel

 

2/ Congruence : définition

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

Définition :

1) On dit aussi que a et b sont égaux modulo n.

2) La congruence modulo 1 ne présente aucun intérêt car dans la division e0uclidienne par 1, tout nombre a pour reste 0. Et donc deux nombres quelconques sont égaux modulo 1.

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

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é)

Exemple :

5 et 14 sont-ils congrus modulo 3 ?
Leurs divisions euclidiennes par 3 sont : 5 = 3 x 1 + 2     14 = 3 x 4 + 2
5 et 14 ont le même reste dans la division euclidienne par 3 donc : 5 14 [3]

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.
Etendons cette remarque au cas général :

 

3/ Congruence : équivalence

Propriétés :

Soient a et b deux entiers relatifs et n entier naturel, n ≥ 2
a ≡ b [n] ⇔ n divise (a-b)

Démonstration :

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
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

Alors : b = a - nk = n x (q - k) + r
Avec 0 ≤ r 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]

Remarque :

Pour montrer que deux nombres sont congrus modulo n, il suffira donc de montrer que leur différence est un multiple de n.

Conséquences :

a ≡ 0[n] ⇔ n divise a

Remarque :

En particulier, n divise n et n divise 0 donc : n ≡ 0[n] et 0 ≡0[n]
a ≡ b[n] ⇔ n divise (a-b) ⇔ a - b ≡ 0[n]

Quel que soit d entier naturel supérieur ou égal à 2 :
Si a ≡ b[n] et d divise n alors a ≡ b[d]

Démonstration :

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

 

4/ Congruence : restes et classes

En trigonométrie où il est question d’angles égaux modulo 2π, on parle de mesure principale, comprise par exemple entre 0 et 2π exclu.
Cette idée de choisir un représentant pour un ensemble de nombres égaux modulo 2π 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 a ≡ r[n]

Démonstration :

En effet, si r est le reste dans la division euclidienne de a par n alors
il existe q entier relatif tel que : a = n x q + r avec 0 ≤ r
Donc n divise (a-r) et par conséquent a est congru à r modulo n.

Propriété réciproque :

Soient a entier relatif et n entier naturel,
Si a ≡ r[n] et 0 ≤ r 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
Donc il s’agit de la division euclidienne de a par n et r en est le reste.

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

Donc par unicité de la division euclidienne, chaque entier a ne peut être congru qu’à un seul entier compris entre 0 et n exclu.

Cet entier étant le reste dans la division euclidienne de a par n.

Chacun des restes possibles dans la division euclidienne par n peut donc être considéré comme le représentant d’un ensemble de nombres qui lui sont congrus modulo n.

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.

Exemple :

Considérons l’ensemble ℤ modulo 2.
Les restes possibles dans la division euclidienne par 2 sont 0 et 1.

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 )

Le terme de « classe » n’est pas explicitement au programme de la terminale mais voir les choses de cette façon permet d’avoir une vision plus claire de la congruence.

Forts de ce découpage en classes, on pourra ramener la résolution de certains exercices à une simple étude de n cas,
correspondants aux différents restes possibles dans la division euclidienne par n.

 

5/ Congruence et opérations

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

La congruence est compatible avec l’addition.

Conséquence :


Conséquence :


Conséquence :





Conséquence de 1 et 4 :


Les démonstrations des propriétés 1 et 3 s’appuient sur l’équivalence a ≡ b[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 : c ≡ c[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.

En effet, par exemple :
45 et 63, multiples de 3 sont congrus à 0 modulo 3 donc : 63 ≡ 45[3]
En simplifiant par 9, on obtiendrait :7 ≡ 5[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 ⇔ n ≡ 1[2] et m impair ⇔ m ≡ 1[2]

Comme la congruence est compatible avec la multiplication : n x m ≡ 1 x 1[2]
n x m ≡ 1[2] donc nxm est impair.

Conclusion : le produit de nombres impairs est un nombre impair.

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

a ) 5416 par 3
b ) 2117 par 4
c ) 232 par 4
d ) (-39)3 par 7
e ) 12013par 11

L’idée est ici de trouver un représentant plus simple du nombre puis d’appliquer la puissance.
Dans la plupart des cas, on pourra se contenter de prendre comme représentant le reste dans la division euclidienne.

a ) 5416 par 3
Ce cas est extrêmement simple : 5+4 = 9 donc 3 divise 54.
D’où 54 ≡ 0[3]
Et comme la congruence est compatible avec la puissance : 5416 ≡ 016[3]

D’où : 5416 ≡ 016[3] , le reste dans la division euclidienne de 5416 ≡ par 3 est donc 0.

b ) 2117 par 4
21 = 4 x 5 + 1 Donc : 21 ≡ 1[4]

D’où : 2717 ≡ 117[4]
D’où : 2717 ≡ 117[4] , le reste dans la division euclidienne de 2717 par 4 est donc 1.

c ) 232 par 4
23 = 4 x 5 + 3
Donc 23 ≡ 3[4]
D’où : 232 ≡ 32[4]

Soit : 232 ≡ 9[4]

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

d ) (-39)3 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 : -39 ≡ 3[7]

Remarque :
Une façon simple de travailler, par exemple modulo 7, est de se dire que :
•&nbsp tout multiple de 7 compte pour 0,
•&nbsp de la même façon que nous éliminons tout multiple de 2π dans la recherche de la mesure principale d’un angle.

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

Le reste dans la division euclidienne de (-39)3 par 7 est donc 6.

e ) 12013 par 11
120 = 11 x 10 + 10

Donc : 120 ≡ 10[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ù : 12013 ≡ (-1)13[11]
Soit 12013 ≡ -1[11]

Le reste dans la division euclidienne de 12013 par 11 est donc 10.

 

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 ap-1 ≡ 1[p]

Remarques :
1) La démonstration de ce théorème, assez technique, est ici admise.

2) Ce théorème, quand il est nécessaire à la résolution d’un exercice de BAC, est souvent rappelé dans l’énoncé. Mais pas systématiquement donc …

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 : ap ≡ a[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 :

ap-1 ≡ 1[p] D’où : a x ap-1