Voir la source de Congruence sur les entiers

{{Voir homonymes|Congruence}}
La '''congruence sur les entiers''' est une relation pouvant relier deux [[Entier relatif|entiers]]. Elle fut pour la première fois étudiée en tant que structure par le [[mathématicien]] [[Allemagne|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é <math>n</math> 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 Z/nZ|Anneau ℤ/''n''ℤ]] ».

== Idée intuitive : « arithmétique de l'horloge » ==
[[Fichier:Clock_group.svg|vignette|L'aiguille des heures matérialise l'arithmétique modulo 12.]]
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''<ref group="N">''Modulo'' est l'[[ablatif]] du nom latin ''modulus'', mesure. Modulo 12 signifie : selon le module 12. Gauss utilisait plutôt la tournure ''[https://gallica.bnf.fr/ark:/12148/bpt6k994003/f13.image.r=.langFR secundum modulum]''. ''Congru'' provient du participe passé du verbe ''congruere'', s'accorder.</ref> 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.

== Congruence modulo ''n'' ==

=== Définition ===
{{Théorème|Définition<ref name=Escofier>{{Ouvrage|auteur1=Jean-Pierre Escofier|titre=Toute l'algèbre de la Licence|éditeur=[[Dunod]]|année=2011|numéro d'édition=3|passage=223|isbn=|lire en ligne={{Google Livres|QiDIaNo_53wC|page=223}}}}.</ref>{{,}}<ref>{{Ouvrage|auteur1=C. Deschamps|auteur2=F. Moulin|auteur3=[[André Warusfel|A. Warusfel]]|et al.=oui|titre=Mathématiques tout-en-un [[MPSI]]|éditeur=[[Éditions Dunod|Dunod]]|année=2015|numéro d'édition=4|passage=347|isbn=|lire en ligne={{Google Livres|caH1CQAAQBAJ|page=347}}}}.</ref>{{,}}<ref name=GuininJoppin/>|Soit ''n'' un [[entier naturel]]<ref>Ou même relatif : {{Ouvrage|auteur1=J.-P. Marco|auteur2=L. Lazzarini|titre=Mathématiques L1|éditeur=[[Pearson (maison d'édition)|Pearson]]|année=2012|passage=282|isbn=|lire en ligne={{Google Livres|x9Ml5YRIeEgC|page=282}}}}.</ref>.

