4- Congruence modulo n - l’ensemble ℤ/nℤ

4.1 Congruence modulo n

4.1.1 Définition

Soient (a;b)∈ ℤ² et n∈IN*.
On dit que a est congru à b modulo n et on écrit a≡b[n] 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.

4.1.2 Propriétés

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

4.1.3 Définition et propriété

1) Définition La congruence modulo n est
reflexive ; symétrique et transitive.
On dit que la congruence modulo n est une relation d'équivalence.

2) 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.

Démonstration
a=nq+r tel que 0≤r<n.
b=nq'+r' tel que 0≤r'<n.

a≡b[n] ⇔ (∃k∈ℤ) b-a=kn
⇔ n(q'-q)+(r'-r)=kn
⇔ r'-r =(k+q-q')n
⇔ n|(r'-r) ⇔ r'=r
car -n<-r≤0 et 0≤r'<n
donc -n<r'-r<n
ou encore |r'-r|<n et n|r'-r ainsi r=r'.

Remarque
Soient (a;b)∈ℤ² et n∈IN*.
ac≡bc[n] ⇏ a≡b[n].
Contre exemple 3×5≡3×4[3] mais 5≢4[3].

Exercice 1 tp

Montrer que 137≡123[7].

Correction

137=19×7+4 et 0≤r=4<7
et 123=17×7+4 tel que 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].

4.1.4 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 ab≡1[n].

Exemples
1) 4×13≡1[17] donc 4 est un inverse de 13 modulo 17.
2) 5×29≡1[3] donc 5 est un inverse de 29 modulo 3.

Exercice 2 tp

Trouver un inverse de 4 pour la congruence modulo 17.

Correction

On désigne par x un inverse de 4
4x≡1[17] ⇔ 4x-1=17k tel que k∈ℤ.
On considère l'équation E: 4x-17k=1 tel que k∈ℤ.
17=4x4+1 ⇔ 17-4x4=4x(-4)-17(-1)=1
(-4;-1) est une solution particulière de l'équation E donc il suffit de prendre x=-4.

Exercice 3 tp

Soit n un entier naturel.
Montrer que 18²ⁿ ≡1[19].

Correction

18²ⁿ=(18²)ⁿ=324ⁿ
324≡1[19] car 19|323
⇒ 324ⁿ≡1ⁿ[19]
⇒ (18²)ⁿ≡1[19]
ainsi 18²ⁿ≡1[19].