Anneaux Z/nZ - Applications

Dans tout ce donument, n ∈ N∗ .

1 Relation de congruence et définition de l’ensemble Z/nZ

Définition 1.1
Soient a, b ∈ Z. On dit que a est congru à b modulo n lorsque n divise a − b. On note alors a ≡ b (mod n).

Proposition 1.2
La relation de congruence modulo n est une relation d’équivalence sur Z.

Preuve. Il faut montrer que la relation de congruence mudulo n est réflexive, symétrique et transitive.
Soit a ∈ Z. n divise 0 donc n divise a − a. On a donc a ≡ a (mod n), d’où la réflexivité.
Soient a, b ∈ Z tels que a ≡ b (mod n). Alors n divise a−b. Il existe k ∈ Z tel a−b = kn. Alors b−a = (−k)n,
avec −k ∈ Z. Par conséquent, n divise b − a et donc b ≡ a (mod n), d’où la symétrie.
Soient a, b, c ∈ Z tels que a ≡ b (mod n) et b ≡ c (mod n). Il existe k, k 0 ∈ Z tels que a−b = kn et b−c = k 0 n.
On a alors :
a − c = a − b + b − c = kn + k 0 n = (k + k 0 )n

avec k + k 0 ∈ Z. n divise alors a − c et donc a ≡ c (mod n), d’où la transitivité. 

Notation 1.3
On note Z/nZ l’ensemble des classes d’équivalence pour la relation de congruence modulo n.

Proposition 1.4
Pour tout a ∈ Z, il existe un unique entier b ∈ J0 ; n − 1K tel que a ≡ b (mod n). b est le reste de la division
euclidienne de a par n.

Preuve. Soit a ∈ Z. Effectuons la division euclidienne de a par n : il existe un unique couple (q, b) ∈ Z × N
tel que a = nq + b, avec b ∈ J0 ; n − 1K. n divise a − b (car nq = a − b) donc a ≡ b (mod n), d’où l’existence.
Soit b0 ∈ J0 ; n − 1K tel que a ≡ b0 (mod n). Il existe q 0 ∈ Z tel que a − b0 = q 0 n, ou encore a = q 0 n + b0 . On a
alors q 0 n + b0 = qn + b, ce qui s’écrit aussi (q 0 − q)n = b − b0 . Or, b − b0 vérifie −n < b − b0 < n. On en déduit
−n < (q 0 − q)n < n, puis −1 < q 0 − q < 1. q − q 0 ∈ Z donc q 0 − q = 0 et donc b − b0 = (q 0 − q)n = 0. D’où
l’unicité. 

Corollaire 1.5
Z/nZ a exactement n éléments : 0, 1, . . . , n − 1.

Preuve. Pour tout α ∈ Z/nZ, il existe un unique a ∈ J0 ; n − 1K tel que α = a, donc Z/nZ admet au plus n
éléments.
 Anneaux Z/nZ - Applications

Soient a, b ∈ J0 ; n − 1K tels que a 6= b. Supposons a = b. Il existe k ∈ Z tel que a − b = nk. Or, −n < a − b < n
donc −n < nk < n. Par suite, −1 < k < 1. Comme k ∈ Z, k = 0 et donc a = b. Contradiction donc a 6= b et
donc Z/nZ a exactement n éléments : 0, 1, . . . , n − 1. 

2 Structure algébrique de Z/nZ

Proposition 2.1
Soient a, a0 , b, b0 ∈ Z tels que a ≡ a0 (mod n) et b ≡ b0 (mod n). Alors a + a0 ≡ b + b0 (mod n) et ab ≡ a0 b0
(mod n).

Preuve. Soient a, a0 , b, b0 ∈ Z tels que a ≡ a0 (mod n) et b ≡ b0 (mod n). Il existe k, k 0 ∈ Z tels que a−a0 = kn
et b − b0 = k 0 n. Alors a − a0 + b − b0 = kn + k 0 n, c’est-à-dire (a + b) − (a0 + b0 ) = (k + k 0 )n, avec k + k 0 ∈ Z
donc a + a0 ≡ b + b0 (mod n).
On a a = a0 + kn et b = b0 + k 0 n. On en déduit :