Deux [[Entier relatif|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.|style=display:table}}On exclut désormais le cas [[trivial]] <math>n=0</math> (la congruence modulo 0 est l'[[Égalité (mathématiques)|égalité]] ; on peut accessoirement remarquer que modulo 1, deux entiers quelconques sont équivalents<ref name="GuininJoppin">{{Ouvrage|auteur1=D. Guinin|auteur2=B. Joppin|titre=Algèbre et géométrie [[Classes préparatoires mathématiques, physique|MP]]|éditeur=[[Éditions Bréal|Bréal]]|année=2004|passage=10|isbn=|lire en ligne={{Google Livres|Hhxmfi7n6h4C|page autre=PR8}}}}.</ref>).{{Théorème|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''.|style=display:table}}

=== Notation ===
Le caractère utilisé pour exprimer la congruence de deux entiers est {{Page h'|≡}}.

On peut exprimer que <math>a</math> et <math>b</math> sont congrus modulo <math>n</math> sous quatre formes :

* <math>a\equiv b \,\,(n)</math>;
* <math>a\equiv b \,\,[n]</math> ;
* ''<math>a\equiv b \,\,(\text{mod } n)</math>'' ;
* ''<math>a\equiv b \mod n</math>'' (notation de Gauss).

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 « <math>a</math> est congru à <math>b</math> modulo <math>n</math> ».

Par exemple : 
{{retrait|26 ≡ 12 (7)}}
car 26 – 12 = 14, multiple de 7 (définition [[#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 [[#Définition|ci-dessus]]).

; Remarques
:* Bien que le [[Caractère (typographie)|caractère typographique]] ≡ soit depuis longtemps disponible, il est encore parfois remplacé par [[=]].
:* Lorsque la congruence est notée (''n''), cette notation peut parfois engendrer une confusion avec des facteurs sous parenthèses. Les notations [''n''], (mod ''n'') et mod ''n'' permettent d'éviter cette ambiguïté.

=== Propriétés ===
==== Relation d'équivalence ====
La congruence modulo <math>n</math> a les propriétés suivantes :

* [[Relation réflexive|réflexivité]] : pour tout entier <math>a</math>, <math>a\equiv a \,\,(n)</math> ;
* [[symétrie]] : pour tous entiers <math>a</math> et <math>b</math>, <math>a\equiv b \,\,(n)\Leftrightarrow b\equiv a \,\,(n)</math> ;
* [[Transitivité (mathématiques)|transitivité]] : pour tous entiers <math>a,b</math> et <math>c</math>, si <math>a\equiv b \,\,(n)</math> et <math>b\equiv c \,\,(n)</math> alors <math>a\equiv c \,\,(n)</math>.

Il s'agit donc d'une [[relation d'équivalence]].

==== Propriétés algébriques ====
Elle a de plus des propriétés algébriques remarquables<ref>Démontrées par exemple dans :

* {{Ouvrage|langue=en|auteur1=Al Cuoco|auteur2=Joseph Rotman|titre=Learning Modern Algebra|lieu=Washington|éditeur=Mathematical association of America|collection=[[Mathematical Association of America|MAA]] Textbooks|année=2013|pages totales=459|passage=134|isbn=978-1-939512-01-7|lire en ligne={{Google Livres|LelYGuQHResC|page=134}}}}, Proposition 4.5 ;
* {{Harvsp|Marco|Lazzarini|p=283|2012}} ;
* {{Note autre projet|wikiversité|Arithmétique/Divisibilité et congruences dans Z#Propriétés des congruences|« Propriétés des congruences »|début=}}</ref> :

Si 
{{retrait|<math>a_1\equiv b_1 \,\,(n)</math> et <math>a_2\equiv b_2 \,\,(n)</math>,}}
alors

* <math>a_1+a_2\equiv b_1+b_2 \,\,(n)</math> et
* <math>a_1a_2\equiv b_1b_2 \,\,(n)</math>.

(On en déduit facilement d'autres, comme : si <math>a\equiv b \,\,(n)</math> alors <math>ac\equiv bc \,\,(n) </math> pour tout entier <math>c</math> et <math>a^q\equiv b^q \,\,(n) </math> pour tout entier <math>q\geqslant0 </math>.)

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 unitaire|anneau]] de (ℤ, +, ×). Ces quelques propriétés vont nous permettre de définir le domaine de l'arithmétique modulaire : les ensembles quotients ℤ/''n''ℤ.

== Anneau résiduel Z/''n''Z ==
{{Article détaillé|Anneau Z/nZ{{!}}Anneau ℤ/''n''ℤ}}

=== Construction ===
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é ℤ{{ind|''n''}} ou ℤ/''n''ℤ composé des ''n'' éléments <math>\{\overline 0, \overline 1, \cdots , \overline {n-1}\}</math> ou plus simplement {0, 1, 2, ... , ''n'' – 1} ensemble des restes, ou résidus, modulo ''n'' que l'on appelle  anneau résiduel<ref group=N>« Résiduel » veut dire « qui reste ».</ref> modulo ''n'' ou encore anneau quotient<ref group=N>Le terme de « quotient » fait référence à la notion d'ensemble quotienté par une [[relation d'équivalence]].</ref>.

Sur cet ensemble peuvent être définies une addition et une multiplication analogues à celles définies sur l'[[Entier relatif|ensemble ℤ des entiers relatifs]] :

* Addition : à deux restes ''a'' et ''b'', on associe le reste de ''a + b'' modulo ''n''. On devrait théoriquement trouver une autre notation pour la somme, par exemple <math>\oplus</math>, mais, pour des raisons de simplicité, on conserve souvent la même notation qui prend alors un sens différent. <br /> Ainsi dans l'anneau des congruences modulo 6, on écrira 3 + 2 = 5 mais 4 + 2 = 0 car la somme de 4 et 2 a pour reste 0 modulo 6
* Multiplication : à deux restes ''a'' et ''b'', on associe le reste de ''a''×''b'' modulo ''n''. Pour les mêmes raisons que précédemment, on utilise pour symbole du produit le même symbole que dans l'ensemble des entiers relatifs. <br /> Ainsi dans l'anneau des congruences modulo 6, on écrira 2×2 = 4, mais 2×5 = 4 (car le produit de 2 par 5 a pour reste 4 dans la division par 6) et même 2×3 = 0

On peut alors construire les tables d'opérations suivantes :

{| class="wikitable gauche" style="text-align:center"
|+ Table d'addition dans ℤ/6ℤ
|-
| style="width:2em" | +
! scope=col style="width:2em" | 0
! scope=col style="width:2em" | 1
! scope=col style="width:2em" | 2
! scope=col style="width:2em" | 3
! scope=col style="width:2em" | 4
! scope=col style="width:2em" | 5
|-
! scope=row | 0
| 0 
| 1
| 2
| 3
| 4
| 5
|-
! scope=row | 1
| 1
| 2
| 3
| 4
| 5
| 0 
|-
! scope=row | 2
| 2
| 3
| 4
| 5
| 0 
| 1
|-
! scope=row | 3
| 3
| 4
| 5
| 0 
| 1
| 2
|-
! scope=row | 4
| 4
| 5
| 0 
| 1
| 2
| 3
|-
! scope=row | 5
| 5
| 0 
| 1
| 2
| 3
| 4
|}

{| class="wikitable gauche" style="text-align:center"
|+ Table de multiplication dans ℤ/6ℤ
|-
| style="width:2em" | ×
! scope=col style="width:2em" | 0
! scope=col style="width:2em" | 1
! scope=col style="width:2em" | 2
! scope=col style="width:2em" | 3
! scope=col style="width:2em" | 4
! scope=col style="width:2em" | 5
|-
! scope=row | 0
| 0 
| 0
| 0
| 0
| 0
| 0
|-
! scope=row | 1
| 0 
| 1
| 2
| 3
| 4
| 5
|-
! scope=row | 2
| 0
| 2
| 4
| 0
| 2 
| 4
|-
! scope=row | 3
| 0
| 3
| 0
| 3 
| 0
| 3
|-
! scope=row | 4
| 0
| 4
| 2 
| 0
| 4
| 2
|-
! scope=row | 5
| 0
| 5 
| 4
| 3
| 2
| 1
|}

{{clr|left}}

Ces opérations ont presque les mêmes propriétés que l'addition et la multiplication dans ℤ.
* l'addition est [[commutativité|commutative]] (les termes peuvent permuter), [[associativité|associative]] (lors de l'addition de 3 termes on peut faire indifféremment la somme des deux premiers et ajouter le dernier  ou la somme des deux derniers et l'ajouter au premier), possède un [[élément neutre]] (ajouter 0 ne change rien) et chaque élément possède un opposé. <br /> Une nuance de taille en comparaison avec l'addition dans ℤ, c'est que, dans ℤ, l'opposé de  ''a'' est –''a'' car ''a'' + (–''a'') = 0. Or, dans l'anneau des congruences modulo ''n'', l'opposé de ''a'' est ''n – a'' car ''a'' + (''n – a'') = 0 (la somme de ''a'' et de ''n – a'' a pour reste 0 dans la division par ''n''). Cependant, –''a'' et ''n – a'' sont interchangeables modulo ''n'' ; le choix de ''n – a'' plutôt que –''a'' tient au fait que l'on choisit comme représentant LE nombre compris entre 0 et ''n'' – 1.
* la multiplication est aussi commutative, associative, possède un élément neutre (multiplier par 1 ne change rien) et reste [[Distributivité|distributive]] pour l'addition.
Un ensemble muni de deux opérations ayant ces propriétés s'appelle un [[anneau unitaire|anneau]].

=== Simplification et équations ===
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 2''a'' = 4 dans ℤ, on sait que ''a'' = 2. Mais modulo 6, si 2''a'' = 4, on sait seulement que  2''a'' 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 {{Citation|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''ℤ
{{retrait|1=modulo 6, on a 2×3 ≡ 0, sans que 2 ni 3 soient congrus à 0. }}

On dit que l'anneau ℤ/6ℤ n'est pas [[anneau intègre|intègre]].

La résolution d'équations peut donc devenir un peu problématique quand des multiplications sont en jeu :
* l'équation ''x'' + 2 = 1 dans ℤ/6ℤ se résout en ajoutant la même quantité (4) dans chaque membre (car 2 + 4 ≡ 0[6]), ce qui donne ''x'' = 5 ;
* l'équation 3''x'' = 2 dans ℤ/10ℤ se résout en remarquant que 7×3 ≡ 1 et que les équations 3''x'' = 2 et ''x'' = 7×2  sont équivalentes (on passe de l'une à l'autre en multipliant chaque membre par 7 ou 3). La solution est alors égale à 4 (car 7×2 a pour reste 4 modulo 10) ;
* l'équation 2''x'' = 3 dans ℤ/10ℤ ne possède aucune solution et l'équation 2''x'' = 6 en possède deux (3 et 8).
On montre que l'équation ''ax = b'' d'[[inconnue (mathématiques)|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 <math>x^2\equiv a \pmod n</math> 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ésidu quadratique|résidus quadratiques]] et à l'énoncé de la [[loi de réciprocité quadratique]].
   
La construction de ℤ/''n''ℤ comme [[relation d'équivalence|anneau quotienté]] par un [[idéal]] et les propriétés algébriques de l'anneau ℤ/''n''ℤ sont traités dans l'article « [[Anneau Z/nZ|Anneau ℤ/''n''ℤ]] ».

=== Puissances et petit théorème de Fermat ===
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 ''a{{exp|k}}'', on obtient donc nécessairement plusieurs fois la même valeur. Donc, il existe ''k'' et ''m'' tels que ''a{{exp|k}}'' et ''a{{exp|m}}'' ont le même reste modulo ''n''. Comme la construction de ''a{{exp|k}}'' 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.

{| class="wikitable gauche" style="text-align:center;width:20em"
|+ Puissances successives dans ℤ/7ℤ
|-
|
! scope="col" | 1
! scope="col" | 2
! scope="col" | 3
! scope="col" | 4
! scope="col" | 5
! scope="col" | 6
|-
! scope="row" | k = 0
| 1
| 1
| 1
| 1
| 1
| 1
|-
! scope="row" | k = 1
| 1
| 2
| 3
| 4
| 5
| 6
|-
! scope="row" | k = 2
| …
| 4
| 2
| 2
| 4
| 1
|-
! scope="row" | k = 3
| …
| 1
| 6
| 1
| 6
| …
|-
! scope="row" | k = 4
| …
| …
| 4
| …
| 2
| …
|-
! scope="row" | k = 5
| …
| …
| 5
| …
| 3
| …
|-
! scope="row" | k = 6
| 1
| 1
| 1
| 1
| 1
| 1
|}

{| class="wikitable gauche" style="text-align:center;width:40em"
|+ Puissances successives dans ℤ/15ℤ
|-
| 
! scope="col" | 1
! scope="col" | 2
! scope="col" | 3
! scope="col" | 4
! scope="col" | 5
! scope="col" | 6
! scope="col" | 7
! scope="col" | 8
! scope="col" | 9
! scope="col" | 10
! scope="col" | 11
! scope="col" | 12
! scope="col" | 13
! scope="col" | 14
|-
! scope="row" | k = 0
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
| 1 
|-
! scope="row" | k = 1
| 1 
| 2 
| 3
| 4 
| 5 
| 6 
| 7 
| 8 
| 9 
| 10 
| 11 
| 12 
| 13 
| 14 
|-
! scope="row" | k = 2
| … 
| 4 
| 9
| 1 
| 10 
| 6 
| 4 
| 4 
| 6 
| 10 
| 1 
| 9 
| 4 
| 1 
|-
! scope="row" | k = 3
| … 
| 8 
| 12
| … 
| 5 
| … 
| 13 
| 2 
| 9 
| … 
| … 
| 3 
| 7 
| … 
|-
! scope="row" | k = 4
| … 
| 1 
| 6
| … 
| … 
| … 
| 1 
| 1 
| … 
| … 
| … 
| 6 
| 1 
| … 
|-
! scope="row" | k = 5
| … 
| … 
| 3
| … 
| … 
| … 
| … 
| … 
| … 
| … 
| … 
| 12 
| … 
| … 
|-
! scope="row" | …
| … 
| … 
| …
| … 
| … 
| … 
| … 
| … 
| … 
| … 
| … 
| … 
| …
| … 
|-
! scope="row" | k = 8
| 1 
| 1 
| …
| 1 
| … 
| … 
| 1 
| 1 
| … 
| … 
| 1 
| … 
| 1 
| 1 
|}

{{clr|left}}

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 ''a''{{6}} 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, ''a''{{8}} est congru à 1 modulo 15.

Ces deux observations correspondent à deux théorèmes :
* le [[petit théorème de Fermat]] qui stipule que, pour tout entier ''n'' premier et tout entier ''a'' premier avec ''n'', <math>a^{n-1} \equiv 1 \pmod n</math> ;
* le [[théorème d'Euler (nombres)|théorème d'Euler]], généralisation du théorème précédent, qui précise que, pour tout entier ''n'' supérieur ou égal à 2, et tout entier ''a'' premier avec ''n'', <math>a^{\varphi(n)}\equiv 1 \pmod n</math>, où <math>\varphi(n)</math>, [[indicatrice d'Euler]], est le nombre d'entiers compris entre 1 et ''n'' et premiers avec ''n''.

== Notes et références ==
=== Notes ===
{{Références|group=N}}
=== Références ===
{{Références}}
== Voir aussi ==
{{Autres projets|v=Arithmétique/Divisibilité et congruences dans Z|wikiversity titre=Arithmétique : Divisibilité et congruences dans Z}}
*[[Arithmétique élémentaire]]
*[[Critère de divisibilité]]
*[[Liste de critères de divisibilité]]
*[[Détermination du jour]]

{{palette|Générateur de nombres pseudo-aléatoires}}
{{Portail|nombre}}

[[Catégorie:Arithmétique élémentaire]]

[[nl:Modulus (wiskunde)]]
[[pl:Arytmetyka modularna#Definicja]]