Modulo (opération)

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

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 ?

En informatique, l'opération modulo^[1]^,^[2], ou opération mod^[3], est une opération binaire qui associe, dans le cas de 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 de la définition mathématique, en particulier a mod n n'est plus forcément positif ou nul comme l'impose la définition mathématique du reste de la division euclidienne^[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].

Différentes définitions de la fonction modulo[modifier | modifier le code]

En principe, le modulo en informatique est défini comme le reste de la division euclidienne. C'est à dire :

Soit la division euclidienne de a par b, on vérifie :

$a = b \times q + r$ ;
$0 \leq r < | b |$ .

En informatique, cette analogie fonctionne pour les entiers naturels, exemple :

12 modulo 10 <=> reste de la division euclidienne de 12 par 10

12 modulo 10 = 2 car 12 = 10 * 1 + 2

Usage[modifier | modifier le code]

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.

Exemple simple[modifier | modifier le code]

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

Exemple avec des décalages circulaires[modifier | modifier le code]

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

Divergence des définitions dans les cas autres que les entiers naturels ...[modifier | modifier le code]

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.

Les différentes définitions en informatique[modifier | modifier le code]

Définition utilisant la partie entière (inférieure)[modifier | modifier le code]

Article connexe : Partie entière et partie fractionnaire.

Soit la notation $\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 :

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 :

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

Définition utilisant la troncature de la partie décimale[modifier | modifier le code]

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

Définition utilisant l'arrondi[modifier | modifier le code]

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

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

Où « arrondi » est la fonction arrondi.

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

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

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

Définition utilisant la partie entière supérieure[modifier | modifier le code]

Soit la notation $\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 :

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

Et la définition du modulo tel que :

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

Comparaison sous forme de tableau[modifier | modifier le code]

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

comparaison des opérateurs Modulo
		partie entière		troncature		fonct. euclidienne
Dividende	Diviseur	Quotient	Reste	Quotient	Reste	Quotient	Reste
117	17	6	15	6	15	6	15
−117	17	−7	2	−6	−15	-7	2
−117	−17	6	−15	6	−15	7	2
117	−17	−7	−2	−6	15	-6	15
12,7	3,5	3	2,2

Comportement avec des opérandes non entiers[modifier | modifier le code]

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.

Comportement des langages de programmation[modifier | modifier le code]

Tableau récapitulatif des différents opérateurs et de leurs définition en fonction du langage informatique
Language	Operateur	Prends en charge les entiers ?	Prise en charge nombre flottants ?	Définition utilisée
ABAP	`MOD`	Oui	Oui	Euclidienne
ActionScript	`%`	Oui	(no)	Troncature
Ada (langage)	`mod`	Oui	(no)	Partie entière (inférieure)^[7]
Ada (langage)	`rem`	Oui	(no)	Troncature^[7]
ALGOL 68	`÷×`, `mod`	Oui	(no)	Euclidienne
AMPL	`mod`	Oui	(no)	Troncature
APL	`\|`^{[note 1]}	Oui	Oui	Partie entière (inférieure)
AppleScript	`mod`	Oui	(no)	Troncature
AutoLISP de AutoCAD	`(rem d n)`	Oui	(no)	Troncature
AWK	`%`	Oui	(no)	Troncature
bash	`%`	Oui	(no)	Troncature
BASIC	`Mod`	Oui	(no)	Dépends de l'implémentation
bc (voir bc (Unix))	`%`	Oui	(no)	Troncature
C^[8] C++	`%`, `div`	Oui	(no)	Troncature^{[note 2]}
	`fmod` (C) `std::fmod` (C++)	(no)	Oui	Troncature^[11]
	`remainder` (C) `std::remainder` (C++)	(no)	Oui	Arrondie
