arithmétique modulaire

Une horloge recommence à 0 après 11, puis après 23, et ainsi de suite. Sur un cadran de 5 positions, 17 et 32 conduisent tous deux à la position 2 : ils laissent le même reste quand on les divise par 5. L'arithmétique modulaire conserve ce qui est commun à ces nombres et ignore le nombre de tours complets.

Le nombre 5 est le module : on compte modulo 5. Les nombres qui donnent le reste 2, comme 2, 7, 12, 17 et 32, appartiennent à une même classe de congruence. Cette manière de compter réapparaît dans les calendriers, les codes et les calculs informatiques.

Soit n un entier naturel strictement positif, appelé module. Deux entiers a et b sont congrus modulo n lorsque leur différence est divisible par n. Cette relation se note $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)a\; \backslash equiv\; b\; \backslash pmod\{n\}$. Elle équivaut à dire que les divisions euclidiennes de a et b par n donnent le même reste, choisi parmi 0, 1, …, n − 1.

Une classe de congruence rassemble tous les entiers qui ont le même reste modulo n. Il y a exactement n classes, représentées par les restes 0 à n − 1. L'arithmétique modulaire calcule avec ces classes : l'addition et la multiplication sont bien définies, car remplacer un nombre par un autre qui lui est congru modulo n ne change pas le résultat modulo n.

Pour n = 5, 17 et 32 sont congrus puisque leur différence vaut 15, qui est divisible par 5. On écrit alors $17\equiv 32(\mathrm{m}\mathrm{o}\mathrm{d}5)17\; \backslash equiv\; 32\; \backslash pmod\{5\}$, et les deux nombres représentent la classe du reste 2. Le choix d'un représentant compris entre 0 et n − 1 est une convention pratique, non une nouvelle classe.

Pour vérifier la relation entre 17 et 32 modulo 5, on effectue les deux divisions euclidiennes. Le dividende est le nombre étudié, le diviseur est 5, et le reste doit être compris entre 0 et 4.

La première division donne 17 = 5 × 3 + 2. La seconde donne 32 = 5 × 6 + 2. Les deux restes valent donc 2, ce qui établit $17\equiv 32(\mathrm{m}\mathrm{o}\mathrm{d}5)17\; \backslash equiv\; 32\; \backslash pmod\{5\}$.

On peut contrôler le même résultat autrement : 32 − 17 = 15, puis 15 = 5 × 3. La différence est un multiple de 5. Les nombres 17 et 32 sont ainsi deux représentants d'une même classe, tandis que 18, qui laisse le reste 3, appartient à une autre classe.

Pour calculer modulo 5, on peut remplacer chaque entier par son reste entre 0 et 4. Ainsi, l'addition de 17 et 9 devient l'addition de 2 et 4, puis le reste de 6 modulo 5 est 1. Le résultat s'écrit $17+9\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}5)17+9\; \backslash equiv\; 1\; \backslash pmod\{5\}$.

La même réduction fonctionne pour une multiplication : 17 × 9 est congru à 2 × 4, donc à 8, puis à 3 modulo 5. On peut donc garder seulement les restes à chaque étape d'un calcul long, à condition de conserver le même module strictement positif.

Le reste de la division de 17 par 5 est le nombre 2. La congruence est une relation entre deux entiers : 17 et 32 sont congrus modulo 5. Le module est ici le nombre 5 qui fixe les classes considérées ; « modulo 5 » désigne la relation ou le cadre de congruence.

Dire que 17 vaut 2 modulo 5 est une façon abrégée de dire que 17 représente la classe de congruence du reste 2. Cela ne signifie pas que 17 et 2 sont égaux comme entiers : ils diffèrent de 15. La division euclidienne, elle, produit un quotient et un reste uniques pour un diviseur positif.

Le module doit être un entier strictement positif dans la définition usuelle. Avec le module 0, la divisibilité par 0 n'offre pas le même cadre, et un module négatif est généralement remplacé par sa valeur absolue. Il faut aussi distinguer la congruence, qui accepte des représentants quelconques, du reste canonique, choisi entre 0 et n − 1.

La réduction modulo n respecte l'addition, la soustraction et la multiplication. Elle ne permet pas de diviser librement : par exemple, annuler un facteur dans une congruence exige des conditions supplémentaires sur ce facteur et sur n. Une congruence comme $2x\equiv 2y(\mathrm{m}\mathrm{o}\mathrm{d}6)2x\; \backslash equiv\; 2y\; \backslash pmod\{6\}$ n'autorise pas à conclure directement que x et y sont congrus modulo 6.

Enfin, deux nombres ayant le même reste pour un module donné peuvent avoir des restes différents pour un autre module. L'égalité de 17 et 32 modulo 5 ne dispense donc pas de préciser le module, et elle ne devient pas une égalité ordinaire entre les deux entiers.

Les classes de congruence modulo n forment l'anneau des entiers modulo n, souvent noté $\mathbb{Z}\mathrm{/}n\mathbb{Z}\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$. Lorsque n est premier, tout élément non nul de cet anneau possède un inverse multiplicatif ; cette propriété est au cœur de plusieurs méthodes de cryptographie.

Les congruences permettent aussi d'étudier les puissances, les critères de divisibilité et les solutions d'équations entières. Le théorème chinois des restes relie des informations modulo plusieurs entiers premiers entre eux et reconstruit une classe modulo leur produit. Ces prolongements gardent la même idée directrice : ne retenir que l'information périodique imposée par le module.