ab = (a0 + kn)(b0 + k 0 n) = a0 b0 + (a0 k 0 + kb0 + kk 0 n)n.

n divise donc ab − a0 b0 et donc ab ≡ a0 b0 (mod n). 

Définition 2.2
Soient α, β ∈ Z/nZ, a, b ∈ Z tels que α = a et β = b. On définit + et × par : α+β = a + b et α×β = a × b.

Remarque 2.3
La proposition précédente assure que le résultat de α + β et α × β est indépendant des représentants
respectifs a et b de α et β.

Théorème 2.4
(Z/nZ , + , ×) est un anneau commutatif.

Preuve. Montrons d’abord que (Z/nZ , +) est un groupe commutatif.

Z/nZ 6= ∅ car 0 ∈ Z/nZ.
Soient α, β, γ ∈ Z/nZ. Soient a, b, c ∈ Z tels que α = a, β = b et γ = c.

α+β =a+b=a+b=b+a=b+a=β+α

donc + est commutative.

0 est un élément neutre pour cette opération car :

α + 0 = a + 0 = a + 0 = a = α.

α admet un opposé qui est −a :

α + −a = a + −a = a + (−a) = 0.

+ est associative :

α + (β + γ) = a + (b + c) = a + b + c = a + (b + c) = (a + b) + c = a + b + c = (a + b) + c = (α + β) + γ.

× est associative :

α × (β × γ) = a × (b × c) = a × b × c = a × (b × c) = (a × b) × c = a × b × c = (a × b) × c = (α × β) × γ.

S. Duchet - http://epsilon.2000.free.fr 2/9

 Anneaux Z/nZ - Applications

× est distributive par rapport à + :

α×(β +γ) = a×(b+c) = a×b + c = a × (b + c) = a × b + a × c = a × b+a × c = a×b+a×c = α×β +α×γ.

Enfin, × est commutative :

α × β = a × b = a × b = b × a = b × a = β × α.

(Z/nZ , + , ×) est donc un anneau commutatif. 

Proposition 2.5
Soit k ∈ Z. k est inversible dans Z/nZ si et seulement si k ∧ n = 1.

Preuve. Soit k ∈ Z. Supposons k inversible dans Z/nZ. Il existe a ∈ Z tel que k × a = 1 donc n divise ka − 1.
Il existe b ∈ Z tel que ka − 1 = nb. Alors ka + (−b)n = 1, avec (a , −b) ∈ Z2 . D’après le théorème de Bézout,
k ∧ n = 1.
Supposons maintenant k ∧ n = 1. Il existe (u , v) ∈ Z2 tel que ku + nv = 1. Alors ku + nv = 1. Or,
ku + nv = k · u + n · v et n = 0 donc ku = 1 et donc k est inversible dans Z/nZ. 

Corollaire 2.6
Z/nZ est un corps si et seulement si n est premier.

Preuve. Supposons que Z/nZ est un corps. Alors Z/nZ est intègre. Supposons n non premier. Il existe
p, q ∈ N − {0 , 1} tel que n = pq. n = 0 donc p × q = 0, avec p, q ∈ J2 ; n − 1K (et donc p 6= 0 et q 6= 0), ce qui
contredit le fait que Z/nZ est intègre. n est donc un nombre premier.
Supposons maintenant n premier. Soit a ∈ J1 ; n − 1K. Alors a ∧ n = 1 et donc a est inversible dans Z/nZ.
Tout élément non nul de Z/nZ est donc inversible donc Z/nZ est un corps. 

3 Applications
3.1 Critères de divisibilité
Théorème 3.1
Soit a ∈ N∗ .
(i) a est divisible par 2 si et seulement si a se termine par 0, 2, 4, 6 ou 8 ;
(ii) a est divisible par 5 si et seulement si a se termine par 0 ou 5 ;
(iii) a est divisible par 3 (respectivement par 9) si et seulement si la somme des chiffres qui le composent
est divisible par 3 (respectivement par 9) ;
(iv) a est divisible par 4 si et seulement si le nombres formé par les deux derniers chiffres est divisible par
4;
(v) a est divisible par 10 si et seulement si a se termine par 0.