C#	`%`	Oui	Oui	Troncature
C#	`Math.IEEERemainder`	(no)	Oui	Arrondie^[12]
Clarion (langage)	`%`	Oui	(no)	Troncature
Clean	`rem`	Oui	(no)	Troncature
Clojure	`mod`	Oui	(no)	Partie entière (inférieure)^[13]
Clojure	`rem`	Oui	(no)	Troncature^[14]
COBOL	`FUNCTION MOD`	Oui	(no)	Partie entière (inférieure)^[15]
COBOL	`FUNCTION REM`	Oui	Oui	Troncature^[15]
CoffeeScript	`%`	Oui	(no)	Troncature
CoffeeScript	`%%`	Oui	(no)	Partie entière (inférieure)^[16]
ColdFusion	`%`, `MOD`	Oui	(no)	Troncature
Common Intermediate Language	`rem` (signed)	Oui	Oui	Troncature^[17]
Common Intermediate Language	`rem.un` (unsigned)	Oui	(no)	NC
Common Lisp	`mod`	Oui	Oui	Partie entière (inférieure)
Common Lisp	`rem`	Oui	Oui	Troncature
Crystal (langage de programmation)	`%`, `modulo`	Oui	Oui	Partie entière (inférieure)
Crystal (langage de programmation)	`remainder`	Oui	Oui	Troncature
D (langage)	`%`	Oui	Oui	Troncature^[18]
Dart (langage)	`%`	Oui	Oui	Euclidienne^[19]
Dart (langage)	`remainder()`	Oui	Oui	Troncature^[20]
Eiffel (langage)	`\\`	Oui	(no)	Troncature
Elixir (langage)	`rem/2`	Oui	(no)	Troncature^[21]
Elixir (langage)	`Integer.mod/2`	Oui	(no)	Partie entière (inférieure)^[22]
Elm (langage)	`modBy`	Oui	(no)	Partie entière (inférieure)^[23]
Elm (langage)	`remainderBy`	Oui	(no)	Troncature^[24]
Erlang (langage)	`rem`	Oui	(no)	Troncature
Erlang (langage)	`math:fmod/2`	(no)	Oui	Troncature (identique au C)^[25]
Euphoria (langage)	`mod`	Oui	(no)	Partie entière (inférieure)
Euphoria (langage)	`remainder`	Oui	(no)	Troncature
F#	`%`	Oui	Oui	Troncature
F#	`Math.IEEERemainder`	(no)	Oui	Arrondie^[12]
Factor	`mod`	Oui	(no)	Troncature
FileMaker	`Mod`	Oui	(no)	Partie entière (inférieure)
Forth (langage)	`mod`	Oui	(no)	Dépends de l'implémentation
	`fm/mod`	Oui	(no)	Partie entière (inférieure)
	`sm/rem`	Oui	(no)	Troncature
Fortran	`mod`	Oui	Oui	Troncature
Fortran	`modulo`	Oui	Oui	Partie entière (inférieure)
Frink	`mod`	Oui	(no)	Partie entière (inférieure)
Full BASIC (standard ANSI) (en)	`MOD`	Oui	Oui	Partie entière (inférieure)^[26]
Full BASIC (standard ANSI) (en)	`REMAINDER`	Oui	Oui	Troncature^[27]
GLSL	`%`	Oui	(no)	Non défini^[28]
GLSL	`mod`	(no)	Oui	Partie entière (inférieure)^[29]
GameMaker Studio (GML)	`mod`, `%`	Oui	(no)	Troncature
GDScript (Godot)	`%`	Oui	(no)	Troncature
	`fmod`	(no)	Oui	Troncature
	`posmod`	Oui	(no)	Partie entière (inférieure)
	`fposmod`	(no)	Oui	Partie entière (inférieure)
Go (langage)	`%`	Oui	(no)	Troncature^[30]
	`math.Mod`	(no)	Oui	Troncature^[31]
	`big.Int.Mod`	Oui	(no)	Euclidienne^[32]
Groovy (langage)	`%`	Oui	(no)	Troncature
Haskell	`mod`	Oui	(no)	Partie entière (inférieure)^[33]
	`rem`	Oui	(no)	Troncature^[33]
	`Data.Fixed.mod'` (GHC)	(no)	Oui	Partie entière (inférieure)
