Congruence sur les entiers

Infos
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
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é : :aa (n)
-Symétrie : :ab (n) ⇔ ba (n)
-Transitivité : :Si ab (n) et bc (n) alors ac (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:同餘
Sujets connexes
Algèbre générale   Allemagne   Anneau (mathématiques)   Anneau Z/nZ   Arithmétique modulaire   Carl Friedrich Gauss   Congruence   Corps (mathématiques)   Corps fini   Critère de divisibilité   Cryptographie   Disquisitiones arithmeticae   Divisibilité   Division euclidienne   Idéal   Indicatrice d'Euler   Leonhard Euler   Liste de critères de divisibilité   Mathématicien   Nombre premier   Notion de module   Petit théorème de Fermat   Plus grand commun diviseur   Relation d'équivalence   Réflexivité   Symétrie   Théorie des nombres   Théorème d'Euler (nombres)   Théorème de congruence linéaire   Théorème des restes chinois   Transitivité (mathématiques)  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^