# Operació mòdul

En informàtica, l'operació mòdul troba el residu de la divisió d'un nombre entre un altre (aquest residu també se sol anomenar mòdul).
Donats dos nombres positius, a (el dividend) i n (el divisor), a mòdul n (abreujat com a mod n) és el residu de la divisió euclidiana de a entre n. Per exemple, l'expressió "5 mod 2" té com a resultat 1, perquè 5 dividit entre 2 dona un quocient de 2 i un residu d'1, mentre que "9 mod 3" té com a resultat 0, perquè la divisió de 9 entre 3 té un quocient de 3 i un residu de 0; no cal restar res de 9 després de multiplicar 3 per 3. Noteu que si es realitza la divisió amb una calculadora convencional, no es mostrarà el resultat indicat anteriorment, sinó que s'expressarà el quocient en forma de fracció decimal.
Encara que aquesta operació acostuma a realitzar-se entre dos nombres naturals, molts sistemes de computació permeten altres tipus d'operands numèrics. El rang de nombres que pot adoptar el mòdul va des de 0 fins a n − 1. (n mod 1 sempre és 0; n mod 0 no està definit, causant un error "Divisió per zero" en els llenguatges de programació).
Quan a o bé n són negatius, la definició intuïtiva que hem vist no es pot aplicar, i els diferents llenguatges de programació ofereixen diferents resultats.

## Càlcul del residu per a l'operació mòdul