Haxe	`%`	Oui	(no)	Troncature
HLSL	`%`	Oui	Oui	Non défini^[34]
J (langage)	`\|`^{[note 1]}	Oui	(no)	Partie entière (inférieure)
Java (langage)	`%`	Oui	Oui	Troncature
Java (langage)	`Math.floorMod`	Oui	(no)	Partie entière (inférieure)
JavaScript TypeScript	`%`	Oui	Oui	Troncature
Julia (langage)	`mod`	Oui	Oui	Partie entière (inférieure)^[35]
Julia (langage)	`%`, `rem`	Oui	Oui	Troncature^[36]
Kotlin (langage)	`%`, `rem`	Oui	Oui	Troncature^[37]
Kotlin (langage)	`mod`	Oui	Oui	Partie entière (inférieure)^[38]
ksh	`%`	Oui	(no)	Troncature (identique à POSIX sh)
ksh	`fmod`	(no)	Oui	Troncature
LabVIEW	`mod`	Oui	Oui	Troncature
LibreOffice	`=MOD()`	Oui	(no)	Partie entière (inférieure)
Logo (langage)	`MODULO`	Oui	(no)	Partie entière (inférieure)
Logo (langage)	`REMAINDER`	Oui	(no)	Troncature
Lua (langage) 5	`%`	Oui	Oui	Partie entière (inférieure)
Lua (langage) 4	`mod(x,y)`	Oui	Oui	Troncature
Liberty BASIC (en)	`MOD`	Oui	(no)	Troncature
Mathcad	`mod(x,y)`	Oui	(no)	Partie entière (inférieure)
Maple	`e mod m` (by default), `modp(e, m)`	Oui	(no)	Euclidienne
	`mods(e, m)`	Oui	(no)	Arrondie
	`frem(e, m)`	Oui	Oui	Arrondie
