4.4 L'ensemble ℤ/pℤ tel que p premier

4.3.1 Définition

Soit x∈ℤ/pℤ.
On dit que x admet un inverse s'il existe un élément v dans ℤ/pℤ tel que xv=1.

Exemples
Inverse de 3∈ℤ/5ℤ.
On cherche un élément u de ℤ/5ℤ s'il existe tel que u3=1.

u3=1 ⇔ 3u≡1[5].
On peut remarquer que u=2 mais on préfére la méthode de la congruence modulo 5 pour plus de connaissances.
On utilise l'algorithme d'Euclide
5=1×3+2
3=1×2+1
donc 1=3-1x2=3-1×(5-1x3)=2×3-1×5
soit 1≡2×3[5] donc u≡2×3[5]
et puisque 3u≡1[5] ou encore 2×3u≡2[5] alors u≡2[5] ainsi 2 est l'inverse de 3.

4.3.3 Propriété

1) Soit p un nombre premier
(∀u∈Z*) (∃v∈Z): u×v≡1[p].
2) Soit p un nombre premier
∀(u;v)∈ℤ/pℤ: u x v=0 ⇒ u=0 ou v=0.

Démonstration u × v=0 ⇒ u × v=0
⇒ u×v≡0[p] ⇒ p|(u×v)
⇒ p|u ou p|v (premier)
⇒ u≡0[p] ou v≡0[p]
⇒ u=0 ou v=0.

Remarque
Si p n'est pas premier alors la propriété précédente n'est pas vraie.
Contre exemple p=15=3×5
3×5=0 mais 3≠0 et 5≠0.

Exercice 1 tp

Soit n∈IN.
En utilisant la notion de la congruence montrer que n(n+1) est un nombre pair.

Correction

Cette question peut être accomplie par disjonction des cas (le cas n pair et le cas n impair)
on fait la même chose mais en utilisant la congruence modulo 2.
ℤ/2ℤ={0 ; 1}.

Rappel: ℤ=0 ∪ 1.
0={x∈IN/ x=2k avec k∈IN} est exactement l'ensemble des nombres pairs
et 1={x∈IN / x=1+2k; k∈IN} est l'ensemble des nombres impairs.
Il suffit donc de montrer que 2|n(n+1)
ou encore n(n+1)≡0[2].
Soit n∈IN donc si n∈0 alors 0×(0+1)=0 est un nombre pair
et si n∈1 alors 1×(1+1)=2 est bien aussi un nombre pair
ainsi (∀n∈IN): n(n+1) est pair.

Exercice 2 tp

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

Exercice 3 tp

Montrer que 594²⁰≡1[7].

Exercice 4 tp

Résoudre dans ℤ l'équation 5x≡10[37].

Correction

u l'inverse de 5 pour la congruence modulo 37 signifie 5u≡1[37].

On utilisant l'algorithme d'Euclide
37=7.5+2
5=2.2+1 donc 1=5-2.2
ou encore 1=5-2.(37-7.5)
=15.5-2.37
ainsi 15.5≡1[37].
On a d'une part 15.5.x ≡ 1.x[37]
et d'autre part 15.5.x ≡ 15.10[37]
et par transitivité x≡150[37].
Puisque 150>37 on peut simplifier
150=4.37+2 donc x≡2[37]
ainsi S={2+37k/ k∈Z}.