5- L’ensemble ℤ/nℤ

5.1 Congruence modulo n (rappel)

5.1.1 Définitions et propriétés

Soient (a;b)∈ ℤ² et n∈IN*.
On dit que a est congru à b modulo n et on écrit a≡b[n] si et seulement si n divise b-a.
En d'autre terme
a≡b[n] ⇔ n|(b-a) ⇔ (∃k∈ℤ): b=kn+a.

Exemples
17≡8[3] car 3|17-8.
13≡9[2] car 2|13-9.

Propriétés
Reflexivité: (∀n∈IN*)(∀a∈ℤ): a≡a[n].
Symétrie: (∀n∈IN*)(∀(a ; b)∈ℤ²)
a≡b[n] ⇔ b≡a[n].
Transitivité: (∀n∈IN*)(∀a;b;c∈ℤ)
a≡b[n] et b≡c[n] ⇒ a≡c[n].

Définition
La congruence modulo n est réflexive ; symétrique et transitive.
On dit que la congruence modulo n est une Relation d'équivalence.

Propriété
Soient n∈IN* et (a;b)∈ℤ².
a≡b[n] ⇔ a et b ont le même reste dans la division euclidienne par n.

Théorème
Soient (a;b)∈ℤ² et n∈IN*.
(∀c∈ℤ*): (ac≡bc[n] et c∧n=1) ⇒ a≡b[n].

Exemple
4.29≡4.3[13]⇒29≡3[13]
car 4∧13=1.

Remarque
La condition c∧n=1 est importante.

Contre exemple 3.5≡3.4[3] mais 5≢4[3].

Exemple
Soient a=137 ; b=123 et n=7.
Montrer que 137≡123[7].

Correction
137=19.7+4 avec 0≤r=4<7
et 123=17.7+4 avec 0≤r'=4<7
et donc a et b ont le même reste dans la division euclidienne par 3
ainsi 137≡123[7]
et de plus 137≡123≡4[7].

5.1.2 Inverse d'un élément pour la congruence modulo n

Définition
Soit (a;n)∈ℤ*².
a admet un inverse pour la congruence modulo n, s'il existe un entier b
tel que a.b≡1[n].

Exemple
3.7≡1[10] donc 3 est un inverse de 7 pour la congruence modulo 10.

Théorème
Soit n∈IN*.
a∈ℤ* admet un inverse pour la congruence modulo n
si et seulement si a∧n=1.

Exemple 1 Soit n=17.
Déterminer un inverse de 4 pour la congruence modulo 17

Correction
4∧17=1 donc 4 admet un inverse, noté x
4.x≡1[17] ⇔ (E): 4x-17k=1 avec k∈ℤ

17=4.4+1 ⇔17-4.4=1
⇔ 4.(-4)-17(-1)=1.
(-4;-1) est une solution particulière de l'équation (E).
Il suffit donc de prendre x=-4.
-4 est bien un inverse de 4 pour la congruence modulo 17.

Exercice 1 tp

1) Effectuer la division euclidienne de 1904 et 1232.
2) Déduire 1904∧1232 et 1904∨1232.