Mathematica	`Mod[a, b]`	Oui	(no)	Partie entière (inférieure)
MATLAB	`mod`	Oui	(no)	Partie entière (inférieure)
MATLAB	`rem`	Oui	(no)	Troncature
Maxima (logiciel)	`mod`	Oui	(no)	Partie entière (inférieure)
Maxima (logiciel)	`remainder`	Oui	(no)	Troncature
Maya Embedded Language	`%`	Oui	(no)	Troncature
Microsoft Excel	`=MOD()`	Oui	Oui	Partie entière (inférieure)
Minitab	`MOD`	Oui	(no)	Partie entière (inférieure)
Modula-2	`MOD`	Oui	(no)	Partie entière (inférieure)
Modula-2	`REM`	Oui	(no)	Troncature
MUMPS	`#`	Oui	(no)	Partie entière (inférieure)
Netwide Assembler (NASM, NASMX)	`%`, `div` (unsigned)	Oui	(no)	NC
Netwide Assembler (NASM, NASMX)	`%%` (signed)	Oui	(no)	Dépends de l'implémentation^[39]
Nim (langage)	`mod`	Oui	(no)	Troncature
Oberon (langage)	`MOD`	Oui	(no)	Proche de Partie entière (inférieure)^{[note 3]}
Objective-C	`%`	Oui	(no)	Troncature (identique à C99)
Object Pascal, Delphi (langage)	`mod`	Oui	(no)	Troncature
OCaml	`mod`	Oui	(no)	Troncature^[40]
OCaml	`mod_float`	(no)	Oui	Troncature^[41]
Occam (langage)	`\`	Oui	(no)	Troncature
Pascal (langage) (ISO-7185 and -10206)	`mod`	Oui	(no)	Proche de l'Euclidienne^{[note 4]}
Perl (langage)	`%`	Oui	(no)	Partie entière (inférieure)^{[note 5]}
Perl (langage)	`POSIX::fmod`	(no)	Oui	Troncature
Phix	`mod`	Oui	(no)	Partie entière (inférieure)
Phix	`remainder`	Oui	(no)	Troncature
PHP	`%`	Oui	(no)	Troncature^[43]
PHP	`fmod`	(no)	Oui	Troncature^[44]
PIC BASIC Pro	`\\`	Oui	(no)	Troncature
PL/I	`mod`	Oui	(no)	Partie entière (inférieure) (ANSI PL/I)
PowerShell	`%`	Oui	(no)	Troncature
Programming Code (PRC)	`MATH.OP - 'MOD; (\)'`	Oui	(no)	Undefined
Progress (Progress Software)	`modulo`	Oui	(no)	Troncature
Prolog (ISO 1995)	`mod`	Oui	(no)	Partie entière (inférieure)
Prolog (ISO 1995)	`rem`	Oui	(no)	Troncature
PureBasic	`%`, `Mod(x,y)`	Oui	(no)	Troncature
PureScript	`mod`	Oui	(no)	Euclidean^[45]
Pure Data	`%`	Oui	(no)	Troncature (same as C)
Pure Data	`mod`	Oui	(no)	Partie entière (inférieure)
Python	`%`	Oui	Oui	Partie entière (inférieure)
Python	`math.fmod`	(no)	Oui	Troncature
Q#	`%`	Oui	(no)	Troncature^[46]
R (langage)	`%%`	Oui	Oui	Partie entière (inférieure)^[47]
Racket	`modulo`	Oui	(no)	Partie entière (inférieure)
Racket	`remainder`	Oui	(no)	Troncature
Raku	`%`	(no)	Oui	Partie entière (inférieure)
RealBasic	`MOD`	Oui	(no)	Troncature
Reason	`mod`	Oui	(no)	Troncature
Rexx	`//`	Oui	Oui	Troncature
RPG	`%REM`	Oui	(no)	Troncature
Ruby	`%`, `modulo()`	Oui	Oui	Partie entière (inférieure)
Ruby	`remainder()`	Oui	Oui	Troncature
Rust	`%`	Oui	Oui	Troncature
Rust	`rem_euclid()`	Oui	Oui	Euclidienne^[48]
SAS	`MOD`	Oui	(no)	Troncature
Scala	`%`	Oui	Oui	Troncature
Scheme	`modulo`	Oui	(no)	Partie entière (inférieure)
Scheme	`remainder`	Oui	(no)	Troncature
Scheme R⁶RS	`mod`	Oui	(no)	Euclidienne^[49]
	`mod0`	Oui	(no)	Arrondie^[49]
	`flmod`	(no)	Oui	Euclidienne
	`flmod0`	(no)	Oui	Arrondie
Scratch	`mod`	Oui	Oui	Partie entière (inférieure)
Seed7	`mod`	Oui	Oui	Partie entière (inférieure)
Seed7	`rem`	Oui	Oui	Troncature
SenseTalk	`modulo`	Oui	(no)	Partie entière (inférieure)
SenseTalk	`rem`	Oui	(no)	Troncature
`sh` (POSIX) (includes bash, mksh, &c.)	`%`	Oui	(no)	Troncature (same as C)^[50]
Smalltalk	`\\`	Oui	(no)	Partie entière (inférieure)
Smalltalk	`rem:`	Oui	(no)	Troncature
Snap!	`mod`	Oui	(no)	Partie entière (inférieure)
Spin	`//`	Oui	(no)	Partie entière (inférieure)
Solidity	`%`	Oui	(no)	Partie entière (inférieure)
SQL (SQL:1999)	`mod(x,y)`	Oui	(no)	Troncature
SQL (SQL:2011)	`%`	Oui	(no)	Troncature
Standard ML	`mod`	Oui	(no)	Partie entière (inférieure)
	`Int.rem`	Oui	(no)	Troncature
	`Real.rem`	(no)	Oui	Troncature
Stata	`mod(x,y)`	Oui	(no)	Euclidienne
Swift	`%`	Oui	(no)	Troncature^[51]
	`remainder(dividingBy:)`	(no)	Oui	Arrondie^[52]
	`truncatingRemainder(dividingBy:)`	(no)	Oui	Troncature^[53]