Operadors mòdul enters en diversos llenguatges de programació :
| Llenguatge | Operador | El resultat té el mateix signe que el... |
| ActionScript | % | Dividend |
| Ada | mod | Divisor |
| Ada | rem | Dividend |
| ASP | Mod | Indefinit |
| ALGOL-68 | ÷×, mod | Sempre positiu |
| AMPL | mod | Dividend |
| APL | | | Divisor |
| AppleScript | mod | Dividend |
| Assemblador x86 | IDIV | Dividend |
| AWK | % | Dividend |
| BASIC | Mod | Indefinit |
| bash | % | Dividend |
| bc | % | Dividend |
| C (ISO 1990) | % | Segons la implementació |
| C (ISO 1990) | div | Dividend |
| C++ (ISO 1998) | % | Segons la implementació |
| C++ (ISO 1998) | div | Dividend |
| C (ISO 1999) | %, div | Dividend |
| C++ (ISO 2011) | %, div | Dividend |
| C# | % | Dividend |
| CLARION | % | Dividend |
| Clojure | mod | Divisor |
| COBOL | FUNCTION MOD | Divisor |
| CoffeeScript | % | Dividend |
| CoffeeScript | %% | Divisor |
| ColdFusion | %, MOD | Dividend |
| Common Lisp | mod | Divisor |
| Common Lisp | rem | Dividend |
| D | % | Dividend |
| Dart | % | Sempre positiu |
| Dart | remainder | Dividend |
| Eiffel | \\ | Dividend |
| Erlang | rem | Dividend |
| Euphoria | mod | Divisor |
| Euphoria | remainder | Dividend |
| F# | % | Dividend |
| FileMaker | Mod | Divisor |
| Forth | mod | Segons la implementació |
| Fortran | mod | Dividend |
| Fortran | modulo | Divisor |
| Frink | mod | Divisor |
| GML (Game Maker) | mod | Dividend |
| GDScript | % | Dividend |
| Go | % | Dividend |
| Haskell | mod | Divisor |
| Haskell | rem | Dividend |
| Haxe | % | Dividend |
| J | |~ | Divisor |
| Java | % | Dividend |
| Java | Math.floorMod | Divisor |
| JavaScript | % | Dividend |
| Julia | mod | Divisor |
| Julia | rem | Dividend |
| LibreOffice | =MOD | Divisor |
| Lua 5 | % | Divisor |
| Lua 4 | mod(x,y) | Divisor |
| Liberty BASIC | MOD | Dividend |
| MathCAD | mod(x,y) | Divisor |
| Maple | e mod m | Sempre positiu |
| Mathematica | Mod | Divisor |
| MATLAB | mod | Divisor |
| MATLAB | rem | Dividend |
| Maxima | mod | Divisor |
| Maxima | remainder | Dividend |
| Maya Embedded Language | % | Dividend |
| Microsoft Excel | =MOD | Divisor |
| Minitab | MOD | Divisor |
| mksh | % | Dividend |
| Modula-2 | MOD | Divisor |
| MUMPS | # | Divisor |
| NASM NASMX | % | Operador mòdul sense signe |
| NASM NASMX | %% | Operador mòdul amb signe |
| Oberon | MOD | Divisor |
| OCaml | mod | Dividend |
| Occam | \ | Dividend |
| Pascal (Delphi) | mod | Dividend |
| Pascal (ISO-7185 and ISO-10206) | mod | Sempre positiu |
| Perl | % | Divisor |
| PHP | % | Dividend |
| PIC Basic Pro | \\ | Dividend |
| PL/I | mod | Divisor (ANSI PL/I) |
| PowerShell | % | Dividend |
| Progress | modulo | Dividend |
| Prolog (ISO 1995) | mod | Divisor |
| Prolog (ISO 1995) | rem | Dividend |
| Python | % | Divisor |
| Python | math.fmod | Dividend |
| Racket | remainder | Dividend |
| RealBasic | MOD | Dividend |
| R | %% | Divisor |
| REXX | // | Dividend |
| RPG | %REM | Dividend |
| Ruby | %, modulo | Divisor |
| Ruby | remainder | Dividend |
| Rust | % | Dividend |
| Scala | % | Dividend |
| Scheme | modulo | Divisor |
| Scheme | remainder | Dividend |
| Scheme R⁶RS | mod | Sempre positiu |
| Scheme R⁶RS | mod0 | El més pròxim a zero |
| Seed7 | mod | Divisor |
| Seed7 | rem | Dividend |
| SenseTalk | modulo | Divisor |
| SenseTalk | rem | Dividend |
| Smalltalk | \\ | Divisor |
| Smalltalk | rem: | Dividend |
| SQL (SQL:1999) | mod(x,y) | Dividend |
| Standard ML | mod | Divisor |
| Standard ML | Int.rem | Dividend |
| Stata | mod(x,y) | Sempre positiu |
| Swift | % | Dividend |
| Tcl | % | Divisor |
| Torque Game Engine | % | Dividend |
| Turing | mod | Divisor |
| Verilog (2001) | % | Dividend |
| VHDL | mod | Divisor |
| VHDL | rem | Dividend |
| Visual Basic | Mod | Dividend |
| Xbase++ | % | Dividend |
| Xbase++ | Mod | Divisor |
| Z3 theorem prover | div, mod | Sempre positiu |
Operadors mòdul en coma flotant en diversos llenguatges de programació :
| Llenguatge | Operador | El resultat té el mateix signe que el... |
| C (ISO 1990) | fmod | Dividend |
| C (ISO 1999) | fmod | Dividend |
| C (ISO 1999) | remainder | El més pròxim a zero |
| C++ (ISO 1998) | std::fmod | Dividend |
| C++ (ISO 2011) | std::fmod | Dividend |
| C++ (ISO 2011) | std::remainder | El més pròxim a zero |
| C# | % | Dividend |
| Common Lisp | mod | Divisor |
| Common Lisp | rem | Dividend |
| D | % | Dividend |
| Dart | % | Sempre positiu |
| Dart | remainder | Dividend |
| F# | % | Dividend |
| Fortran | mod | Dividend |
| Fortran | modulo | Divisor |
| Go | math.Mod | Dividend |
| Haskell (GHC) | Data.Fixed.mod' | Divisor |
| Java | % | Dividend |
| JavaScript | % | Dividend |
| Microsoft Excel | =MOD | Divisor |
| OCaml | mod_float | Dividend |
| Perl | POSIX::fmod | Dividend |
| Perl6 | % | Divisor |
| PHP | fmod | Dividend |
| Python | % | Divisor |
| Python | math.fmod | Dividend |
| REXX | // | Dividend |
| Ruby | %, modulo | Divisor |
| Ruby | remainder | Dividend |
| Scheme R⁶RS | flmod | Sempre positiu |
| Scheme R⁶RS | flmod0 | El més pròxim a zero |
| Standard ML | Real.rem | Dividend |
| Swift | % | Dividend |
| Xbase++ | % | Dividend |
| Xbase++ | Mod | Divisor |
En matemàtiques, el resultat de l'operació mòdul és el residu de la divisió euclidiana, encara que són possibles altres convencions. Els ordinadors i les calculadores tenen diferents maneres d'emmagatzemar i representar els nombres i, per tant, la seva definició de l'operació mòdul depèn del llenguatge de programació i/o del maquinari subjacent.
En gairebé tots els sistemes de computació, el quocient q i el residu r de a dividit per n satisfà
    ${\begin{aligned}q\,&\in \mathbb {Z} \\a\,&=nq+r\\|r|\,&<|n|.\end{aligned}}$         (1)