Preuve. Soit a ∈ N∗ . Il existe un unique p ∈ N et un unique (p+1)-uplet (ap , . . . , a0 ) ∈ J0 ; 9Kp+1 , avec ap 6= 0

p
k
X
tels que a = ak 10k . Pour prouver l’assertion (i), on se place dans Z/2Z. Pour k > 1, 10k = 10 = 0 donc
k=0
a = a0 . a est divisible par 2 si et seulement si a = 0 c’est-à-dire si et seulement si a0 = 0. a0 ≡ 0 (mod 2) si
et seulement si a0 ∈ {0, 2, 4, 6, 8}, d’où le résultat.
Les autres points se démontrent de la même manière et sont laissés au lecteur. 

S. Duchet - http://epsilon.2000.free.fr 3/9

 Anneaux Z/nZ - Applications

3.2 Groupes cycliques

Proposition 3.2
Un groupe cyclique à n éléments est isomorphe à (Z/nZ , +).

Preuve. Soit G un groupe cyclique à n éléments. Soit g un générateur de G. G étant fini, g est d’ordre fini.
Notons p l’ordre de g. On a alors G = {e, g, . . . , g p−1 }, où e désigne l’élément neutre du groupe G. G ayant
n élements, on en déduit que n = p. On a donc G = {e, g, . . . , g n−1 }. Soit φ l’application définie sur Z/nZ, à
valeurs dans G définie par :
∀α ∈ Z/nZ , φ(α) = g a

où a est l’unique élément de J0 ; n − 1K tel que α = a.

Montrons que φ est un isomorphisme.
Soient α, β ∈ Z/nZ. Il existe un unique couple (a , b) ∈ J0 ; n − 1K2 tel que α = a et β = b. Il existe un unique
couple (q , r) ∈ Z × N tel que a + b = nq + r, avec r ∈ J0 ; n − 1K. Alors φ(α + β) = g r . Or,

g a+b = g nq+r = (g n )q g r = eq g r = g r

donc
φ(α + β) = g a+b = g a g b = φ(α)φ(β).

φ est donc un morphisme de groupes.

Montrons maintenant que φ est injectif. Soit α ∈ ker φ. Il existe un unique a ∈ J0 ; n − 1K tel que α = a.
φ(α) = e donc g a = e. Par suite, a = 0 donc ker φ = {0} et donc φ est injectif. G et Z/nZ ayant le même
nombre fini d’éléments, on en déduit que φ est bijectif. φ est donc un isomorphisme. 

3.3 Equation diophantienne

L’équation x2 − y 2 = 18, d’inconnue (x , y) ∈ Z2 n’a pas de solution dans Z2
Supposons le contraire. Soit (a , b) ∈ Z2 une solution de cette équation. Alors a2 − b2 = 18. Plaçons-nous dans
2
Z/4Z. a2 − b2 = a2 − b2 = a2 − b et 18 = 2.
a ∈ {0, 1, 2, 3} donc a2 ∈ {0, 1, 4, 9} = {0, 1}.
De même, b ∈ {0, 1}.
2 2
Si a2 = 0 et b = 0, alors a2 − b = 0.
2 2
Si a2 = 1 et b = 0, alors a2 − b = 1.
2 2
Si a2 = 0 et b = 1, alors a2 − b = −1 = 3.
2 2
Si a2 = 1 et b = 1, alors a2 − b = 0.
2
On en déduit : a2 − b ∈ {2} ∩ {0, 1, 3} = ∅. Par suite, l’équation x2 − y 2 = 18, d’inconnue (x , y) ∈ Z2 n’a
pas de solution dans Z2 .

3.4 Théorème chinois

Théorème 3.3
Soit (a, b) ∈ (N∗ )2 . Les anneaux Z/abZ et Z/aZ × Z/bZ sont isomorphes si et seulement si a ∧ b = 1.