Tcl	`%`	Oui	(no)	Partie entière (inférieure)
Tcl	`fmod()`	(no)	Oui	Troncature (as C)
tcsh	`%`	Oui	(no)	Troncature
Torque	`%`	Oui	(no)	Troncature
Turing	`mod`	Oui	(no)	Partie entière (inférieure)
Verilog (2001)	`%`	Oui	(no)	Troncature
VHDL	`mod`	Oui	(no)	Partie entière (inférieure)
VHDL	`rem`	Oui	(no)	Troncature
VimL	`%`	Oui	(no)	Troncature
Visual Basic	`Mod`	Oui	(no)	Troncature
WebAssembly	`i32.rem_u`, `i64.rem_u` (unsigned)	Oui	(no)	NC^[54]
WebAssembly	`i32.rem_s`, `i64.rem_s` (signed)	Oui	(no)	Troncature^[54]
x86 assembly	`IDIV`	Oui	(no)	Troncature
XBase++	`%`	Oui	Oui	Troncature
XBase++	`Mod()`	Oui	Oui	Partie entière (inférieure)
Zig	`%`, `@mod`, `@rem`	Oui	Oui	Troncature^[55]
Z3 theorem prover	`div`, `mod`	Oui	(no)	Euclidienne

Quelques détails concernant certains langages suivants la définition utilisant la partie entière inférieure[modifier | modifier le code]

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]. »

Quelques détails concernant certains langages suivants la définition utilisant la troncature[modifier | modifier le code]

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

Valeur d'un modulo 0 (valeur 'zéro')[modifier | modifier le code]

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.

Équivalence[modifier | modifier le code]

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$

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

↑ ^{a et b} Argument order reverses, i.e., α|ω computes $\omega {\bmod {\alpha }}$ , the remainder when dividing ω by α.
↑ C99 and C++11 define the behavior of % to be Troncature^[9]. The standards before then leave the behavior implementation-defined^[10].
↑ Divisor must be positive, otherwise undefined.
↑ As discussed by Boute, ISO Pascal (langage)'s definitions of div and mod do not obey the Division Identity of $D = d \cdot (D / d) + D % d$ , and are thus fundamentally broken.
↑ Perl (langage) usually uses arithmetic modulo operator that is machine-independent. For examples and exceptions, see the Perl documentation on multiplicative operators^[42].

Références[modifier | modifier le code]

