Modulo (opération)

Pour les articles homonymes, voir Modulo.

Cet article ne cite pas suffisamment ses sources (juin 2009).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Les contributeurs sont tenus de ne pas participer à une guerre d’édition sous peine de blocage.

Cette page a récemment subi une guerre d’édition durant laquelle plusieurs contributeurs ont mutuellement annulé leurs modifications respectives. Ce comportement non collaboratif est interdit par la « règle des trois révocations ». En cas de désaccord éditorial, ils doivent en discuter et trouver un consensus avant toute nouvelle modification sur le même sujet.

Ce bandeau a été déposé par Dfeldmann (discuter) 14 septembre 2024 à 17:58 (CEST).

En informatique, l'opération modulo^[1],[2], ou opération mod^[3], 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 (ou a % n dans certains langages informatiques). Ainsi 9 mod 4 = 1, car 9 = 2×4 + 1 et 0 ≤ 1 < 4. De même 9 mod 3 = 0. L'opération peut être étendue aux entiers relatifs, voire aux nombres réels^[4], mais alors les langages de programmation peuvent diverger, en particulier a mod n n'est plus forcément positif ou nul^[5].

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^[6].

L'opération mod associe à deux entiers naturels a et b ≠ 0 le reste de la division euclidienne de a par b, qui est l'unique entier r vérifiant :

• a = b × q + r pour un certain entier naturel q ;
• 0 ≤ r < b.

Par exemple :

12 mod 10 = 2 car 12 = 10 * 1 + 2 et 0 ≤ 2 < 10

c'est-à-dire que 2 est le reste de la division euclidienne de 12 par 10.

En mathématique le modulo est couramment utilisé pour définir des relations de congruence sur les entiers. C'est à dire des relations de comparaison circulaire typique, par exemple, des calculs calendaires.

En informatique, le modulo est classiquement utilisé dans le même esprit.

Un exemple classique utilisé en mathématique et également représentatif de son usage en informatique, est le calcul sur une horloge.

En effet, sur une horloge, l'addition des heures est circulaire : si il est 9h et que je rajoute 4h alors il est 13h, mais, sur une horloge qui repasse à 0 après le passage à 12, alors il est noté 1h.

On dit que les opérations sur l'horloge sont alors « modulo 12 ».

1 et 13 sont alors dit « congrus modulo 12 », ou encore :

1 ≡ 13 (mod 12).

En considérant le modulo comme une opération, comme c'est le cas en informatique, on écrirait :

Heure_finale = ( Heure_initiale + x ) mod 12

De manière générale, en informatique, l'opération modulo est utilisée pour toute opération circulaire similaire (calcul calendaire, certains parcours de tableau etc.)

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

L'analogie avec la définition du reste de la division euclidienne est brisée une fois qu'on l'étend aux entiers négatifs ou aux réels. Le comportement du modulo diffère alors en fonction des langages de programmation et ne respecte en général plus la définition mathématique du reste de la division euclidienne.

En effet, le reste de la division reste positif dans tout les cas (voir schéma ci-contre), contrairement à de nombreuses autres définitions utilisées en informatique (voir sections ci-après).

On décrit ci-dessous quelques-unes des définitions courantes dans les langages informatiques.

Soit la notation ${\displaystyle \lfloor x\rfloor }$ définissant le plus grand entier inférieur ou égal à x.

Alors on peut poser une définition du modulo tel que :

${\displaystyle 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. Ce qui le distingue du reste de la division euclidienne puisque le modulo peut alors être négatif quand le quotient est négatif.

Exemple :

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. La valeur modulaire retournée est toujours du signe du diviseur (le diviseur étant positif dans la plupart des calculs cycliques).

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

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

L'opérateur mod retourne alors :

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

Exemple :

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.

On peut également utiliser l'arrondi en définissant le quotient tel que :

${\displaystyle q=arrondi({\frac {a}{b}})}$

Où « arrondi » est la fonction arrondi.

Le reste, résultat du modulo, est alors défini par :

${\displaystyle r=a-n*arrondi({\frac {a}{b}})}$

Cette définition est notamment utilisée dans le langage LISP.

Soit la notation ${\displaystyle \left\lceil x\right\rceil }$ définissant le plus petit entier supérieur ou égal à x.

Alors on peut poser une définition du quotient ainsi :

${\displaystyle q=\left\lceil {\frac {a}{n}}\right\rceil }$

Et la définition du modulo tel que :

${\displaystyle a{\bmod {n}}=a-\left\lceil {\frac {a}{n}}\right\rceil \times n}$

Le comportement est proche de celui de la partie entière inférieure.

Ce comportement est également trouvé en LISP.

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

D'un point de vue strictement mathématique, il n'existe pas d'équivalent strict au modulo dans l'espace des réels. Il peut exister des équivalences partielles mais certaines opérations ne sont alors plus valables.

Toutefois, du strict point de vue des définitions utilisées dans les langages informatiques, les deux définitions informatiques précédentes du modulo restent valide et permettent donc à x et y d'être 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, par analogie avec la fonction mathématique, en C, C++, PHP et de nombreux langages, l'opérateur mod ou % n'opère que sur les types entiers. A contrario : dans certains cas l'opérateur modulo est étendu aux réels. Attention, parce que suivant le langage, les types numériques sont parfois convertis implicitement en entiers (par coercition) ce qui peut donner l'impression que l'opérateur est étendu aux réels quand ce n'est pas le cas.

• 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 ;
• 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^[56]. »

• Free Pascal et Delphi n'autorisent que des opérandes entiers, et la définition du langage^[57] précise : « Le signe du résultat est le signe de l'opérande gauche » ;
• C^[8], C++ : a % n demande des opérandes entiers ;
• 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 partie entière inférieure pour l'un de ces langages on peut utiliser l'expression :

   (a % n + n) % n

Dans la plupart des langages, l'opération modulo ne donne aucun résultat si le diviseur est nul, mais lance une exception arithmétique de division par zéro.

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

• Portail de l’informatique