Preuve. Si n ∈ N∗ et x ∈ Z, on note cln (x) la classe de x dans Z/nZ. Soit (a, b) ∈ (N∗ )2 tel que a ∧ b = 1.
Soit f l’application définie sur Z/abZ, à valeurs dans Z/aZ × Z/bZ, définie par ξ 7→ (cla (x) ; clb (x)), où x ∈ Z
tel que ξ = clab (x).

S. Duchet - http://epsilon.2000.free.fr 4/9

 Anneaux Z/nZ - Applications

Montrons déjà que l’application f est bien définie.

Soit ξ ∈ Z/abZ. Soient x, y ∈ Z tels que ξ = clab (x) = clab (y). x ≡ y (mod ab) donc ab divise x − y.On en
déduit que a divise x − y (c’est-à-dire cla (x) = cla (y)) et b divise x − y (c’est-à-dire clb (x) = clb (y)) et donc
f est bien définie.
Montrons maintenant que f est un morphisme d’anneaux. Soient ξ, η ∈ Z/abZ. Soient x, y ∈ Z tels que
ξ = clab (x) et η = clab (y). On a ξ + η = clab (x + y), ξη = clab (xy) et :

f (ξ+η) = (cla (x+y) ; clb (x+y)) = (cla (x)+cla (y) ; clb (x)+clb (y)) = (cla (x) ; clb (x))+(cla (y) ; clb (y)) = f (ξ)+f (η)

f (ξη) = (cla (xy) ; clb (xy)) = (cla (x)cla (y) ; clb (x)clb (y)) = (cla (x) ; cla (y))(clb (x) ; clb (y)) = f (ξ)f (η)

f (clab (1)) = (cla (1) ; clb (1))

f est bien un morphisme d’anneaux.

Il reste à montrer que f est bijective. Soit ξ ∈ Z/abZ tel que f (ξ) = (cla (0) ; clb (0)). Soit x ∈ Z tel que
ξ = clab (x). f (ξ) = (cla (x) ; clb (x)). On en déduit cla (x) = cla (0) (donc a divise x) et clb (x) = clb (0) (donc b
divise x). a et b étant premiers entre eux, on en déduit que ab divise x, c’est-à-dire clab (x) = clab (0). f est
donc injective.
card(Z/abZ) = ab et card(Z/aZ × Z/bZ) = card(Z/aZ) × card(Z/bZ) = ab. f est donc bijective (car injective
entre deux ensembles finis de même cardinal).
Supposons maintenant a ∧ b 6= 1. Montrons qu’alors Z/abZ et Z/aZ × Z/bZ ne sont pas isomorphes. clab (1)
est d’ordre ab dans le groupe additif Z/abZ donc l’ordre du groupe additif Z/abZ est un multiple de ab. Soit
p = ppcm(a ; b).
Soit (α ; β) ∈ Z/aZ × Z/bZ. Il existe (x ; y) ∈ J0 ; n − 1K × J0 ; m − 1K tel que (α ; β) = (cla (x) ; clb (y)).
(pα ; pβ) = (cla (px) ; clb (py)). p est un multiple de a donc cla (px) = cla (0). De même, p est un multiple de b
donc clb (py) = clb (0). On en déduit que tous les éléments de Z/aZ × Z/bZ ont un ordre qui divise p. L’ordre
de Z/aZ × Z/bZ est donc inférieur ou égal à p. Or, p < ab car a ∧ b 6= 1. Z/abZ étant d’ordre un multiple de
ab, il ne peut donc pas être isomorphe à un groupe dont l’ordre est strictement inférieur à ab. 

3.5 Théorème des restes chinois et systèmes de congruences

Théorème 3.4
Soient p ∈ N∗ , n1 , . . . , np des entiers naturels deux à deux premiers entre eux et (a1 , . . . , ap ) ∈ Zp . Alors
le système de congruences défini par : ∀k ∈ J1, pK, x ≡ ak (mod nk ) admet une unique solution modulo
p
uk Nk ak , où pour tout k ∈ J1, pK, Nk = nNk et uk ≡ Nk−1 (mod nk ).
P
N = n1 . . . np , donnée par x ≡
k=1