Tot i aquestes condicions, encara existeix una ambigüitat respecte al signe si el residu és diferent de zero: hi ha dues opcions possibles per al residu, una amb signe negatiu i l'altra amb signe positiu, i també hi ha dues opcions per al quocient. En teoria de nombres, hom acostuma a escollir el residu amb signe positiu, però l'elecció dels llenguatges de programació depèn del llenguatge i dels signes de a i/o n. Les implementacions estàndard de Pascal i Algol68 proporcionen un residu positiu (o 0) fins i tot per a divisors negatius, i alguns llenguatges de programació, com C90, deixen l'elecció del signe del residu a cada implementació, en el cas on n o a són negatius (vegeu la taula per a més detalls). L'operació a mòdul 0 resta indefinida per a la majoria de sistemes, encara que alguns d'ells la defineixen per tal que el resultat sigui a.
* Moltes implementacions empren la divisió truncada, on es defineix el quocient per truncament q = trunc(a/n), i per tant, d'acord amb l'equació (1), el residu hauria de tenir el mateix signe que el dividend. El quocient s'arrodoneix cap a zero: igual al primer enter en la direcció del zero des del quocient racional exacte.
       $r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)$
* Donald Knuth descriu la divisió arrodonida ((anglès) floored division) on el quocient ve definit per la funció part entera q = ⌊a/n⌋, i per l'equació (1), el residu hauria de tenir el mateix signe que el divisor. A causa del comportament de la funció part entera, el quocient sempre s'arrodoneix cap a baix, fins i tot si és negatiu.
       $r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor$
* Raymond T. Boute descriu la definició euclidiana en la qual el residu és sempre no-negatiu, 0 ≤ r i, per tant, és consistent amb l'algorisme de divisió euclidiana. Aquesta convenció està simbolitzada per Sempre negatiu
* a la taula. En aquest cas,
       $n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor$
       $n<0\Rightarrow q=\left\lceil {\frac {a}{n}}\right\rceil$
    o equivalentment
       $q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor$
    on sgn és la funció signe, i per tant
       $r=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor$.
* Common Lisp també defineix la divisió arrodonida i la divisió entera per dalt ((anglès) ceiling-division), on la divisió ve donada per q = round(a/n) i q = ceil(a/n) respectivament.
* IEEE 754 defineix una funció residu on el quocient és a/n arrodonit cap a la convenció més propera. Per tant, el signe del residu s'escull per tal que sigui el més pròxim a zero.
Com descriu Leijen,
| « | (anglès) Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition. Despite its widespread use, truncated division is shown to be inferior to the other definitions. | (català) Boute argumenta que la divisió euclidiana és superior a les altres, en termes de regularitat i utilitat de les seves propietats matemàtiques, encara que la divisió arrodonida, recomanada per Knuth, també és una bona definició. Tot i el seu ús generalitzat, s'ha vist que la divisió truncada és inferior a les altres definicions. | » |
| — Daan Leijen, Division and Modulus for Computer Scientists ||||

## Malentesos comuns

Quan el resultat de l'operaciò mòdul té el signe del dividend, de vegades pot portar a resultats sorprenents.
Per exemple, per comprovar si un nombre és senar, hom podria pensar a comprovar si el residu de la divisió entre 2 dona 1:
Però en un llenguatge on el mòdul té el signe del dividend, aquesta implementació és incorrecta, perquè quan n (el dividend) és negatiu i senar, n % 2 retorna −1, i la funció retorna fals.
Una alternativa correcta és comprovar que el residu no és 0 (perquè un residu 0 és independent del signe dels operands):
O bé tenint en compte que, per a un nombre senar, el residu pot ser 1 o −1:

## Expressió de l'operació mòdul

Algunes calculadores tenen un botó de funció mod , i molts llenguatges de programació tenen una funció mod o similar, expressada com mod(a, n), per exemple. Alguns suporten també expressions que usen "%", "mod", o "Mod" com a operador mòdul o residu, com
    a % n
o
    a mod n
o equivalentment, en entorns que no disposen d'una funció mod (notem que 'int' retorna la part entera de a/n):
    a - (n * int(a/n)).

## Cost computacional

És possible implementar les operacions mòdul de manera que, a cada pas, es calculi una divisió amb residu. Però en casos especials, existeixen alternatives més ràpides sobre certs tipus de maquinari. Per exemple, el residu de potències de 2 també es pot expressar en forma d'operació AND bit a bit:
    x % 2$^n$ == x & (2$^n$ - 1).
