La congruence sur les entiers est une relation pouvant unir deux entiers. Elle fut pour la première fois étudiée en tant que structure par le mathématicien allemand Carl Friedrich Gauss à la fin du XVIIIe siècle et présentée au public dans ses Disquisitiones arithmeticae en 1801. Elle est aujourd'hui couramment utilisée en théorie des nombres, en algèbre générale et en cryptographie. Elle représente le fondement d'une branche mathématique appelée arithmétique modulaire.
C'est une arithmétique où l'on ne raisonne pas directement sur les nombres, mais sur leurs restes respectifs par la division euclidienne par un certain entier : le module (qui sera noté n tout au long de l'article). On parle alors de congruence.
L'histoire, les outils développés pour l'arithmétique modulaire, ainsi que les applications sont traités dans l'article « Arithmétique modulaire ». Une analyse plus exhaustive et moins didactique est proposée dans l'article « Anneau ℤ/nℤ ».
L'arithmétique modulaire est un système arithmétique d'entiers modifiés, où les nombres sont « abaissés » lorsqu'ils atteignent une certaine valeur.
Donnons comme exemple, l'« arithmétique de l'horloge » qui se réfère à l'« addition » des heures indiquées par la petite aiguille d'une horloge : concrètement, si nous commençons à 9 heures et ajoutons 4 heures, alors plutôt que de terminer à 13 heures (comme dans l'addition normale), nous sommes à 1 heure. De la même manière, si nous commençons à minuit et nous attendons 7 heures trois fois de suite, nous nous retrouvons à 9 heures (au lieu de 21).
Fondamentalement, quand nous atteignons 12, nous recommençons à zéro ; nous travaillons modulo 12. Pour reprendre l'exemple précédent, on dit que 9 et 21 sont congrus modulo[N 1] 12. Les nombres 9, 21, 33, 45, etc. sont considérés comme égaux lorsqu'on travaille modulo 12.
Pour généraliser, nous pouvons imaginer une horloge qui contient un nombre arbitraire d'heures, et faire des calculs avec un nouveau module.
Définition[1],[2],[3] — Soit n un entier naturel[4].
Deux entiers relatifs a et b sont dits congrus modulo n si leur différence est divisible par n, c'est-à-dire si a est de la forme b + kn avec k entier.
On exclut désormais le cas trivial n = 0 (la congruence modulo 0 est l'égalité ; on peut accessoirement remarquer que modulo 1, deux entiers quelconques sont équivalents[3]).
Définition équivalente si n > 0 — Soit n un entier naturel non nul.
Deux entiers a et b sont dits congrus modulo n si le reste de la division euclidienne de a par n est égal à celui de la division de b par n.
Le caractère utilisé pour exprimer la congruence de deux entiers est ≡.
On peut exprimer que a et b sont congruents modulo n sous quatre formes :
La dernière est celle préconisée par la norme ISO/CEI 80000-2 de 2009.
Quelle que soit la notation choisie, ceci se lit « a est congru à b modulo n ».
Par exemple : 26 ≡ 12 (7) car 26 – 12 = 14, multiple de 7 (définition ci-dessus), ou encore : car 26 et 12 ont tous les deux 5 comme reste dans la division par 7 (définition équivalente ci-dessus).
La congruence modulo n a les propriétés suivantes :
Il s'agit donc d'une relation d'équivalence.
Elle a de plus des propriétés algébriques remarquables[5] :
Si a1 ≡ b1 (n) et a2 ≡ b2 (n), alors
(On en déduit facilement d'autres, comme : si a ≡ b (n) alors ac ≡ bc (n) pour tout entier c et aq ≡ bq (n) pour tout entier q ≥ 0.)
On peut parler d'une certaine « compatibilité » avec les opérations d'addition et de multiplication des entiers, c'est-à-dire de « compatibilité » avec la structure d'anneau de (ℤ, +, ×). Ces quelques propriétés vont nous permettre de définir le domaine de l'arithmétique modulaire : les ensembles quotients ℤ/nℤ.
Les propriétés précédentes montrent que deux nombres congrus entre eux modulo n sont interchangeables dans une addition ou une multiplication, lors d'une congruence modulo n. L'idée vient alors de regrouper tous les nombres congrus entre eux modulo n dans une même classe que l'on appelle une classe d'équivalence et de ne travailler qu'avec un représentant particulier de cette classe. Comme tous les nombres de la même classe ont le même reste dans la division par n, on privilégie les restes dans la division par n et l'on travaille sur un ensemble noté ℤn ou ℤ/nℤ composé des n éléments ou plus simplement {0, 1, 2, ... , n – 1} ensemble des restes, ou résidus, modulo n que l'on appelle anneau résiduel[N 2] modulo n ou encore anneau quotient[N 3].
Sur cet ensemble peuvent être définies une addition et une multiplication analogues à celles définies sur l'ensemble ℤ des entiers relatifs :
On peut alors construire les tables d'opérations suivantes :
+ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 | 5 |
1 | 1 | 2 | 3 | 4 | 5 | 0 |
2 | 2 | 3 | 4 | 5 | 0 | 1 |
3 | 3 | 4 | 5 | 0 | 1 | 2 |
4 | 4 | 5 | 0 | 1 | 2 | 3 |
5 | 5 | 0 | 1 | 2 | 3 | 4 |
× | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 | 4 | 5 |
2 | 0 | 2 | 4 | 0 | 2 | 4 |
3 | 0 | 3 | 0 | 3 | 0 | 3 |
4 | 0 | 4 | 2 | 0 | 4 | 2 |
5 | 0 | 5 | 4 | 3 | 2 | 1 |
Ces opérations ont presque les mêmes propriétés que l'addition et la multiplication dans ℤ.
Un ensemble muni de deux opérations ayant ces propriétés s'appelle un anneau.
La seule opération que l'on a l'habitude de faire dans ℤ et qui n'est pas toujours juste dans l'anneau ℤ/nℤ est la simplification.
En effet si 2a = 4 dans ℤ, on sait que a = 2. Mais modulo 6, si 2a = 4, on sait seulement que 2a a pour reste 4 dans la division par 6 donc que a a pour reste 2 dans la division par 3. a peut donc avoir pour reste dans la division par 6 soit 2, soit 5. Plus simplement : on a 2×2 ≡ 2×5 sans pour autant avoir 2 ≡ 5.
De même, la propriété constamment utilisée dans les ensembles de nombres classiques « pour qu'un produit de deux termes soit nul, il faut et il suffit que l'un des termes le soit » n'est pas toujours réalisée dans ℤ/nℤ modulo 6, on a 2×3 ≡ 0, sans que 2 ni 3 soient congrus à 0.
On dit que l'anneau ℤ/6ℤ n'est pas intègre.
La résolution d'équations peut donc devenir un peu problématique quand des multiplications sont en jeu :
On montre que l'équation ax = b d'inconnue x dans ℤ/nℤ possède une unique solution si et seulement si a et n sont premiers entre eux.
La recherche de solutions à l'équation qui peut avoir, selon les valeurs de n et de a, aucune, une, deux solutions, ou même davantage, donne lieu à l'étude des résidus quadratiques et à l'énoncé de la loi de réciprocité quadratique.
La construction de ℤ/nℤ comme anneau quotienté par un idéal et les propriétés algébriques de l'anneau ℤ/nℤ sont traités dans l'article « Anneau ℤ/nℤ ».
De la multiplication dans ℤ/nℤ, il est naturel de s'intéresser aux puissances successives. Il n'y a que n – 1 restes possibles, donc n – 1 valeurs possibles pour ak, on obtient donc nécessairement plusieurs fois la même valeur. Donc, il existe k et m tels que ak et am ont le même reste modulo n. Comme la construction de ak est fondée sur une récurrence, dès que l'on tombe sur un reste déjà rencontré, on sait que la suite des puissances devient cyclique à partir de cette puissance et l'on peut arrêter l'exploration.
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
k = 0 | 1 | 1 | 1 | 1 | 1 | 1 |
k = 1 | 1 | 2 | 3 | 4 | 5 | 6 |
k = 2 | … | 4 | 2 | 2 | 4 | 1 |
k = 3 | … | 1 | 6 | 1 | 6 | … |
k = 4 | … | … | 4 | … | 2 | … |
k = 5 | … | … | 5 | … | 3 | … |
k = 6 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
k = 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
k = 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
k = 2 | … | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 |
k = 3 | … | 8 | 12 | … | 5 | … | 13 | 2 | 9 | … | … | 3 | 7 | … |
k = 4 | … | 1 | 6 | … | … | … | 1 | 1 | … | … | … | 6 | 1 | … |
k = 5 | … | … | 3 | … | … | … | … | … | … | … | … | 12 | … | … |
… | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
k = 8 | 1 | 1 | … | 1 | … | … | 1 | 1 | … | … | 1 | … | 1 | 1 |
Une observation sur les puissances dans ℤ/7ℤ et ℤ/15ℤ montre que, dans le premier cas, pour tout a premier avec 7 (c'est-à-dire non multiple de 7), on a a6 congru à 1 modulo 7 et dans le second cas, les seules suites passant par 1 correspondent à des entiers premiers avec 15 ; il y a 8 entiers premiers avec 15 et l'on remarque que pour a premier avec 15, a8 est congru à 1 modulo 15.
Ces deux observations correspondent à deux théorèmes :