Les congruences

Une horloge affiche 14 h, on avance de 3 heures : elle affiche 17 h. On avance encore de 10 heures : elle n'affiche pas 27 h, mais 3 h. On vient de calculer modulo 24.

La définition

Deux entiers a et b sont congrus modulo n s'ils ont le même reste dans la division par n. On écrit :

a ≡ b  (mod n)

Ce qui revient à dire que n divise a - b.

27 ≡ 3   (mod 24)      car 27 - 3 = 24
38 ≡ 12  (mod 26)      car 38 - 12 = 26

C'est exactement l'opération qui faisait revenir Z sur A dans le chiffre de César.

Ce qui se conserve

L'intérêt, c'est qu'on peut calculer avant ou après réduction, le résultat est le même :

si  a ≡ a'  et  b ≡ b'   (mod n)
alors  a + b ≡ a' + b'   (mod n)
et     a × b ≡ a' × b'   (mod n)

Concrètement, on peut réduire à chaque étape sans changer le résultat final. C'est ce qui rend les calculs cryptographiques praticables : les nombres ne grossissent jamais au-delà de n.

17 × 23 (mod 5)  =  2 × 3 (mod 5)  =  6 (mod 5)  =  1

Un piège

L'addition et la multiplication passent au modulo, mais pas la division. Écrire a / b (mod n) n'a pas de sens en général. Il faut passer par la notion d'inverse — c'est l'objet de la leçon suivante.