↑ « Fonction modulo », sur IBM.com
↑ Brian W. Kernighan et Denis M. Ritchie, Le Langage C : Norme Ansi, Dunod, 2000, p. 41 - Les opérateurs arithmétiques
↑ 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.
↑ ^{a et b} « ISO/IEC 8652:2012 - Information technology — Programming languages — Ada », ISO, IEC,‎ 2012, sec. 4.5.5 Multiplying Operators
↑ ^{a et b} 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.
↑ « C99 specification (ISO/IEC 9899:TC2) », 6 mai 2005 (consulté le 16 août 2018), sec. 6.5.5 Multiplicative operators
↑ « ISO/IEC 14882:2003: Programming languages – C++ », International Organization for Standardization (ISO), International Electrotechnical Commission (IEC),‎ 2003, sec. 5.6.4 :
« the binary % operator yields the remainder from the division of the first expression by the second. .... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined »
↑ « ISO/IEC 9899:1990: Programming languages – C », ISO, IEC,‎ 1990, sec. 7.5.6.4 :
« The $fmod$ function returns the value $x - i * y$ , for some integer $i$ such that, if $y$ is nonzero, the result has the same sign as $x$ and magnitude less than the magnitude of $y$ . »
↑ ^{a et b} (en-US) dotnet-bot, « Math.IEEERemainder(Double, Double) Method (System) » (consulté le 4 octobre 2022)
↑ « clojure.core - Clojure v1.10.3 API documentation » (consulté le 16 mars 2022)
↑ « clojure.core - Clojure v1.10.3 API documentation », sur clojure.github.io (consulté le 16 mars 2022)
↑ ^{a et b} ISO/IEC JTC 1/SC 22/WG 4, ISO/IEC 1989:2023 – Programming language COBOL, ISO, janvier 2023 (lire en ligne )
↑ CoffeeScript operators
↑ ISO/IEC JTC 1/SC 22, ISO/IEC 23271:2012 — Information technology — Common Language Infrastructure (CLI), ISO, février 2012 (lire en ligne), §§ III.3.55–56
↑ « Expressions - D Programming Language », sur dlang.org (consulté le 1^er juin 2021)
↑ « operator % method - num class - dart:core library - Dart API », sur api.dart.dev (consulté le 1^er juin 2021)
↑ « remainder method - num class - dart:core library - Dart API », sur api.dart.dev (consulté le 1^er juin 2021)
↑ « Kernel — Elixir v1.11.3 », sur hexdocs.pm (consulté le 28 janvier 2021)
↑ « Integer — Elixir v1.11.3 », sur hexdocs.pm (consulté le 28 janvier 2021)
↑ « Basics - core 1.0.5 », sur package.elm-lang.org (consulté le 16 mars 2022)
↑ « Basics - core 1.0.5 », sur package.elm-lang.org (consulté le 16 mars 2022)
↑ « Erlang -- math », sur erlang.org (consulté le 1^er juin 2021)
↑ ANSI, Programming Languages — Full BASIC, New York, American National Standards Institute, 28 janvier 1987 (lire en ligne), § 5.4.4 :
« X modulo Y, i.e., X-Y*INT(X/Y). »
↑ ANSI, Programming Languages — Full BASIC, New York, American National Standards Institute, 28 janvier 1987 (lire en ligne), § 5.4.4 :
« "The remainder function, i.e., X-Y*IP(X/Y)." »
↑ « GLSL Language Specification, Version 4.50.7 » : « If both operands are non-negative, then the remainder is non-negative. Results are undefined if one or both operands are negative. », section 5.9 Expressions
↑ « GLSL Language Specification, Version 4.50.7 », section 8.3 Common Functions
↑ « The Go Programming Language Specification - The Go Programming Language », sur go.dev (consulté le 28 février 2022)
↑ « math package - math - pkg.go.dev », sur pkg.go.dev (consulté le 28 février 2022)
↑ « big package - math/big - pkg.go.dev », sur pkg.go.dev (consulté le 28 février 2022)
↑ ^{a et b} « 6 Predefined Types and Classes », sur www.haskell.org (consulté le 22 mai 2022)
↑ « Operators », Microsoft (consulté le 19 juillet 2021) : « The % operator is defined only in cases where either both sides are positive or both sides are negative. Unlike C, it also operates on floating-point data types, as well as integers. »
↑ « Mathematics · The Julia Language », sur docs.julialang.org (consulté le 20 novembre 2021)
↑ « Mathematics · The Julia Language », sur docs.julialang.org (consulté le 20 novembre 2021)
↑ (en) « rem - Kotlin Programming Language », sur Kotlin (consulté le 5 mai 2021)
↑ (en) « mod - Kotlin Programming Language », sur Kotlin (consulté le 5 mai 2021)
↑ « Chapter 3: The NASM Language », sur NASM - The Netwide Assembler version 2.15.05
↑ « OCaml library : Stdlib », sur ocaml.org (consulté le 19 février 2022)
↑ « OCaml library : Stdlib », sur ocaml.org (consulté le 19 février 2022)
↑ Perl documentation
↑ « PHP: Arithmetic Operators - Manual », sur www.php.net (consulté le 20 novembre 2021)
↑ « PHP: fmod - Manual », sur www.php.net (consulté le 20 novembre 2021)
↑ « EuclideanRing »
↑ (en-US) QuantumWriter, « Expressions », sur docs.microsoft.com (consulté le 11 juillet 2018)
↑ « R: Arithmetic Operators », sur search.r-project.org (consulté le 24 décembre 2022)
↑ « F32 - Rust »
↑ ^{a et b} r6rs.org
↑ « Shell Command Language », sur pubs.opengroup.org (consulté le 5 février 2021)
↑ « Apple Developer Documentation », sur developer.apple.com (consulté le 20 novembre 2021)
↑ « Apple Developer Documentation », sur developer.apple.com (consulté le 20 novembre 2021)
↑ « Apple Developer Documentation », sur developer.apple.com (consulté le 20 novembre 2021)
↑ ^{a et b} « WebAssembly Core Specification: Version 2.0 », World Wide Web Consortium, 19 avril 2022, § 4.3.2 Integer Operations
↑ « Zig Documentation », sur Zig Programming Language (consulté le 18 décembre 2022)
↑ "Why does -22 // 10 return -3?"
↑ (en) Michaël Van Canneyt, « Reference guide for Free Pascal, version 2.6.0 », décembre 2011.

