Congruence modulo n
Définition

Soit n un entier naturel2. Deux entiers relatifs a et b sont dits congrus modulo n si leur
différence est divisible par n, c'est-à-dire si a est de la forme b + kn avec k entier3,4,5.

On exclut désormais le cas trivial n = 0 (la congruence modulo 0 est l'égalité ; on peut
accessoirement remarquer que modulo 1, deux entiers quelconques sont équivalents5).

Deux entiers a et b sont alors congrus modulo n si et seulement si le reste de la division
euclidienne de a par n est égal à celui de la division de b par n.

Notation

Le caractère utilisé pour exprimer la congruence de deux entiers est ≡.

On peut exprimer que a et b sont congruents modulo n sous quatre formes : a ≡ b (n) ; a ≡ b
[n] ; a ≡ b (mod n) ; a ≡ b mod n (notation de Gauss)3. La dernière est celle préconisée par la
norme ISO 80000-2 de 2009.

Quelle que soit la notation choisie, ceci se lit « a est congru à b modulo n ».

Par exemple : 26 ≡ 12 (7) car 26 – 12 = 14, multiple de 7 (critère 1 ci-dessus) ; et 26 et 12 ont
tous les deux 5 comme reste dans la division par 7 (critère 2).

Remarques :

 Bien que le caractère typographique ≡ soit depuis longtemps disponible, il est encore
parfois remplacé par =3.
 Lorsque la congruence est notée (n), cette notation peut parfois engendrer une
confusion avec des facteurs sous parenthèses. Les notations [n], (mod n) et mod n
permettent d'éviter cette ambiguïté.

Propriétés

Relation d'équivalence

La congruence modulo n a les propriétés suivantes :

 réflexivité : pour tout entier a, a ≡ a (n) ;
 symétrie : pour tous entiers a et b, a ≡ b (n) ⇔ b ≡ a (n) ;
 transitivité : pour tous entiers a, b et c, si a ≡ b (n) et b ≡ c (n) alors a ≡ c (n).

Il s'agit donc d'une relation d'équivalence.

Propriétés algébriques

Elle a de plus des propriétés algébriques remarquables :
Si a1 ≡ b1 (n) et a2 ≡ b2 (n), alors

 a1 + a2 ≡ b1 + b2 (n) et
 a1a2 ≡ b1b2 (n).

Démonstration6,7

Si a1 – b1 et a2 – b2 sont multiples de n alors (a1 + a2) – (b1 + b2) et a1a2 – b1b2 aussi, puisque

 (a1 + a2) – (b1 + b2) = (a1 – b1) + (a2 – b2) et
 a1a2 – b1b2 = a1a2 – a1b2 + a1b2 – b1b2 = a1(a2 – b2) + (a1 – b1)b2.

(On en déduit facilement d'autres, comme : si a ≡ b (n) alors ac ≡ bc (n) pour tout entier c et
aq ≡ bq (n) pour tout entier q > 0.)

On peut parler d'une certaine « compatibilité » avec les opérations d'addition et de
multiplication des entiers, c'est-à-dire de « compatibilité » avec la structure d'anneau de (ℤ, +,
*). Ces quelques propriétés vont nous permettre de définir le domaine de l'arithmétique
modulaire : les ensembles quotients ℤ/nℤ.