LEÇON N˚ 14 :
Congruences dans Z. Anneau Z/nZ.
Pré-requis :
– Relation d’équivalence ;
– Définitions d’un groupe, d’un anneau, d’un corps ;
– Division euclidienne dans Z, notation d’un cardinal (| · |) ;
– Nombres premiers (et notation ∧), PGCD, théorème de Bézout.
14.1 Congruences dans Z (n ∈ N, n > 2)
Définition 1 : Soit (x, y) ∈ Z2 . On dit que x est congru à y modulo n si x − y ∈ nZ. On note alors
x ≡ y [n].
Proposition 1 : La relation de congruence est une relation d’équivalence.
démonstration :
Réfléxivité : x − x = 0 · n ∈ nZ, donc x ≡ x [n].
Symétrie : On suppose que x ≡ y [n], c’est-à-dire qu’il existe k ∈ Z tel que x − y = kn. Alors
y − x = −k · n ∈ nZ, donc y ≡ x [n].
Transitivité : On suppose cette fois que x ≡ y [n] et y ≡ z [n], c’est-à-dire qu’il existe k, k ′ ∈ Z tels
que x − y = kn et y − z = k ′ n. Alors x − z = (x − y) + (y − z) = kn + k ′ n = (k + k ′ )n ∈ nZ,
donc x ≡ z [n].
Les trois points de la définition d’une relation d’équivalence sont vérifiées, donc celle de congruence en
est une.
Proposition 2 : La relation de congruence est compatible avec l’addition et la multiplication de Z,
c’est-à-dire que
x ≡ y [n] x + x′ ≡ y + y ′ [n]
⇒
x ≡ y [n]
′ ′
x · x′ ≡ y · y ′ [n].
démonstration : On a les implications suivantes :
∈Z
z }| {
n
x = y + kn x + x′ = y + y ′ + (k + k ′ ) n
⇔
x′ = y ′ + k ′ n x · x′ = y · y ′ + (ky ′ + k ′ y + nkk ′ ) n.
| {z }
∈Z
x′
x + ≡ y + [n] y′
⇔
x · x′ ≡ y · y ′ [n],
2 Congruences dans Z. Anneau Z/nZ.
ce qui démontre le résultat.
Exercice : Soit p ∈ N. Montrer que x ≡ y [n] implique à la fois px ≡ py [n] et xp ≡ y p [n].
Solution : En effet, il existe k ∈ Z tel que x − y = kn. D’une part, on a ainsi que p(x − y) = p(kn) ⇔ px − py = (pk)n ⇔ px ≡
py [n]. Attention cependant à la réciproque, parce que la division par p ne garantit que le multiplicateur de n soit entier ! Il faut
alors que p divise n pour satisfaire cette condition.
D’autre part, on procède par récurrence pour la seconde congruence. Pour p = 1, il n’y a aucun problème. Supposant le résultat
vrai au rang p − 1, on applique la proposition 2 pour montrer qu’il l’est toujours au rang p, et ainsi achever la récurrence. ♦
14.2 L’anneau Z/nZ (n ∈ N∗)
Définition 2 : L’ensemble quotient de Z sur la relation de congruence est noté Z/nZ. On note x la
classe d’équivalence de x dans Z/nZ, c’est-à-dire x = {y ∈ Z | y ≡ x [n]}.
Théorème 1 : Pour tout x ∈ Z, il existe un unique r ∈ x tel que 0 6 r < n.
démonstration : On effectue la division euclidienne de x par n : il existe un unique couple (q, r) ∈
Z × N tel que x = qn + r et 0 6 r < n, donc r ⇔ x [n] ⇔ r ∈ x et 0 6 r < n.
Exercice : Montrer qu’en partiulier, x ≡ y [n] si et seulement si x et y ont même reste dans la division
euclidienne par n.
Solution : Notons x = qn + r et y = q ′ n + r ′ , avec 0 6 r, r ′ < n. On a alors les équivalences suivantes :
x ≡ y [n] ⇔ x − y = kn ⇔ qn + r − q ′ n − r ′ = kn ⇔ r − r ′ = n(k − q + q ′ )
06r,r ′ <n
⇔ r ≡ r ′ [n] ⇔ r = r′ ,
et le résultat est ainsi démontré. ♦
Corollaire 1 : Z/nZ = {0, 1, . . . , n − 1}, et |Z/nZ| = n.
démonstration : Par le théorème précédent, r ∈ x est unique. Donc, par transitivité, tous les éléments
congrus à r modulo n le sont aussi à x modulo n, ce qui nous amène à écrire que r = x. Mais r =
{0, 1, . . . , n − 1}, d’où le résultat.
Proposition 3 : On définit une addition + et une multiplication · sur Z/nZ de la manière suivante :
pour tous α, β ∈ Z/nZ, il existe a, b ∈ Z tels que a = α et b = β, et l’on pose ainsi
α+β =a+b=a+b et α · β = a · b = a · b.
Congruences dans Z. Anneau Z/nZ. 3
démonstration : Il faut vérifier que + et · sont bien définies sur Z/nZ :
α = a = a′ a ≡ a′ [n] prop 2 a + b ≡ a′ + b′ [n] a + b = a′ + b ′
⇒ ⇒ ⇒
β = b = b′ b ≡ b′ [n] a · b ≡ a′ · b′ [n] a · b = a′ · b,
donc cette définition est indépendante du choix des représentants, ce qui la rend pertinente.
Théorème 2 : (Z/nZ, +, ·) est un anneau commutatif.
démonstration : Découle directement du fait que Z soit un anneau commutatif.
14.3 Eléments inversibles
Théorème 3 : x ∈ Z/nZ est inversible si et seulement si x ∧ n = 1.
démonstration : On a les équivalences suivantes :
x inversible dans Z/nZ ⇔ ∃ y ∈ Z/nZ | x · y = 1
⇔ ∃ x, y ∈ Z | x · y ≡ 1 [n]
⇔ ∃ x, y, u ∈ Z | x · y + u · n = 1
Bézout
⇔ x ∧ n = 1.
Théorème 4 : Les propositions suivantes sont équivalentes :
(i) n premier ;
(ii) Z/nZ est intègre ;
(iii) Z/nZ est un corps.
démonstration :
thm 3
(i) ⇒ (iii) : n premier ⇒ ∀ a ∈ {1, . . . , n − 1}, a ∧ n = 1 ⇒ ∀ a ∈ (Z/nZ)∗ , a est inversible
⇒ Z/nZ est un corps.
(ii) ⇒ (i) : On procède par contraposée : n non premier ⇒ ∃ n1 , n2 ∈ N | (n1 n2 = n et 1 < n1 , n2 <
n) ⇒ n1 · n2 = n = 0. Mais n1 6= 0 et n2 6= 0, donc Z/nZ n’est pas intègre.
Enfin, puisque tout corps est intègre, le théorème est démontré.
4 Congruences dans Z. Anneau Z/nZ.
14.4 Applications
14.4.1 Théorème des restes chinois
Théorème 5 (des restes chinois) : Soient p, q ∈ N∗. Alors
p∧q =1 ⇔ Z/pZ × Z/qZ ∼
= Z/pqZ.
démonstration :
"=⇒" : Soit f l’application définie par
f : Z −→ Z/pZ × Z/qZ
x 7−→ (x, x
e).
On vérifie aisément grâce à la proposition 3 que f est un morphisme d’anneaux.
Déterminons alors son noyau. Soit x ∈ Z tel que f (x) = (0, e 0). Alors on a simultanément x = 0
et x e
e = 0, c’est-à-dire p et q divisent x. Or p ∧ q = 1 par hypothèse, donc la produit pq divise aussi
x, de sorte que x ∈ pqZ, et le noyau recherché n’est autre que pqZ.
L’application quotient f : Z/pqZ −→ Z/pZ × Z/qZ est donc injective, et les deux ensembles ont
même cardinal, donc f est bijective, d’où Z/pqZ ∼
= Z/pZ × Z/qZ.
"⇐=" : Soit g l’isomorphisme (d’après le sens direct) d’anneau défini par
g : Z/pqZ −→ Z/pZ × Z/qZ
b 7−→ (x, x
x e).
Supposons p ∧ q = d 6= 1. Alors il existe p′ , q ′ tels que p = p′ d et q = q ′ d. Puisque g(b
1) = (1, e1)
1 est d’ordre pq pour l’addition, il doit en être de même pour (1, e
et b 1).
Or dp′ q ′ (1, e
1) = q ′ (p1), p′ (qe
1 = (0, e
0), donc (1, e1) est d’ordre inférieur ou égal à dp′ q ′ < pq.
On aboutit à une contradiction qui prouve bien que p ∧ q = 1.
14.4.2 Petit théorème de Fermat
Théorème 6 (de Fermat) : Si p est premier, alors pour tout a ∈ Z, ap ≡ a [p].
p
démonstration : Puisque p est premier, alors pour tout k ∈ {1, . . . , p − 1}, p divise k . En effet,
p p
k = p(p − 1) · · · (p − k + 1)/k! ⇔ k! k = p(p − 1) · · · (p − k + 1). Comme p est premier, il est
premier avec tout entier le précédent, donc p ∧ k = 1, et il vient que p ne divise pas k!. Par le théorème
de Gauss, il s’ensuit que p divise pk .
Procédons ensuite par récurrence sur l’entier a ∈ N.
• Initialisation : Si a = 0, le résultat est évident.
• Hérédité : Supposons que (a − 1)p ≡ a − 1 [p].
p
X p H.R.
ap = (a − 1 + 1)p = k (a − 1)k ≡ (a − 1)p + 1 [p] ≡ a − 1 + 1 [p] ≡ a [p].
k=0
Congruences dans Z. Anneau Z/nZ. 5
Si a ∈ (−N)∗ , alors −a ∈ N ⇒ (−a)p ≡ −a [p]. Supposons alors un instant p 6= 2 de sorte que
la condition p premier soit équivalente à dire que p est impair. La relation de congruence précédente
devient alors −ap ≡ −a [p] ⇔ ap ≡ a [p]. Enfin, si p = 2, alors quelque soit a, l’entier ap − a est pair,
et donc divisible par p.
14.4.3 Théorème de Wilson
Théorème 7 (de Wilson) : Soit p > 2 un entier naturel. Alors p est premier si et seulement si (p −
1)! ≡ −1 [p].
démonstration :
"=⇒" : Supposons p non premier, de sorte qu’il existe d, p′ tel que p = dp′ . d est strictement compris
entre 1 et p, et puisque p divise (p − 1)! + 1 par hypothèse, d le divise aussi. Or d est l’un des
facteurs de (p − 1)! donc d divise (p − 1)!, et on arrive ainsi à la contradiction que d divise 1.
Finalement, p est premier.
"⇐=" : Puisque p est premier, a ne le divise par. D’après le petit théorème de Fermat, ap ⇔ a [p] ⇔
a(ap−1 − 1) ≡ 0 [p] ⇒ ap−1 ≡ 1 [p] ⇔ ap−1 = 1. Par suite, le polynôme X p−1 − 1 admet pour
racines tous les éléments de (Z/pZ)∗ et, le produit des racines valant −1, il vient que (p − 1)! +
1 = 0, c’est-à-dire (p − 1)! ≡ −1 [p].
14.4.4 Critères de divisibilité
En base 10, tout entier naturel N s’écrit sous la forme N = a0 + 10a1 + · · · + 10n an .
Puisque 10 ≡ 1 [3/9], 10n ≡ 1 [3/9] pour tout n, donc N ≡ a0 + a1 + · · · + an [3/9]. On en tire le critère
suivant : « Un nombre est divisible par 3 (ou 9) si la somme de ses chiffres l’est ».
De même, 10 ≡ −1 [11] ⇒ ∀ n ∈ N, 10n ≡ (−1)n [11] ⇒ N ≡ a0 − a1 + a2 + · · · + (−1)n an [11]. D’où
le critère suivant : « Un nombre est divisible par 11 si la différence de la somme de ses chiffres de rang
pairs par celle de ses chiffres de rang impairs l’est ».
Exercice : Dire si les nombres suivants sont multiples de 3, 9 et/ou 11 :
324, 1948617, 18690045, 2310905821257, 1073741824.
Solution : On récapitule ceci selon le tableau suivant (Σp désigne la somme des chiffres de rang pairs et Σi celle des chiffres de
rangs impairs) :
6 Congruences dans Z. Anneau Z/nZ.
Nombre 324 1948617 18690045 2310905821257 1073741824
Sommes des chiffres 9 36 33 45 37
Divisible par 3 ? oui oui oui oui non
Divisible par 9 ? oui oui non oui non
Σp 2 18 22 17 19
Σi 7 18 11 28 18
|Différence| 5 0 11 11 1
Divisible par 11 ? non oui oui oui non
Ces critères permettent aussi de commencer la décomposition d’un nombre en produit de facteurs premiers, mais ceci sera l’objet
de la leçon n˚ 13. . . ♦