Preuve. Soient p ∈ N∗ , n1 , . . . , np des entiers deux à deux premiers entre eux et (a1 , . . . , ap ) ∈ Zp . Notons
(S) le système de congruences défini par :

∀k ∈ J1, pK, x ≡ ak (mod nk ).

N
Pour tout k ∈ J1, pK, on note Nk l’entier Nk . Les entiers nk étant deux à deux premiers entre eux, il en résulte
que pour tout entier k ∈ J1, pK, Nk et nk sont premiers entre eux et donc Nk est inversible modulo nk . Pour
p
tout k ∈ J1, pK, notons uk ≡ Nk−1 (mod nk ). Soit x =
P
uk Nk ak . Soit i ∈ J1, pK. Si k ∈ J1, pK et k 6= i, alors
k=1
Ni ≡ 0 (mod nk ). On a alors x ≡ ui Ni ai (mod ni ). Or ui Ni ≡ 1 (mod ni ) par définition de ui donc x ≡ ai
(mod ni ). Ceci étant vrai pour tout entier i ∈ J1, pK, x est une solution du système (S). D’où l’existence.

S. Duchet - http://epsilon.2000.free.fr 5/9

 Anneaux Z/nZ - Applications

Soit y une autre solution de (S). Alors pour tout k ∈ J1, pK, x − y ≡ 0 (mod nk ), c’est-à-dire nk divise x − y.
Les entiers nk étant deux à deux premiers entre eux, il en résulte que N divise x − y, c’est-à-dire x ≡ y
(mod N ), d’où l’unicité de la solution modulo N . 

Exemple 3.5
Résoudre dans Z le système suivant :


 x ≡ 4 (mod 5)

x ≡ 3 (mod 6)


x ≡ 2 (mod 7).


5 ∧ 6 ∧ 7 = 1. On applique le théorème des restes chinois, avec n1 = 5, n2 = 6, n3 = 7, N = 210, a1 = 4, a2 = 3

et a3 = 2. On sait que ce système admet une unique solution modulo 210, donnée par x = u1 a1 N1 + u2 a2 N2 +
N 210 N 210 N 210
u3 a3 N3 , où N1 = n1 = 5 = 42, N2 = n2 = 6 = 35 et N3 = n3 = 7 = 30, et u1 , u2 , u3 sont les inverses
respectifs de N1 , N2 , N3 modulo n1 , n2 , n3 .
42∧5 = 1. D’après le théorème de Bézout, il existe (u, v) ∈ Z2 tel que 42u+5v = 1. L’algorithme d’Euclide
donne :
42 = 5 × 8 + 2
5=2×2+1
2=1×2+0
En remontant cet algorithme, on obtient successivement :
1=5−2×2
1 = 5 − (42 − 5 × 8) × 2
1 = 5 − 42 × 2 + 5 × 16
42 × (−2) + 5 × 17 = 1.
On en déduit que u1 = −2.
Un raisonnement analogue conduit à u2 = −1 et u3 = −3.
Par suite, x ≡ −2 × 4 × 42 + (−1) × 3 × 35 + (−3) × 30 × 2 (mod 210), c’est-à-dire x ≡ 9 (mod 210) (après
simplifications).

Exemple 3.6
Résoudre
 dans Z le système suivant :
 x ≡ 3 (mod 4)
 x ≡ 5 (mod 6).

4 et 6 ne sont pas premiers entre eux. Soit x une solution du système. Alors x ≡ 2 (mod 3), de sorte qu’on
peut
 résoudre le système :
 x ≡ 3 (mod 4)
 x ≡ 2 (mod 3).
4 et 3 sont premiers entre eux donc on applique le théorème chinois pour résoudre ce système. On vérifie
ensuite que les solutions trouvées sont solutions du système de départ.

