Congruence sur les entiers

Pour les articles homonymes, voir Congruence.

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 XVIII^e 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 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.

Sommaire

1 Idée intuitive : « arithmétique de l'horloge »
2 Congruence modulo n
3 Anneau résiduel Z/nZ
4 Notes et références
5 Voir aussi

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

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 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 supérieur ou égal à 2, si l'une des conditions équivalentes suivantes est vérifiée :

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

Notation

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

a ≡ b (n) ou a ≡ b [n] ou encore a ≡ b (mod n)

ce qui se lit dans tous les cas « a est congru à b modulo n ».

Par exemple :

26 ≡ 12 (7)

qui se lit « 26 est congru à 12 modulo 7 »

Le caractère utilisé est ≡. Cependant, par commodité, il est parfois remplacé par =.

Propriétés

Relation d'équivalence

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

Réflexivité :

Pour tout entier a, a ≡ a (n)

Symétrie :

Pour tous entiers a et b, a ≡ b (n) ⇔ b ≡ a (n)

Transitivité :

Pour tous entiers a, b et c, si a ≡ b (n) et b ≡ c (n) alors a ≡ c (n)

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 :

a₁ ≡ b₁ (n) et a₂ ≡ b₂ (n)

alors

a₁ + a₂ ≡ b₁ + b₂ (n),
a₁a₂ ≡ b₁b₂ (n), et
a₁^q ≡ b₁^q (n), pour n'importe quel entier naturel q supérieur ou égal à 1.

Implications secondaires :

a₁c ≡ b₁c (n), ∀ c ∈ Z.
ka₁ + a₂ ≡ kb₁ + b₂ (n), ∀ k ∈ Z.

Démonstration

Par hypothèse, a₁ = x₁ n + b₁ et a₂ = x₂ n + b₂.

Pour l'addition : a₁ + a₂ = (x₁ + x₂) n + (b₁ + b₂ ) ≡ b₁ + b₂ (n).
Multiplication :

a₁ a₂ = x₁ x₂ n ² + (x₁ b₂ + b₁ x₂) n + b₁ b₂ = (x₁ x₂ n + x₁ b₂ + b₁ x₂) n + b₁ b₂ ≡ b₁b₂ (n).

Élévation à n'importe quelle puissance : on applique de façon répétée la propriété ci-dessus de la multiplication,

pour a₂=a₁ et b₂=b₁, puis

pour a₂=a₁² et b₂=b₁²,

pour a₂=a₁³ et b₂=b₁³, etc.

on obtient ainsi de proche en proche :

a₁² ≡ b₁² (n), puis

a₁³ ≡ b₁³ (n),

a₁⁴ ≡ b₁⁴ (n), etc.

(Cette démonstration peut être formalisée par un raisonnement par récurrence.)

En utilisant la réflexivité :

a₁ ≡ b₁ (n) et c ≡ c (n)

Alors

a₁c ≡ b₁c (n).

De même :

a₁ ≡ b₁ (n) et a₂ ≡ b₂ (n)

k ≡ k (n)

Alors

ka₁ + a₂ ≡ kb₁ + b₂ (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 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 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, que l'on appelle 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 :

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 $\oplus$ , mais, pour des raisons de simplicité, on conserve souvent la même notation qui prend alors un sens différent.

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

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 :

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$
×	1	2	3	4	5
0	0	0	0	0	0
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	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$ .

l'addition est commutative (les termes peuvent permuter), 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é.

Une nuance de taille en comparaison avec l'addition dans $\mathbb Z$ , c'est que, dans $\mathbb Z$ , 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 distributive pour l'addition.

Un ensemble muni de deux opérations ayant ces propriétés s'appelle un anneau.

Simplification et équations

La seule opération que l'on a l'habitude de faire dans $\mathbb Z$ et qui n'est pas toujours 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 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 $\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 donc devenir un peu problématique quand des multiplications sont en jeu :

l'équation x + 2 = 1 dans $\mathbb Z/6\mathbb Z$ se résout en ajoutant la même quantité (4) dans chaque membre x = 5 (car 2 + 4 = 0[6])
l'équation 3x = 2 dans $\mathbb Z/10\mathbb Z$ se résout en remarquant que 3 × 7 = 1 et que les équations 3x = 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 2 × 7 a pour reste 4 modulo 10)
l'équation 2x = 3 dans $\mathbb Z/10\mathbb Z$ ne possède aucune solution et l'équation 2x = 6 en possède deux (3 et 8)

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 seulement 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 et à 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 possibles, donc n - 1 valeurs possibles pour $a k$ , on obtient donc nécessairement plusieurs fois la même valeur. Donc, il existe k et m tels que $a k$ et $a m$ ont le même reste modulo n. Comme la construction de $a 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 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 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 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, $a^{n-1} \equiv 1 \pmod n$
le 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, $a^{\varphi(n)}\equiv 1 \pmod n$ , où $φ(n)$ , indicatrice d'Euler, est le nombre d'entiers compris entre 1 et n et premiers avec n.

Notes et références

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

Voir aussi

Portail des mathématiques

Catégorie :

Arithmétique élémentaire

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Congruence sur les entiers de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

Congruence Sur Les Entiers — Pour les articles homonymes, voir Congruence. 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… … Wikipédia en Français
Théorème de Fermat sur les sommes de deux carrés — Théorème des deux carrés de Fermat Pierre Fermat En mathématiques, le théorème des deux carrés de Fermat énonce les conditions pour qu’un nombre entier soit la somme de deux carrés parfaits (c est à dire de deux carrés d’entiers) et précise de… … Wikipédia en Français
Opérations sur les dérivées — Le calcul de la dérivée de certaines fonctions à valeurs réelles ou complexes (ou plus généralement dans un corps topologique) peut être effectué en utilisant un certain nombre d opérations sur les dérivées, notamment certaines liées aux… … Wikipédia en Français
Opérations sur les limites — Cette page est une annexe de l article limite (mathématiques élémentaires), qui explique comment traduire en termes de limites les opérations usuelles : addition, multiplication, composition... Tous les résultats listés ici sont valables à… … Wikipédia en Français
Congruence modulo — Congruence sur les entiers Pour les articles homonymes, voir Congruence. 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… … Wikipédia en Français
Congruence — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Derrière le terme de congruence se cachent des notions semblables mais de niveaux d abstraction différents. Historiquement, la notion de congruence sur… … Wikipédia en Français
PGCD de nombres entiers — Cet article de vulgarisation évite les aspects trop pointus ou techniques. Pour consulter un article plus détaillé, voir : PGCD. Le PGCD de nombres entiers différents de zéro est, parmi les diviseurs communs à ces entiers, le plus grand d… … Wikipédia en Français
congruence — [ kɔ̃gryɑ̃s ] n. f. • 1771; « convenance » XVe; de congru 1 ♦ Math. Égalité de figures géométriques (dites congruentes). ⇒ énantiomorphe. Congruence de droites : famille de droites à deux paramètres. Congruence sur un ensemble E muni d une loi de … Encyclopédie Universelle
Distance entre deux points sur le plan cartésien — Dans le plan cartésien, les points sont définis à l aide de leurs coordonnées dites cartésiennes. Soit deux points A et B dans le plan cartésien. On appelle (xA,yA) les coordonnées du point A et (xB,yB) les coordonnées du point B : alors la… … Wikipédia en Français
Factorisation des entiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Congruence sur les entiers

Sommaire

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