Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Arithmétique modulaire

L'arithmétique modulaire, fut pour la première fois étudiée 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 abstraite et en cryptographie.

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).

Sommaire

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

2 Congruence modulo n

2.1 Définition
2.2 Propriétés

">3 Ensembles quotients $\mathbb{Z}/n\mathbb{Z}\,$

3.1 Construction
3.2 Structure d'anneau
3.3 Éléments inversibles, structure de corps

4 L'opération « modulo » en informatique

4.1 Implémentation de la fonction mod

5 Voir aussi

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 à midi 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 ; nous travaillons modulo 12. Pour généraliser, nous pouvons facilement imaginer une horloge qui contient un nombre arbitraire de nombre d'heures, et faire des calculs avec un nouveau modulo. En arithmétique traditionnelle, 8 + 6 est égal à 14, tandis qu'en arithmétique modulo 12 le résultat est 2, parce que 2 est le reste de la division euclidienne de 14 par 12.

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 ;
ils ont même reste lorsqu'ils sont divisés par n, c'est-à-dire que 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 (utilisant cette définition, nous pouvons généraliser à d'autres ensembles de nombres. Par exemple, nous pouvons définir a est congru à b modulo π lorsqu'il existe un entier k tel que a−b=kπ) ;
a−b ∈ nℤ, l'idéal de tous les entiers divisibles par n.

On écrira alors :

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

14 ≡ 26 (12).

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 b ≡ c (n).

C'est donc une relation d'équivalence.

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

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

alors

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

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

On peut parler d'une certaine « compatibilité » avec les opérations d'addition et de multiplication des entiers (« compatibilité » avec la structure d'anneau de ℤ). Plus généralement on appellera congruence sur une structure donnée toute relation d'équivalence « compatible » avec cette structure.

Ces quelques propriétés vont nous permettre de définir le domaine de l'arithmétique modulaire : les ensembles quotients ℤ/nℤ.

Ensembles quotients $\mathbb{Z}/n\mathbb{Z}\,$

Construction

La congruence modulo n étant une relation d'équivalence sur l'ensemble des entiers, ont 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{n}$ . On la note , ou $a + n\mathbb{Z}$ , ou encore, tout simplement, $\dot{a}$ quand on sait de quel n on parle.

L'ensemble quotient de $\mathbb{Z}$ par la congruence modulo n est l'ensemble { $[a]_n | a \in \mathbb{Z}\,$ }, noté encore $\mathbb{Z}/n\mathbb{Z}\,$ et parfois $\mathbb{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 :

$[a]_n + [b]_n = [a + b]_n\,$
$[a]_n \times [b]_n = [ab]_n\,$

De cette façon, $\mathbb{Z}/n\mathbb{Z}\,$ devient un anneau commutatif à n éléments.

Par exemple, dans l'anneau $\mathbb{Z}/12\mathbb{Z}\,$ , nous avons

$[8]_{12} \times [3]_{12} + [6]_{12} = [6]_{12}\,$ .

L'origine du terme anneau se trouve ici : les nombres 0, …, n−1 sont en effet arrangés dans un anneau de la même manière que les chiffres des heures sur une horloge.

En algèbre abstraite, il apparaît que l'arithmétique modulaire est un cas particulier d'un anneau quotient formé à partir d'un anneau modulo un idéal. Ainsi $\mathbb{Z}/n\mathbb{Z}\,$ est l'anneau quotient de $\mathbb{Z}\,$ par l'idéal $n\mathbb{Z}\,$ , d'où cette notation à première vue mystérieuse : « $\mathbb{Z}/n\mathbb{Z}\,$ ».

Éléments inversibles, structure de corps

Si a et b sont des entiers, l'équation de congruence

$a.x \equiv b \pmod{n}\,$

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 [a]_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{n}\,$

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{n}\,$

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}\,$ .

L'opération « modulo » en informatique

Une très grande part des calculs réalisés en informatique sont des calculs d'arithmétique modulaire (d'autres se font, par exemple, en arithmétique saturée). Ceci est dû au fait que les données manipulées sont toujours représentées au final comme une suite finie de bits, c’est-à-dire un entier compris entre 0 et $n - 1 = 2^{m} - 1\,$ et que donc l'arithmétique des entiers doit être approchée sur ces ensembles finis. De plus, nombre d'opérations sont réalisées bit à bit, c’est-à-dire dans $\mathbb{Z}/2\mathbb{Z}\,$ .

Du fait de cette utilisation au quotidien, des notations spécifiques sont apparues pour cette discipline.

Ainsi, en programmation informatique, on désigne par « modulo » l'opération de calcul du reste de la division euclidienne. Si a est un entier quelconque et n un entier strictement positif, on écrira a mod n pour représenter le reste dans {0, …, n−1} de la division de a par b. Par exemple, 26 mod 12 = 2.

On note souvent cette opération a % n (notation utilisée dans les langages dérivés de C).

Implémentation de la fonction mod

Dans la pratique x mod y peut être calculé en utilisant d'autres fonctions. Des différences apparaissent suivant les types des variables utilisées, lesquels contiennent le type entier dans les implémentations courantes.

En utilisant la partie entière floor, floor(z) est le plus grand entier inférieur à z :

x mod y = x - y*floor(x/y).

En utilisant la fonction de troncature de la partie décimale (désignée par remain() dans certains calculateurs et qui retourne toujours un entier positif ; réalisée en C par l'opérateur de base %) :

x mod y = x - y*iPart(x/y)

Dans le cas de la fonction partie entière floor, le résultat est négatif pour un modulo avec un entier strictement négatif (en convenant de poser a mod -n = -(a mod n), par exemple 1 mod -2 = -1). Nous obtenons une fonction notée mod() sur les calculateurs et implémentée dans certains langages de haut niveau incluant Perl. Perl utilise aussi l'opérateur % pour effectuer une opération modulo, en faisant allusion à l'opérateur de division /.

Les deux définitions permettent à x et y d'être des entiers ou des nombres rationnels.

L'expression x mod 0 n'est pas définie dans la majorité des systèmes numériques, bien que certains la définissent comme étant x.

Voir aussi

Divisibilité
Critère de divisibilité
Trouver un critère de divisibilité

Catégories: Arithmétique modulaire

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the