Modulo (opération)

En informatique, l'opération modulo^{[réf. souhaitée]}, ou opération mod[1], est une opération binaire qui associe à deux entiers naturels le reste de la division euclidienne du premier par le second, le reste de la division de a par n (n ≠ 0) est noté a mod n (a % n dans certains langages informatiques). Ainsi 9 mod 4 = 1, car 9 = 2×4 + 1 et 0 ≤ 1 < 4, 9 mod 3 = 0, … L'opération peut être étendue aux entiers relatifs, voire aux nombres réels[2], mais alors les langages de programmation peuvent diverger, en particulier a mod n n'est plus forcément positif ou nul[3].

En mathématiques, l'usage du terme modulo est différent même s'il est lié : il ne désigne pas une opération mais intervient pour caractériser une relation de congruence sur les entiers (et plus généralement pour d'autres congruences) ; le mot clef mod associé n'est le plus souvent utilisé que pour noter cette congruence, même si un ouvrage comme Concrete Mathematics l'utilise également pour désigner l'opération binaire[4].

Trois définitions de la fonction modulo

Dans la pratique, x mod y peut être calculé en utilisant d'autres fonctions. Ainsi, en notant :

x=\lfloor x\rfloor +\{x\}

, avec

\lfloor x\rfloor

la partie entière inférieure et

\{x\}

la partie fractionnaire,

on a :

a{\bmod {n}}=a-(\lfloor a/n\rfloor \times n)

.

Par exemple, 9 mod 4 = 9 − ⌊9/4⌋×4 = 9 − 2×4 = 1.

Des différences apparaissent suivant les types des variables utilisées, lesquels contiennent le type entier dans les implémentations courantes. Mais la principale différence réside dans l'interprétation de la partie entière du quotient, en fonction du signe du dividende ou celui du diviseur quand ceux-ci peuvent être négatifs :

En utilisant la partie entière (définition mathématique)

$\lfloor x\rfloor$ est le plus grand entier inférieur ou égal à x.

a{\bmod {n}}=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n

L'opérateur mod retourne alors un modulo toujours compris entre 0 (inclus) et le diviseur n (exclu) et qui a le même signe que le diviseur n.

Exemple :

Dividende	Diviseur	Quotient	Reste
117	17	6	15
−117	17	−7	2
−117	−17	6	−15
117	−17	−7	−2
12,7	3,5	3	2,2

Cette définition vérifie les lois de l'arithmétique modulo, plus : x mod −y = −((−x) mod y). Elle convient pour les calculs cycliques (par exemple calendaires). La valeur modulaire retournée est toujours du signe du diviseur (le diviseur étant positif dans la plupart des calculs cycliques, dont les calculs calendaires).

En utilisant la fonction de troncature de la partie décimale

$\left[x\right]$ est la troncature entière de x.

a{\bmod {n}}=a-\left[{\frac {a}{n}}\right]\times n

L'opérateur mod retourne alors :

un modulo positif inférieur à $\left|n\right|$ pour a positif.
un modulo négatif supérieur à $-\left|n\right|$ pour a négatif.

Exemple :

Dividende	Diviseur	Quotient	Reste
117	17	6	15
−117	17	−6	−15
−117	−17	6	−15
117	−17	−6	15

Le modulo a le même signe que l'opérande gauche.

Cette définition vérifie la loi: x mod −y = x mod y. Elle viole la loi (x+n) mod n = x mod n.

Comparaison sous forme de tableau

comparaison des opérateurs Modulo
		def. mathématique		troncature
Dividende	Diviseur	Quotient	Reste	Quotient	Reste	Reste
117	17	6	15	6	15	15
−117	17	−7	2	−6	−15	?
−117	−17	6	−15	6	−15	15
117	−17	−7	−2	−6	15	?
12,7	3,5	3	2,2

Comportement avec des opérandes non entiers

Les trois définitions permettent à x et y d'être des entiers négatifs, ou des nombres rationnels (ou réels en mathématiques, bien que les systèmes informatiques de calcul numérique ne sachent travailler que sur un sous-ensemble des nombres rationnels, du fait de limites de précision).

Cependant en C, C++, PHP et de nombreux langages, l'opérateur mod ou % n'opère que sur les types entiers. Suivant le langage, les types numériques sont parfois convertis implicitement en entiers (par coercition).

Comportement des langages de programmation

Les langages suivants utilisent la définition mathématique (1.)

Perl : $a % $n est défini sur les entiers ; les opérandes réels sont tronqués vers 0 par coercition ;
Visual Basic : a Mod n est défini sur les réels et sur les entiers, et renvoie un entier si les deux opérandes sont entiers ;
Pascal (ISO 7185) : a mod n n'admet que des opérandes entiers, et n doit être strictement positif ;
Excel : MOD(a;n) fonctionne sur les nombres réels ;
langage Python : La FAQ explique ce choix par l'exemple suivant :

« si une horloge indique 10 heures, qu'indiquait-elle 200 heures avant ? -190 % 12 == 2 est utile ; -190 % 12 == -10 est un bug prêt à mordre[5]. »

Les langages suivants utilisent la définition (2.)

Free Pascal et Delphi n'autorisent que des opérandes entiers, et la définition du langage[6] précise : « Le signe du résultat est le signe de l'opérande gauche » ;
C[7], C++ : a % n demande des opérandes entiers ;
Java : a % n permet des opérandes réels ;
Javascript : a % n permet des opérandes réels ;
PHP : $a % $n est défini sur les entiers et retournera un résultat ayant le même signe que $a ;
Scilab : modulo(a, n) accepte des réels.

Si l'on souhaite utiliser le modulo dans sa définition mathématique pour l'un de ces langages on peut utiliser l'expression (a % n + n) % n.

Valeur d'un modulo 0 (valeur 'zéro')

Dans la plupart des langages, l'opération modulo ne génère aucun résultat si le diviseur est nul, et une exception arithmétique de division par zéro est alors générée.

Équivalence

Les opérations sur les modulos peuvent être réduites ou étendues de la même manière que les autres opérations mathématiques.

Identité:
- $(a\,{\bmod {\,}}n)\,{\bmod {\,}}n=a\,{\bmod {\,}}n$
- $n^{x}\,{\bmod {\,}}n=0$ pour tous les entiers strictement positifs $x$ .
- Si $n$ est un nombre premier qui n'est pas un diviseur de $b$ , alors $ab^{n-1}\,{\bmod {\,}}n=a\,{\bmod {\,}}n$ , d'après le petit théorème de Fermat.
Inverse:
- $((-a\,{\bmod {\,}}n)+(a\,{\bmod {\,}}n))\,{\bmod {\,}}n=0$
- $b^{-1}\,{\bmod {\,}}n$ est l'inverse modulaire, qui est défini si et seulement si $b$ et $n$ sont premiers entre eux, ce qui est le cas quand la partie gauche est définie: $((b^{-1}\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n=1$ .
Distributivité:
- $(a+b)\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)+(b\,{\bmod {\,}}n))\,{\bmod {\,}}n$
- $ab\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n$
- D’où : $a^{2}\,{\bmod {\,}}n=(a\,{\bmod {\,}}n)^{2}\,{\bmod {\,}}n$
Division (définition): ${\frac {a}{b}}\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n$ , quand l'opérande de gauche est défini. Non définie sinon.
Multiplication inverse: $((ab\,{\bmod {\,}}n)\,(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n=a\,{\bmod {\,}}n$

Applications

L'opération modulo permet d'effectuer un décalage circulaire d'indices. En effet, si l'on considère la suite des entiers contigus de 1 à n, u = (1, 2, 3, …, n − 1, n), alors on peut décaler de p rangs avec :

u'_i = ((u_i + p − 1) mod n) + 1.

Par exemple, pour décaler de deux la suite (1, 2, 3, 4, 5) :

u'_i = ((u_i + 1) mod 5) + 1 ;

on a bien :

u'₁ = ((1 + 1) mod 5) + 1 = 3
u'₂ = ((2 + 1) mod 5) + 1 = 4
…
u'₄ = ((4 + 1) mod 5) + 1 = 1

et donc u' = (3, 4, 5, 1, 2).

Notes et références

Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes : Fondations pour l'informatique, Paris, Vuibert, 2003, 2^e éd., xiv+688 (ISBN 978-2-7117-4824-2), p. 88-89.
Raymond T. Boute, « The Euclidean definition of the functions div and mod », ACM Transactions on Programming Languages and Systems, ACM Press (New York, NY, USA), vol. 1, n^o 2,‎ avril 1992, p. 127–144 (DOI 10.1145/128861.128862, lire en ligne), p. 128-129.
Graham, Knuth et Patashnik 2003, p. 89, et note marginale p. 88.
Graham, Knuth et Patashnik 2003, p. 88-89, pour l'opération binaire, p.143 pour la congruence. Les auteurs n'utilisent le terme modulo que pour la relation de congruence, mais nomment « mod » l'opération binaire.
"Why does -22 // 10 return -3?"
(en) Michaël Van Canneyt, « Reference guide for Free Pascal, version 2.6.0 », décembre 2011.
Depuis ISO C99. En ISO C90, en cas d'opérande négatif, le signe du résultat était défini par l'implémentation.

Portail de l’informatique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes : Fondations pour l'informatique, Paris, Vuibert, 2003, 2^e éd., xiv+688 (ISBN 978-2-7117-4824-2), p. 88-89.

[2] Raymond T. Boute, « The Euclidean definition of the functions div and mod », ACM Transactions on Programming Languages and Systems, ACM Press (New York, NY, USA), vol. 1, n^o 2,‎ avril 1992, p. 127–144 (DOI 10.1145/128861.128862, lire en ligne), p. 128-129.

[3] Graham, Knuth et Patashnik 2003, p. 89, et note marginale p. 88.

[4] Graham, Knuth et Patashnik 2003, p. 88-89, pour l'opération binaire, p.143 pour la congruence. Les auteurs n'utilisent le terme modulo que pour la relation de congruence, mais nomment « mod » l'opération binaire.

[5] "Why does -22 // 10 return -3?"

[6] (en) Michaël Van Canneyt, « Reference guide for Free Pascal, version 2.6.0 », décembre 2011.

[7] Depuis ISO C99. En ISO C90, en cas d'opérande négatif, le signe du résultat était défini par l'implémentation.