Deux nombres entiers $a$ et $b$ sont dits congrus modulo $n$ si $n$ divise la différence $a - b$. Cela est souvent noté :

où $n$ est un entier positif appelé le modulus. En termes simples, $a$ et $b$ laissent le même reste lorsqu'ils sont divisés par $n$.

Exemples :

1. $17 \equiv 5 \pmod{6}$ car la différence $17 - 5 = 12$ est divisible par 6.

2. $25 \equiv 4 \pmod{7}$ car $25$ et $4$ donnent tous deux un reste de $4$ lorsqu'ils sont divisés par $7$.

Les systèmes de chiffrement comme RSA utilisent des congruences pour coder et décoder des messages.

Le calcul des fonctions de hachage pour la vérification de l'intégrité des données ou pour des structures de données comme les tables de hachage utilise également des congruences.

Propriétés de base :

• Addition et Soustraction:

  Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors $a + c \equiv b + d \pmod{n}$ et $a - c \equiv b - d \pmod{n}$.

• Multiplication:

  Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors $ac \equiv bd \pmod{n}$.

• Puissance:

  Si $a \equiv b \pmod{n}$, alors pour tout entier positif $k$, $a^k \equiv b^k \pmod{n}$.
  (la réciproque est fausse).