Définitions

n désignant un entier relatif positif non nul. On dit que deux entiers relatifs x et y sont 'congrus modulo n' (notation x ≡ y [n]) si la différence x-y est un multiple de n.
On voit tout de suite que cette définition est équivalente à:
x et y on même reste dans la division par n.
On voit aussi que:
(x ≡ y [n]) ⇔ (x-y ≡ 0 [n])
Par exemple 8 et 15 sont congrus modulo 7. Mais 5 et 6 ne sont pas congrus modulo 4.

Propriétés

∀ n ≠ 0 la congruence modulo n est une relation d'équivalence sur n.
Pour cette relation il y a exactement n classes d'équivalence qui sont:
Toutes ces classes possèdent un nombre infini d'éléments.

Toute relation de congruence modulo n est compatible avec l'addition.
Cela veut dire que si  x ≡ y [n] et x' ≡ y' [n] alors  (x+x') ≡ (y+y') [n].
En effet (x+x')-(y+y')=(x-y)+(x'-y')    et  ( (x-y) ∈ nℤ) ∧( (x'-y') ∈ nℤ) ⇒ ((x-y)+(x'-y') ∈ nℤ) car nℤ est un sous-groupe additif de ℤ
Toute relation de congruence modulo n est compatible avec la multiplication.
Cela veut dire que si  x ≡ y [n] et x' ≡ y' [n] alors  (xx') ≡ (yy') [n].
En effet (xx')-(yy')=(x-y)y'+x(x'-y')    et  ( (x-y) ∈ nℤ) ∧( (x'-y') ∈ nℤ) ⇒ ((x-y)y'+x(x'-y') ∈ nℤ) car nℤ est un idéal de ℤ

Conséquences

Supposons x ≡ a [9] et y ≡ b [9] alors xy ≡ ab [9]. C'est là l'origine de la fameuse 'preuve par neuf' des classes primaires de nos pères et grands-pères. Cette 'preuve' n'est d'ailleurs nullement une preuve. Elle est une preuve a contrario, c'est à dire que si le test échoue alors le résultat de la multiplication est faux à coup sûr, mais si le test passe, cela veut dire seulement que le résultat exact et le résultat trouvé diffèrent seulement d'un multiple de 9. Il y a donc environ 9/10 chances pour que l'opération soit exacte.
Mais on peut croiser les tests.
Examinons par exemple le test de divisibilité par 11.
Ce test est basé sur la remarque que 10n est congru à 1 modulo 11 pour n pair  et à  -1 modulo 11 pour n impair. Le test de divisibilité par 11 est donc facile à mettre en oeuvre.
On fait la somme alternée des chiffres du nombres en  mettant des signes sur les chiffres de rang pair et des - sur les chiffres de rang impair.
Par exemple pour 17845 on calcule (5+8+1)-(4+7)= 14-11=3 on sait donc que le reste de 17845 dans la division par 11 est 3.
Maintenant si une multiplication passe le test de la preuve par 9 et conjointement celui de la preuve par 11, la différence entre le produit réel et le produit trouvé est un multiple de 9 et un multiple de 11, donc un multiple de leur ppcm qui est 99 car ils sont premiers entre eux. On voit que dans ce cas (tests croisés) la probabilité de la justesse de l'opération augmente considérablement.