S. Duchet - http://epsilon.2000.free.fr 6/9

 Anneaux Z/nZ - Applications

3.6 Indicatrice d’Euler

Définition 3.7
On suppose n > 2. On note ϕ(n) le nombre d’entiers compris entre 1 et n et premiers avec n. ϕ est appelé
indicatrice d’Euler.

Proposition 3.8
(i) Soient p, q ∈ N∗ , avec p ∧ q = 1. Alors ϕ(pq) = ϕ(p)ϕ(q) ;
N
Y
(ii) Si prkk est une décomposition de n en produit de facteurs premiers, on a :
k=1

N N  
Y Y 1
ϕ(n) = (pri i − pri i −1 ) = n 1−
pi
k=1 k=1

Preuve.
(i) Soient p, q ∈ N∗ tels que p ∧ q = 1. Alors Z/pqZ et Z/pZ × Z/qZ sont isomorphes. Il en résulte que
(Z/pqZ)∗ et (Z/pZ × Z/qZ)∗ sont isomorphes.
Montrons maintenant que (Z/pZ × Z/qZ)∗ = (Z/pZ)∗ × (Z/qZ)∗ .

(α ; β) ∈ (Z/pZ × Z/qZ)∗ ⇐⇒ ∃(α0 ; β 0 ) ∈ Z/pZ × Z/qZ, (α ; β) · (α0 ; β 0 ) = (clp (1) ; clq (1))
⇐⇒ ∃(α0 ; β 0 ) ∈ Z/pZ × Z/qZ, (αα0 , ββ 0 ) = (clp (1) ; clq (1))
⇐⇒ ∃α0 ∈ Z/pZ, ∃β 0 ∈ Z/qZ, αα0 = clp (1), ββ 0 = clq (1)
⇐⇒ α ∈ (Z/pZ)∗ , β ∈ (Z/qZ)∗

On en déduit alors que (Z/pqZ)∗ et (Z/pZ)∗ × (Z/qZ)∗ sont isomorphes. Ce sont des ensembles finis donc ils
ont le même cardinal. Or, card(Z/pqZ)∗ = ϕ(pq) et

card((Z/pZ)∗ × (Z/qZ)∗ ) = card(Z/pZ)∗ × card(Z/qZ)∗ = ϕ(p)ϕ(q).

Il vient alors ϕ(pq) = ϕ(p)ϕ(q).

(ii) L’assertion (i) se généralise pour plusieurs nombres deux à deux premiers entre eux. Soit p un nombre
premier et r ∈ N∗ .

ϕ(pr ) = card({k ∈ {1, . . . , pr } , k ∧ pr = 1}) = card({k ∈ {1, . . . , pr }}) − card({k ∈ {1, . . . , pr } , k ∧ pr 6= 1}).

card({k ∈ {1, . . . , pr }}) = pr . Soit k ∈ J1 ; pr K. p étant premier, on a :

k ∧ pr = 1 ⇐⇒ p|k ⇐⇒ k ∈ {pq , 1 6 q 6 pr−1 }

donc card({k ∈ {1, . . . , pr } , k ∧ pr 6= 1}) = pr−1 . On en déduit ϕ(pr ) = pr − pr−1 .

Y N
Soit n ∈ N∗ . Notons Pkrk sa décomposition en facteurs premiers.
k=1

N
! N N   YN N   N  
Y Y Y 1 Y 1 Y 1
ϕ(n) = ϕ prkk = (prkk − prkk −1 ) = prkk 1− = rk
pk 1− =n 1− .
pk 1
pk 1
pk
k=1 k=1 k=1 k=1 k= k=

S. Duchet - http://epsilon.2000.free.fr 7/9

 Anneaux Z/nZ - Applications

3.7 Le petit théorème de Fermat

Théorème 3.9
Soit p un nombre premier. Alors pour tout n ∈ N, np ≡ n (mod p).
 
p
Preuve. Soit p un nombre premier. Montrons d’abord que pour tout k ∈ J1 ; p − 1K, p divise . Soit
k
k ∈ J1 ; p − 1K.  
p p!
k! = = p(p − 1) · · · (p − k + 1).
k (p − k)!
 
