Congruences et arithmétique modulaire

La relation de congruence

Si aujourd’hui est un lundi, dans $15$ jours ce sera un mardi, et dans $1000$ jours ce sera un dimanche : pour le savoir, il n’est pas nécessaire de compter les jours un par un, car il suffit de connaître le reste de la division du nombre de jours par $7$. De même, $5$ heures après $9$ heures, il est $2$ heures sur une horloge de $12$ heures, et le dernier chiffre d’un produit ne dépend que des derniers chiffres des facteurs. Dans les trois cas, on calcule avec des restes et on oublie le quotient. La leçon sur la divisibilité et la division euclidienne a réparti les entiers en classes selon le reste qu’ils laissent dans la division par un entier naturel, et a démontré que le reste d’une somme, d’un produit et d’une puissance ne dépend que des restes des données. Cette leçon donne à ces observations un langage propre, celui des congruences, que Gauss introduisit en 1801 dans ses Disquisitiones Arithmeticae, et en fait un instrument de calcul. Comme dans cette leçon, les entiers sont utilisés par anticipation, avec les règles de leur arithmétique et de leur ordre, qui sont fondées dans la leçon sur les entiers relatifs.

Définition (congruence). Soit $n$ un entier naturel. Deux entiers $a$ et $b$ sont congrus modulo $n$ si $n$ divise leur différence $a - b$. On écrit $a \equiv b \pmod{n}$ et on lit « $a$ est congru à $b$ modulo $n$ » ; l’entier naturel $n$ s’appelle le module de la congruence.

Ainsi, $17 \equiv 2 \pmod{5}$, car $17 - 2 = 15$ ; $-3 \equiv 9 \pmod{4}$, car $-3 - 9 = -12$ ; et un entier est pair exactement lorsqu’il est congru à $0$ modulo $2$. Que $a$ soit multiple de $n$ s’écrit maintenant $a \equiv 0 \pmod{n}$. Avec le module $1$, tous les entiers sont congrus entre eux, car $1$ divise tout entier ; ce cas est sans intérêt, et dans les exemples le module sera au moins égal à $2$. Le signe $\equiv$, à trois traits, rappelle celui de l’égalité parce que, comme on le verra, la congruence se comporte presque en tout comme elle ; l’exception, la division, occupera la section sur les inverses.

La définition par la différence est la plus commode pour démontrer, mais l’intuition des exemples initiaux est celle du reste. La proposition suivante assure que les deux disent la même chose ; son contenu a déjà été observé, sous une autre forme, dans la leçon sur la divisibilité, pour fonder les critères de divisibilité, et il est démontré ici en détail.

En particulier, tout entier est congru modulo $n$ à son reste, qui est l’un des $n$ entiers $0, 1, \ldots, n - 1$, et à un seul d’entre eux, car deux de ces entiers sont leurs propres restes et, s’ils sont distincts, laissent des restes distincts. Calculer modulo $n$ consiste à remplacer chaque nombre par un représentant commode de sa colonne : le reste, ou parfois un petit nombre strictement négatif, comme $-1$ au lieu de $n - 1$.