Exemples (suposant que x és un enter positiu):
    x % 2 == x & 1
    x % 4 == x & 3
    x % 8 == x & 7.
En dispositus i programes que implementen les operacions bit a bit de forma més ràpida que les operacions mòdul, aquestes alternatives proporcionen càlculs més ràpids.
Els compiladors optimitzadors poden reconèixer expressions de la forma expressió % constant on constant és una potència de 2, i llavors implementar-les com expressió & (constant-1). Això permet al programador escriure codi més senzill i sense penalitzar el rendiment. (Nota: Aquesta aproximació no funciona per a llenguatges on el residu té el signe del dividend –com ara C–, perquè si el dividend és negatiu, llavors el residu serà negatiu, però expressió & (constant-1) sempre retornarà un resultat positiu; de tal manera que cal fer un tractament especial per al cas on el dividend pot ser negatiu.)

## Equivalències

Algunes operacions mòdul es poden factoritzar o desenvolupar, de la mateixa manera que altres operacions matemàtiques. Això pot ser útil en demostracions de criptografia, com l'intercanvi de claus Diffie-Hellman.
* Identitat:
** $(a\,{\bmod {\,}}n)\,{\bmod {\,}}n=a\,{\bmod {\,}}n$
** $n^{x}\,{\bmod {\,}}n=0$ per a tots els valors enters positius de $x$.
** Si $n$ és un nombre primer que no és un divisor de $b$, llavors $ab^{n-1}\,{\bmod {\,}}n=a\,{\bmod {\,}}n$, a causa del petit teorema de Fermat.
* Invers:
** $((-a\,{\bmod {\,}}n)+(a\,{\bmod {\,}}n))\,{\bmod {\,}}n=0$
** $b^{-1}\,{\bmod {\,}}n$ denota l'invers multiplicatiu modular, que està definit si i només si $b$ i $n$ són coprimers, que és el cas en què el primer terme està definit: $((b^{-1}\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n=1$.
* Distributivitat:
** $(a+b)\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)+(b\,{\bmod {\,}}n))\,{\bmod {\,}}n$
** $ab\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n$
* Divisió (definició): ${\frac {a}{b}}\,{\bmod {\,}}n=((a\,{\bmod {\,}}n)(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n$, quan el segon terme està definit, i indefinit altrament.
* Invers multiplicatiu: $((ab\,{\bmod {\,}}n)\,(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n=a\,{\bmod {\,}}n$

## Notes

* ↑ Tal com està implementat en ACUCOBOL, Micro Focus COBOL, i possiblement altres.
* 1 2 El divisor ha de ser positiu, altrament no està definit.
* ↑ Habitualment, Perl utilitza una aritmètica per al càlcul de l'operador mòdul que és independent de màquina. Vegeu la documentació de Perl per a excepcions i exemples.
* ↑ Des d'un punt de vista matemàtic, aquestes són només dues opcions d'entre el nombre infinit d'opcions per a la desigualtat satisfeta pel residu.

## Referències

* ↑ «ISO/IEC 14882:2003 : Programming languages -- C++». ISO, IEC, 2003.. "l'operador binari % proporciona el residu de la divisió de la primera expressió entre la segona. [...] Si tots dos operands són no-negatius, llavors el residu és no-negatiu; altrament, el signe del residu depèn de la implementació" ((anglès) "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")
* ↑ open-std.org, section 6.5.5
* ↑ CoffeeScript operators
* ↑ «Expressions». D Programming Language 2.0. Digital Mars. [Consulta: 29 juliol 2010].
* 1 2 r6rs.org
* ↑ «ISO/IEC 9899:1990 : Programming languages -- C». ISO, IEC, 1990.. "The fmod function returns the value x - i * y, for some integer i such that, if y is nonzero, the result as the same sign as x and magnitude less than the magnitude of y.".
* ↑ Knuth, Donald. E.. The Art of Computer Programming. Addison-Wesley, 1972. ISBN 0-201-89683-4.
* ↑ Boute, Raymond T. «The Euclidean definition of the functions div and mod». ACM Transactions on Programming Languages and Systems (TOPLAS). ACM Press (New York, NY, USA), 14, 2, abril 1992, pàg. 127–144. DOI: 10.1145/128861.128862.
* ↑ Leijen, Daan. «Division and Modulus for Computer Scientists» (PDF), 03-12-2001. [Consulta: 25 desembre 2014].
* ↑ Horvath, Adam. «Faster division and modulo operation - the power of two», 05-07-2012.

## Vegeu també

* Mòdul (desambiguació)
* Exponenciació modular