La congruence des entiers relatifs Congruence

1. Le terme « modulo »

Si n est un entier naturel non nul, on dit que deux entiers relatifs a et b sont congrus modulo n s’ils ont le même reste euclidien quand on les divise par n. On écrit alors a ≡b [n] ou encore a = b [modulo n].

Exemple : quand on divise 14 et 17 par 3, on obtient un reste égal à 2, donc 14 ≡ 17 [3].

« Modulo » vient du latin « modulus » qui signifie « mesure ». Modulo 26 signifie « selon le module 26 ». « Congru » provient également du verbe latin « congruere », « s’accorder ».

2. Calcul des restes modulo n

Soit z un entier relatif et soit n un entier naturel non nul. Le reste de la division euclidienne de z par n est un entier naturel r tel que 0 ≤ r <n. À titre d’exemple, cherchons le reste de la division euclidienne de -155 par 9. On a 155=17×9+2 d’où -155=-17×9-2. Comme 2=9-7, on peut écrire -155=-17×9-(9-7) d’où...