Qu’est-ce qu’une congruence modulo un entier ?
Réponse courte
Pour n entier strictement positif, a ≡ b modulo n signifie que n divise a − b. Autrement dit, a et b ont le même reste dans leur division euclidienne par n.
Comprendre
Une égalité de restes
Pour des entiers a et b et un entier n > 0, on écrit a ≡ b [n] lorsque a − b est un multiple de n. Cela équivaut à dire que les divisions euclidiennes de a et b par n donnent le même reste. La congruence compare des classes de nombres ; elle ne signifie pas que a = b.
Lire et vérifier l’écriture
Comme 17 − 2 = 15 est divisible par 5, 17 ≡ 2 [5]. De même, −3 − 2 = −5 est multiple de 5, donc −3 ≡ 2 [5]. Les deux nombres ont le reste 2 modulo 5, même si l’un est négatif.
Calculer avec les restes
On peut additionner ou multiplier des congruences de même module : remplacer un nombre par un autre ayant le même reste ne modifie pas le résultat modulo n. Par exemple, 17 + 8 ≡ 2 + 3 ≡ 0 [5], donc 25 est divisible par 5. En revanche, la division ou l’annulation d’un facteur n’est pas automatique ; elle exige des conditions supplémentaires sur le facteur et le module.
Exemples
- 17 ≡ 2 [5], car 17 − 2 = 15 = 3 × 5.
- −3 ≡ 2 [5], car −3 − 2 = −5 est un multiple de 5.
- 17 + 8 ≡ 2 + 3 ≡ 0 [5] ; ainsi 25 est divisible par 5.
Pièges fréquents
- Lire a ≡ b [n] comme une égalité ordinaire : 17 et 2 ne sont pas égaux, ils ont seulement le même reste modulo 5.
- Croire que le reste d’un entier négatif est forcément négatif : avec un diviseur positif, le reste euclidien est toujours entre 0 inclus et n exclu.
