Congruences modulo n : a ≡ b [n] si a et b ont même reste

Définition

$a$ est congru à $b$ modulo $n$ si $a - b$ est divisible par $n$ :

$a \equiv b \pmod{n} \iff n \mid (a - b)$

Équivaut à : $a$ et $b$ ont le même reste dans la division par $n$.

Exemples

• $17 \equiv 5 \pmod{12}$ (car $17 - 5 = 12$).
• $-3 \equiv 4 \pmod{7}$ (car $-3 - 4 = -7$).
• $25 \equiv 1 \pmod{24}$ (utile pour les heures !).

Opérations : elles se conservent

Si $a \equiv a' \pmod n$ et $b \equiv b' \pmod n$ :

• Addition : $a + b \equiv a' + b' \pmod n$
• Soustraction : $a - b \equiv a' - b' \pmod n$
• Multiplication : $a \times b \equiv a' \times b' \pmod n$
• Puissance : $a^k \equiv (a')^k \pmod n$

⚠️ La division n’est pas toujours possible !

Application 1 : critère de divisibilité

Pour tester si $n$ est divisible par $9$ : somme des chiffres.

Pourquoi ? Car $10 \equiv 1 \pmod 9$, donc $10^k \equiv 1 \pmod 9$. Un nombre est congru à la somme de ses chiffres mod 9.

Application 2 : calculer un reste énorme

Calculer $2^{100}$ mod 5.

$2^4 = 16 \equiv 1 \pmod 5$.

$100 = 4 \times 25$, donc $2^{100} = (2^4)^{25} \equiv 1^{25} = 1 \pmod 5$.

Reste = 1.

Application 3 : jour de la semaine

Aujourd’hui = mercredi. Dans 100 jours ?

$100 = 14 \times 7 + 2$, donc $100 \equiv 2 \pmod 7$. Mercredi + 2 = vendredi.

Petit théorème de Fermat

Si $p$ premier et $a$ non divisible par $p$ :

$a^{p - 1} \equiv 1 \pmod p$

Utilisation : simplifier des puissances modulo un nombre premier.

Erreurs classiques

1. Diviser dans une congruence sans PGCD = 1 avec $n$.
2. Écrire $a \equiv b \pmod n$ quand $a - b$ n’est pas divisible par $n$.
3. Oublier que les restes sont positifs ($0 \leq r < n$).

?À toi de jouer

46 mod 7 = ?

A.4B.6C.7D.0

Valider