Portail de l’informatique

[rev-8] {a et b} Argument order reverses, i.e., α|ω computes $\omega {\bmod {\alpha }}$ , the remainder when dividing ω by α.

[c-12] C99 and C++11 define the behavior of % to be Troncature^[9]. The standards before then leave the behavior implementation-defined^[10].

[42] Divisor must be positive, otherwise undefined.

[45] As discussed by Boute, ISO Pascal (langage)'s definitions of div and mod do not obey the Division Identity of $D = d \cdot (D / d) + D % d$ , and are thus fundamentally broken.

[47] Perl (langage) usually uses arithmetic modulo operator that is machine-independent. For examples and exceptions, see the Perl documentation on multiplicative operators^[42].

[1] « Fonction modulo », sur IBM.com

[2] Brian W. Kernighan et Denis M. Ritchie, Le Langage C : Norme Ansi, Dunod, 2000, p. 41 - Les opérateurs arithmétiques

[3] 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.

[portal.acm.org-4] 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.

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

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

[Ada-7] {a et b} « ISO/IEC 8652:2012 - Information technology — Programming languages — Ada », ISO, IEC,‎ 2012, sec. 4.5.5 Multiplying Operators

[ref_auto_1-9] {a et b} 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.

[C99-10] « C99 specification (ISO/IEC 9899:TC2) », 6 mai 2005 (consulté le 16 août 2018), sec. 6.5.5 Multiplicative operators

[11] « ISO/IEC 14882:2003: Programming languages – C++ », International Organization for Standardization (ISO), International Electrotechnical Commission (IEC),‎ 2003, sec. 5.6.4 :
« the binary % operator yields the remainder from the division of the first expression by the second. .... If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined »

[13] « ISO/IEC 9899:1990: Programming languages – C », ISO, IEC,‎ 1990, sec. 7.5.6.4 :
« The $fmod$ function returns the value $x - i * y$ , for some integer $i$ such that, if $y$ is nonzero, the result has the same sign as $x$ and magnitude less than the magnitude of $y$ . »

[.NET-14] {a et b} (en-US) dotnet-bot, « Math.IEEERemainder(Double, Double) Method (System) » (consulté le 4 octobre 2022)

[15] « clojure.core - Clojure v1.10.3 API documentation » (consulté le 16 mars 2022)

[16] « clojure.core - Clojure v1.10.3 API documentation », sur clojure.github.io (consulté le 16 mars 2022)

[isocobol-17] {a et b} ISO/IEC JTC 1/SC 22/WG 4, ISO/IEC 1989:2023 – Programming language COBOL, ISO, janvier 2023 (lire en ligne )

[CoffeeScript-18] CoffeeScript operators

[19] ISO/IEC JTC 1/SC 22, ISO/IEC 23271:2012 — Information technology — Common Language Infrastructure (CLI), ISO, février 2012 (lire en ligne), §§ III.3.55–56

[20] « Expressions - D Programming Language », sur dlang.org (consulté le 1^er juin 2021)

[21] « operator % method - num class - dart:core library - Dart API », sur api.dart.dev (consulté le 1^er juin 2021)

[22] « remainder method - num class - dart:core library - Dart API », sur api.dart.dev (consulté le 1^er juin 2021)

[23] « Kernel — Elixir v1.11.3 », sur hexdocs.pm (consulté le 28 janvier 2021)

