Congruence sur les entiers

La congruence sur les entiers est une relation pouvant unir deux entiers. Elle fut pour la première fois étudiée comme structure par le mathématicien allemand Carl Friedrich Gauss à la fin du XVIIIe siècle...



Catégories :

Arithmétique élémentaire - Mathématiques élémentaires

Page(s) en rapport avec ce sujet :

  • Congruences modulo n. Définition. Soit n un entier strictement positif...... Le théorème des restes chinois sert à résoudre un dispositif... (source : gymnase-yverdon.vd)
  • Deux entiers relatifs sont congrus modulo n (avec n un entier naturel) si et .... Exemple de congruence. Quel est le reste de la division de 2ˆ{16}\, ... (source : fr.wikiversity)

La congruence sur les entiers est une relation pouvant unir deux entiers. Elle fut pour la première fois étudiée comme structure par le mathématicien allemand Carl Friedrich Gauss à la fin du XVIIIe siècle et présentée au public dans ses Disquisitiones arithmeticæ en 1801. Elle est actuellement fréquemment 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 nommée arithmétique modulaire.

C'est une arithmétique où 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 mais aussi 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 dispositif arithmétique d'entiers modifiés, où les nombres sont «abaissés» quand 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).

Essentiellement, lorsque 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 reconnus comme égaux quand on travaille modulo 12.

Pour généraliser, nous pouvons aisément 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 supérieur ou égal à 2, si l'une des conditions équivalentes suivantes est vérifiée :

  1. leur différence est divisible par n ; (il existe un entier k tel que ab = kn)
  2. le reste de la division euclidienne de a par n est égal à celui de la division de b par n ;
  3. a-b\in n\Z, l'idéal de l'ensemble des entiers divisibles par n.

Notation

Si a et b sont congruents modulo n, on écrira :

ab (n) ou ab [n] ou encore ab (mod n)

ce qui se lit dans l'ensemble des cas «a est congru à b modulo n».

Par exemple :

26 ≡ 12 (14)

Le caractère utilisé est ≡. Cependant, par commodité, il est quelquefois remplacé par = même si cela reste faux dans l'absolu.

Propriétés

Relation d'équivalence

La congruence modulo n a les propriétés suivantes :

Pour tout entier a, aa (n)
Pour tous entiers a et b, ab (n) ⇔ ba (n)
Pour tous entiers a, b et c, si ab (n) et bc (n) alors ac (n)

C'est par conséquent une relation d'équivalence.

Propriétés algébriques

Elle a de plus des propriétés algébriques remarquables :

Si

a1b1 (n)   et  a2b2 (n)

alors

a1 + a2b1 + b2 (n)

et

a1a2b1b2 (n).

Enfin, avec un entier naturel q supérieur ou égal à 1, on obtient :

a1qb1q (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.

Anneau résiduel Z/nZ

Article détaillé : Anneau Z/nZ.

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 l'ensemble des nombres congrus entre eux modulo n dans une même classe qu'on nomme une classe d'équivalence et de ne travailler qu'avec un représentant spécifique de cette classe. Comme l'ensemble des nombres de la même classe ont même reste dans la division par n, on privilégie les restes dans la division par n et on travaille sur un ensemble noté \mathbb Z_n ou \mathbb Z/n\mathbb Z composé des n éléments \{\overline 0, \overline 1, \cdots \overline {n-1}\} ou plus simplement {0, 1, 2, ..., n - 1} ensemble des restes modulo n, qu'on nomme anneau résiduel [1] modulo n ou encore anneau quotient [2]

Sur cet ensemble peuvent être définies une addition et une multiplication analogues à celles définies sur les entiers relatifs :

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

Table d'addition dans \mathbb Z/6\mathbb Z
+ 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
Table de multiplication dans \mathbb Z/6\mathbb Z
× 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 \mathbb Z.

Un ensemble pourvu de deux opérations ayant ces propriétés se nomme un anneau.

Simplification et équations

La seule opération qu'on a l'habitude de faire dans \mathbb Z et qui n'est pas forcément juste dans l'anneau \mathbb Z/n\mathbb Z est la simplification.

En effet si 2a = 4 dans \mathbb Z, on sait que a = 2. Mais, dans \mathbb Z/6\mathbb Z, si 2a = 4, on sait uniquement que 2a a pour reste 4 dans la division par 6 par conséquent que a a pour reste 2 dans la division par 3. a peut par conséquent avoir pour reste dans la division par 6 soit 2 soit 5. Plus simplement : on a 2 × 2 = 2 × 5 sans pour tout 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 forcément réalisée dans \mathbb Z/n\mathbb Z

dans \mathbb Z/6\mathbb Z, on a 2 × 3 = 0, sans que 2 ni 3 ne soient nuls

On dit que l'anneau \mathbb Z/6\mathbb Z n'est pas intègre.

La résolution d'équations peut par conséquent devenir légèrement problématique lorsque des multiplications sont en jeu :

On montre que la résolution de l'équation ax = b d'inconnue x dans \mathbb Z/n\mathbb Z possède une unique solution si et uniquement si a et n sont premiers entre-eux

La recherche de solutions à l'équation xˆ2\equiv a \pmod n 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 ainsi qu'à l'énoncé de la loi de réciprocité quadratique.

La construction de \mathbb Z/n\mathbb Z comme anneau quotienté par un idéal et les propriétés algébriques de l'anneau Z/nZ sont traités dans l'article Anneau Z/nZ

Puissances et petit théorème de Fermat

De la multiplication dans \mathbb Z/n\mathbb Z, il est naturel de s'intéresser aux puissances successives. Il n'y a que n - 1 restes envisageables, par conséquent n - 1 valeurs envisageables pour ak, on obtient par conséquent obligatoirement 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 qu'on tombe sur un reste déjà rencontré, on sait que la suite des puissances devient cyclique à partir de cette puissance et on peut arrêter l'exploration.

Puissances successives dans \mathbb Z/7\mathbb Z
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
Puissances successives dans \mathbb Z/15\mathbb Z
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 \mathbb Z/7\mathbb Z et \mathbb Z/15\mathbb Z montre que, dans le premier cas, pour tout a premier avec 7 (c'est-à-dire non congru à 0 modulo 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 on remarque que pour a premier avec 15, a8 est congru à 1 modulo 15.

Ces deux observations correspondent à deux théorèmes :

Notes et références

  1. résiduel veut dire " qui reste"
  2. le terme de quotient fait référence à la notion d'ensemble quotienté par une relation d'équivalence

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Congruence_sur_les_entiers.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu