Operació mòdul

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à

${\displaystyle {\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.^{[nota 4]} 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.

${\displaystyle r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)}$ 

• Donald Knuth^[7] 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.

${\displaystyle r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor }$ 

• Raymond T. Boute^[8] 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,

${\displaystyle n>0\Rightarrow q=\left\lfloor {\frac {a}{n}}\right\rfloor }$ 

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

o equivalentment

${\displaystyle q=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor }$ 

on sgn és la funció signe, i per tant

${\displaystyle 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,

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:

bool es_senar(int n) {
 return n % 2 == 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):

bool es_senar(int n) {
 return n % 2 != 0;
}

O bé tenint en compte que, per a un nombre senar, el residu pot ser 1 o −1:

bool es_senar(int n) {
 return n % 2 == 1 || n % 2 == -1;
}

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

É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 % 2n == x & (2n - 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.^[10]

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

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:
  • ${\displaystyle (a\,{\bmod {\,}}n)\,{\bmod {\,}}n=a\,{\bmod {\,}}n}$ 
  • ${\displaystyle n^{x}\,{\bmod {\,}}n=0}$  per a tots els valors enters positius de ${\displaystyle x}$ .
  • Si ${\displaystyle n}$  és un nombre primer que no és un divisor de ${\displaystyle b}$ , llavors ${\displaystyle ab^{n-1}\,{\bmod {\,}}n=a\,{\bmod {\,}}n}$ , a causa del petit teorema de Fermat.
• Invers:
  • ${\displaystyle ((-a\,{\bmod {\,}}n)+(a\,{\bmod {\,}}n))\,{\bmod {\,}}n=0}$ 
  • ${\displaystyle b^{-1}\,{\bmod {\,}}n}$  denota l'invers multiplicatiu modular, que està definit si i només si ${\displaystyle b}$  i ${\displaystyle n}$  són coprimers, que és el cas en què el primer terme està definit: ${\displaystyle ((b^{-1}\,{\bmod {\,}}n)\,(b\,{\bmod {\,}}n))\,{\bmod {\,}}n=1}$ .
• Distributivitat:
  • ${\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}$ 
• Divisió (definició): ${\displaystyle {\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: ${\displaystyle ((ab\,{\bmod {\,}}n)\,(b^{-1}\,{\bmod {\,}}n))\,{\bmod {\,}}n=a\,{\bmod {\,}}n}$ 

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