p
p divise donc k! . Or p est premier avec k! car p est un nombre premier et k < p (donc p est premier avec
k
tous les nombres entiers compris
 entre 1 et p − 1 donc avec leur produit). D’après le théorème de Gauss, il
p
en résulte que p divise .
k
Montrons maintenant le théorème par récurrence sur n. Pour n ∈ N, notons H(n) l’égalité np ≡ n (mod p).
H(0) est clairement vérifiée.
Soit n ∈ N. Supposons H(n) vraie.
p   p−1  
p
X p k p
X p
(n + 1) = n =1+n + nk .
k k
k=0 k=1
 
p
Or, pour tout k ∈ J1 ; p − 1K, ≡ 0 (mod p) donc (n + 1)p ≡ 1 + np (mod p). D’après l’hypothèse de
k
récurrence, np ≡ n (mod p) donc (n + 1)p ≡ n + 1 (mod p). H(n + 1) est donc vraie. D’après le principe de
récurrence, on en déduit que H(n) est vraie pour tout entier naturel n. 

3.8 Cryptage RSA

Proposition 3.10
Soient p et q deux nombres premiers distincts. On pose n = pq. Soient c et d deux entiers naturels tels
que cd ≡ 1 (mod ϕ(n)). Alors pour tout t ∈ Z, tcd ≡ t (mod n).

Preuve. Soient p, q deux nombres premiers distincts. On note n = pq. Soient c et d deux entiers naturels tels
que cd ≡ 1 (mod ϕ(n)). Soit t ∈ Z. ϕ(n) = ϕ(pq) = ϕ(p)ϕ(q) = (p − 1)(q − 1), d’après ce qui a été vu sur
l’indicatrice d’Euler.
Pour montrer que tcd ≡ t (mod n), il suffit de montrer que tcd ≡ t (mod p) et tcd ≡ t (mod q). En effet,
on aura dans ce cas p|tcd − t et q|tcd − t. p et q étant premiers distincts donc premiers entre eux, il vient
pq|tcd − t, c’est-à-dire tcd ≡ t (mod n).
Montrons que tcd ≡ t (mod p).
Si t ∧ p = 1, alors tp ≡ t (mod p) d’après le petit théorème de Fermat. t ∧ p = 1 donc t est inversible modulo
p donc tp · t−1 ≡ t · t−1 (mod p), c’est-à-dire tp−1 ≡ 1 (mod p). cd ≡ 1 (mod ϕ(n)) donc il existe k ∈ Z tel
que cd = 1 + kϕ(n) = 1 + k(p − 1)(q − 1). On a alors :

tcd ≡ t1+k(p−1)(q−1) ≡ t · (tp−1 )k(q−1) ≡ t (mod n).

Si t ∧ p 6= 1, p étant premier, alors p divise t, c’est-à-dire t ≡ 0 (mod p). Das ce cas, on a de façon évidente
tcd ≡ t (mod p).
Dans tous les cas, tcd ≡ t (mod p). De même, tcd ≡ t (mod q) et donc tcd ≡ t (mod n).
Complément :

S. Duchet - http://epsilon.2000.free.fr 8/9

 Anneaux Z/nZ - Applications

c
L’application f de Z/nZ dans Z/nZ définie par t 7→ t est appelée fonction de chiffrement. L’application g de
d
Z/nZ dans Z/nZ définie par t 7→ t est appelée fonction de déchiffrement, t étant le message. Le couple (n , c)
est appelée clé publique, d étant la clé secrète. La sûreté du chiffrement est assurée par le fait que connaissant
(n , c), il est très difficile de déterminer d car il faudrait exprimer n comme produit de deux facteurs premiers
p et q, ce qui n’est pas envisageable lorsque p et q sont grands (une bonne centaine de chiffres).
RSA vient du nom des inventeurs Rivest, Shamir et Adleman qui ont mis au point ce système en 1977.


S. Duchet - http://epsilon.2000.free.fr 9/9