Table of contents

1 Définition de Modulo 1.1 Implémentation de la fonction mod 2 Applications de l'arithmétique modulaire 3 Congruence modulo 4 Ressources externes

Définition de Modulo

Si a est un entier quelconque et n un entier strictement positif, nous écrivons a mod n pour représenter le reste dans {0, ..., n-1} obtenu en effectuant une division euclidienne de a par n. Par exemple, 26 mod 12 = 2.

Dans certains langages de programmation, cette opération est écrite a % n.

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.

Applications de l'arithmétique modulaire

L'arithmétique modulaire, fut pour la première fois étudiée par Carl Friedrich Gauss à la fin du dix-huitième siècle, et appliquée à la théorie des nombres, à l' algèbre abstraite et à la cryptographie.

Les opérations arithmétiques fondamentales sont effectuées par de nombreux ordinateurs en arithmétique modulaire, modulo 2^b (b étant le nombre de bits utilisés pour représenter les données).

Ceci intervient les langages de programmation tel que le langage C; où par exemple les opérations arithmétiques sur les nombres entiers de type int sont prises modulo 2³², sur la plupart des ordinateurs.

Congruence modulo

Deux entiers a et b sont dits congruents modulo n, ce qui s'écrit

a = b (mod n)

1. leur différence est divisible par n;
2. ils ont même reste quand ils sont divisés par n, i.e. a mod n = b mod n;
3. a-b=kn pour un certain entier k; (utilisant cette définition, nous pouvons généraliser à d'autres ensembles de nombres. Par exemple, nous pouvons définir a = b (mod π) si a-b=kπ pour un entier k.)
4. a-b ∈ nZ, l' idéal de tous les entiers divisibles par n.

14 = 26 (mod 12).

a₁ = b₁ (mod n)    and    a₂ = b₂ (mod n)

a₁ + a₂ = b₁ + b₂ (mod n)

a₁a₂ = b₁b₂ (mod n).

(a₁ + a₂) mod n = ((a₁ mod n) + (a₂ mod n)) mod n

(a₁a₂) mod n = ((a₁ mod n)(a₂ mod n)) mod n

Z_n = { [0]_n, [1]_n, [2]_n, ..., [n-1]_n }

• [a]_n + [b]_n = [a + b]_n
• [a]_n × [b]_n = [ab]_n

[8]₁₂×[3]₁₂ + [6]₁₂ = [6]₁₂.

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. À partir de la dernière des quatre conditions équivalentes, nous déduisons que est l'anneau quotient de par l'idéal , et est souvent noté .

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

ax = b (mod n)

Posons b=1. La proposition précédente est équivalente à l'affirmation que les éléments inversibles de l'anneau 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,

est un corps si et seulement si n est un nombre premier. Tous les corps finis sont des extensions de ceux-ci. 

a^p = a (mod p).

a^φ(n) = 1 (mod n),

Ressources externes