Congruence sur les entiers

La congruence sur les entiers fut pour la première fois étudiée en tant que structure par le mathématicien allemand Carl Friedrich Gauss à la fin du 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 modulo (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 Z/nZ.

Idée intuitive : « arithmétique de l'horloge »

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 à 7 heures et ajoutons 8 heures, alors plutôt que de terminer à 15 heures (comme dans l'addition normale), nous sommes à 3 heures. 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 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 facilement imaginer une horloge qui contient un nombre arbitraire d'heures, et faire des calculs avec un nouveau modulo.

Congruence modulo n

Définition

Deux entiers a et b sont dits congruents modulo n, où n est un entier non nul et différent de 1 et -1, si l'une des conditions équivalentes suivantes est vérifiée :
-leur différence est divisible par n ;
-le reste de la division euclidienne de a par n est égal à celui de la division de b par n ;
-il existe un entier k tel que a-b=kn
-a-b\in n\Z, l'idéal de tous les entiers divisibles par n. On écrira alors : :a \equiv b \ (n) ou a \equiv b ou encore a\equiv b \pmod n ce qui se lit dans tous les cas « a est congru à b modulo n ». Par exemple : 26 ≡ 12 (14).

Propriétés

La congruence modulo n a les propriétés suivantes :
-Réflexivité : :a ≡ a (n)
-Symétrie : :a ≡ b (n) ⇔ b ≡ a (n)
-Transitivité : :Si a ≡ b (n) et b ≡ c (n) alors a ≡ c (n) C'est donc une relation d'équivalence. Elle a de plus des propriétés algébriques remarquables : Si :a1 ≡ b1 (n)    et    a2 ≡ b2 (n) alors :a1 + a2 ≡ b1 + b2 (n) et :a1a2 ≡ b1b2 (n). 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 (Z, +,
-)). Ces quelques propriétés vont nous permettre de définir le domaine de l'arithmétique modulaire : les ensembles quotients Z/nZ.

Ensembles quotients Z/nZ

Construction

La congruence modulo n étant une relation d'équivalence sur l'ensemble des entiers, on peut donc diviser cet ensemble en classes d'équivalences. La classe d'équivalence de l'entier a est l'ensemble des entiers b tels que a \equiv b \pmod. On la note _n, ou a + n\mathbb Z, ou encore, tout simplement, \dot quand on sait de quel n on parle. L'ensemble quotient de \mathbb Z par la congruence modulo n est l'ensemble \_n | a \in \mathbb Z\, noté encore \mathbb Z/n\mathbb Z\, et parfois \Z_n.

Structure d'anneau

On définit une addition et une multiplication sur l'ensemble \mathbb Z/n\mathbb Z\, par les règles suivantes :
- _n + _n = _n\,
- _n \times _n = _n\, De cette façon, \mathbb Z/n\mathbb Z\, devient un anneau commutatif à n éléments si n est non nul (sinon, \mathbb Z/0\mathbb Z\, est isomorphe à \mathbb Z). Par exemple, dans l'anneau \mathbb Z/12\mathbb Z\, , nous avons : _ \times _ + _ = _\, .

Éléments inversibles, structure de corps

Si a et b sont des entiers, l'équation de congruence : a.x \equiv b \pmod\, a une solution x si et seulement si le plus grand commun diviseur pgcd(a, n) divise b. Pour plus de détails vous pourrez consulter la page concernant le théorème de congruence linéaire. Des systèmes d'équations de congruence plus compliqués avec différentes congruences peuvent être résolus en utilisant le théorème des restes chinois. Posons b=1. La proposition précédente est équivalente à l'affirmation que les éléments inversibles de l'anneau \mathbb Z/n\mathbb Z\, sont précisément les éléments n tels que a et n n'ont aucun diviseur en commun non trivial (sont premiers entre eux). Ainsi, \mathbb Z/n\mathbb Z\, est un corps si et seulement si n est un nombre premier. Tous les corps finis sont des extensions de ceux-ci. Un important théorème relatif aux congruences modulo un nombre premier est le petit théorème de Fermat : si p est un nombre premier et a est un entier quelconque, alors : a^p \equiv a \pmod\, Ce résultat fut généralisé par Euler : pour tout entier strictement positif n et tout entier a premier avec n, : a^\phi(n) \equiv 1 \pmod\, où \phi\, désigne la fonction φ d'Euler comptant les entiers compris entre 1 et n et premiers avec n. Le théorème d'Euler est une conséquence du théorème de Lagrange, appliqué au groupe des inversibles de l'anneau \mathbb Z/n\mathbb Z\, .

Voir aussi

-Arithmétique modulaire
-Divisibilité
-Critère de divisibilité
-Liste de critères de divisibilité
-Anneau Z/nZ
-Notion de module Catégorie:Arithmétique modulaire de:Kongruenz (Zahlentheorie) en:Modular arithmetic es:Aritmética modular he:חשבון מודולרי it:Aritmetica modulare ja:合同式 nl:Modulus (wiskunde) pl:Ciało Zp pt:Módulo th:เลขคณิตมอดุลาร์ zh:同餘