congruence modulo n

Imaginez un cadran numéroté de 0 à 11. En partant de 0, avancer de 14 pas conduit au repère 2. Avancer de 38 pas conduit au même repère, car chaque tour complet compte 12 pas.

Les nombres 14 et 38 sont donc congrus modulo 12. Ils ne sont pas égaux, mais la division par 12 leur laisse le même reste, 2. Leur écart, 24, correspond aussi à deux tours complets.

Soit n un entier strictement positif, appelé module, et soient a et b deux entiers relatifs. On dit que a est congru à b modulo n lorsqu'ils ont le même reste dans la division euclidienne par n. On écrit a ≡ b (mod n). Le critère équivalent est que n divise leur différence : $n\mid (a-b)n\backslash mid(a-b)$. Ainsi, 38 ≡ 14 (mod 12), car 38 − 14 = 24 et 12 divise 24.

La congruence modulo n est une relation d'équivalence : tout entier est congru à lui-même, la relation peut être inversée et deux congruences successives peuvent être enchaînées. Tous les entiers congrus à a forment sa classe de congruence, ou classe résiduelle. Pour n positif, il existe exactement n classes, représentées par les restes 0, 1, …, n − 1. Modulo 12, la classe de 2 contient notamment −10, 2, 14, 26 et 38.

L'addition et la multiplication ne dépendent pas du représentant choisi : elles définissent des opérations sur les classes. L'ensemble obtenu est l'anneau ℤ/nℤ. Lorsque n est premier, chaque classe non nulle possède un inverse multiplicatif ; ℤ/nℤ est alors un corps.

On veut déterminer si 38 et 14 sont congrus modulo 12. Les données sont les deux entiers 38 et 14, ainsi que le module 12. Deux contrôles indépendants permettront de vérifier le résultat.

1. Effectuer les divisions euclidiennes : 38 = 3 × 12 + 2 et 14 = 1 × 12 + 2. Les deux restes valent 2.

2. Conclure avec les restes : 38 et 14 appartiennent à la même classe résiduelle modulo 12. On écrit donc 38 ≡ 14 (mod 12).

3. Refaire le test par la différence : $38-14=24=2\times 1238-14=24=2\backslash times12$. Comme 24 est un multiple de 12, le critère de divisibilité confirme la congruence.

4. Contrôler la classe : −10, 2, 14, 26 et 38 s'obtiennent en ajoutant à 2 un multiple entier de 12. Le passage d'un terme au suivant ne change donc jamais le reste modulo 12.

Pour tester rapidement deux entiers, on soustrait l'un à l'autre et on cherche si le module divise exactement la différence. Ce test évite deux divisions ; les divisions euclidiennes restent préférables si l'on veut aussi connaître le reste commun.

Pour calculer une longue somme ou un produit modulo n, on peut remplacer chaque entier par son reste, puis réduire de nouveau le résultat. Par exemple, modulo 12, 14 et 38 ont tous deux pour reste 2 : leur somme 14 + 38 = 52 se réduit donc comme 2 + 2, et donne le reste 4. Si la valeur entière exacte est nécessaire, il faut conserver le calcul ordinaire, car une classe résiduelle ne retient que le reste.

Pour décrire un phénomène périodique, comme un cadran de 12 positions, la congruence identifie les nombres qui atteignent le même repère après des tours complets. Si le nombre de tours compte, la congruence seule ne suffit pas : 14 et 38 ont le même repère, mais diffèrent de deux tours.

Égalité et congruence. Une égalité affirme que deux entiers sont identiques ; une congruence dépend d'un module et affirme seulement que leur différence en est un multiple. Ainsi, 38 ≠ 14 mais 38 ≡ 14 (mod 12).

Divisibilité et congruence. Dire que 12 divise 24 compare directement deux entiers. Dire que 38 est congru à 14 modulo 12 compare leurs classes ; le test de divisibilité porte alors sur leur différence 38 − 14.

Reste et classe résiduelle. Le reste 2 est l'unique représentant compris entre 0 et 11 de sa classe modulo 12. La classe elle-même contient une infinité d'entiers, dont −10, 14 et 38.

Le module doit être fixé. La congruence 38 ≡ 14 est vraie modulo 12, mais fausse modulo 5, car 24 n'est pas divisible par 5. Une écriture sans module ne permet donc aucun verdict.

Les modules dégénérés demandent une convention. Modulo 1, tous les entiers ont le reste 0 : il n'existe qu'une classe. La division euclidienne modulo 0 n'est pas définie. Pour un module négatif, on emploie habituellement sa valeur absolue afin de retrouver des restes compris entre 0 et |n| − 1.

On ne simplifie pas toujours un facteur. Modulo 12, 2 × 1 ≡ 2 × 7, puisque 2 et 14 ont le même reste. Pourtant, 1 n'est pas congru à 7 modulo 12. Avant de simplifier par un facteur, il faut vérifier que ce facteur possède un inverse modulo le module.

Un représentant n'est pas forcément un reste. Le nombre −10 appartient à la classe de 2 modulo 12, mais le reste euclidien choisi pour représenter cette classe est 2. Il faut réduire le représentant dans l'intervalle de 0 à 11 lorsqu'un reste canonique est demandé.

Division euclidienne — Retrouver le quotient et le reste qui permettent de tester une congruence.

relation d'équivalence — Voir pourquoi réflexivité, symétrie et transitivité organisent les entiers en classes.

arithmétique modulaire — Prolonger la congruence par le calcul sur les classes résiduelles.

nombre premier — Relier la primalité du module à l'existence des inverses non nuls.