[24] « Integer — Elixir v1.11.3 », sur hexdocs.pm (consulté le 28 janvier 2021)

[25] « Basics - core 1.0.5 », sur package.elm-lang.org (consulté le 16 mars 2022)

[26] « Basics - core 1.0.5 », sur package.elm-lang.org (consulté le 16 mars 2022)

[27] « Erlang -- math », sur erlang.org (consulté le 1^er juin 2021)

[28] ANSI, Programming Languages — Full BASIC, New York, American National Standards Institute, 28 janvier 1987 (lire en ligne), § 5.4.4 :
« X modulo Y, i.e., X-Y*INT(X/Y). »

[29] ANSI, Programming Languages — Full BASIC, New York, American National Standards Institute, 28 janvier 1987 (lire en ligne), § 5.4.4 :
« "The remainder function, i.e., X-Y*IP(X/Y)." »

[30] « GLSL Language Specification, Version 4.50.7 » : « If both operands are non-negative, then the remainder is non-negative. Results are undefined if one or both operands are negative. », section 5.9 Expressions

[31] « GLSL Language Specification, Version 4.50.7 », section 8.3 Common Functions

[32] « The Go Programming Language Specification - The Go Programming Language », sur go.dev (consulté le 28 février 2022)

[33] « math package - math - pkg.go.dev », sur pkg.go.dev (consulté le 28 février 2022)

[34] « big package - math/big - pkg.go.dev », sur pkg.go.dev (consulté le 28 février 2022)

[Haskell_2010-35] {a et b} « 6 Predefined Types and Classes », sur www.haskell.org (consulté le 22 mai 2022)

[36] « Operators », Microsoft (consulté le 19 juillet 2021) : « The % operator is defined only in cases where either both sides are positive or both sides are negative. Unlike C, it also operates on floating-point data types, as well as integers. »

[37] « Mathematics · The Julia Language », sur docs.julialang.org (consulté le 20 novembre 2021)

[38] « Mathematics · The Julia Language », sur docs.julialang.org (consulté le 20 novembre 2021)

[39] (en) « rem - Kotlin Programming Language », sur Kotlin (consulté le 5 mai 2021)

[40] (en) « mod - Kotlin Programming Language », sur Kotlin (consulté le 5 mai 2021)

[41] « Chapter 3: The NASM Language », sur NASM - The Netwide Assembler version 2.15.05

[43] « OCaml library : Stdlib », sur ocaml.org (consulté le 19 février 2022)

[44] « OCaml library : Stdlib », sur ocaml.org (consulté le 19 février 2022)

[46] Perl documentation

[48] « PHP: Arithmetic Operators - Manual », sur www.php.net (consulté le 20 novembre 2021)

[49] « PHP: fmod - Manual », sur www.php.net (consulté le 20 novembre 2021)

[purescript_euclid-50] « EuclideanRing »

[51] (en-US) QuantumWriter, « Expressions », sur docs.microsoft.com (consulté le 11 juillet 2018)

[52] « R: Arithmetic Operators », sur search.r-project.org (consulté le 24 décembre 2022)

[rust_rem_euclid-53] « F32 - Rust »

[r6rs-54] {a et b} r6rs.org

[55] « Shell Command Language », sur pubs.opengroup.org (consulté le 5 février 2021)

[56] « Apple Developer Documentation », sur developer.apple.com (consulté le 20 novembre 2021)

[57] « Apple Developer Documentation », sur developer.apple.com (consulté le 20 novembre 2021)

[58] « Apple Developer Documentation », sur developer.apple.com (consulté le 20 novembre 2021)

[wasmcs2-59] {a et b} « WebAssembly Core Specification: Version 2.0 », World Wide Web Consortium, 19 avril 2022, § 4.3.2 Integer Operations

[60] « Zig Documentation », sur Zig Programming Language (consulté le 18 décembre 2022)

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[note 1]

[8]

[note 2]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[note 3]

[40]

[41]

[note 4]

[note 5]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[9]

[10]

[42]