Resto

En aritmética o resto ou residuo dunha división de dous números enteiros é o número que se lle debe restar ao dividendo para que sexa igual a un determinado número de veces o divisor. Equivalentemente, é o número resultante da diferenza do dividendo co produto do divisor polo cociente.

${\mbox{Resto=Dividendo}}-{\mbox{(divisor}}\times {\mbox{cociente)}}$

Segundo o seu resto as divisións clasifícanse como exactas, se o seu resto é cero, ou enteiras, cando non o é.

Xeralmente o resto de dividir x entre y adóitase expresar como $\textstyle x{\mbox{ mod }}y$. Por exemplo $\textstyle 2=17{\mbox{ mod }}5$.

En aritmética modular escríbese $x\equiv r{\pmod {y}}$, onde x é o residuo e lese "x é equivalente a r módulo y". Por exemplo $17\equiv 2{\pmod {5}}$, temos que 17 é equivalente a 2 módulo 5, quere dicir, que se dividimos 17 entre 5 temos 2 como residuo.

En termos da función chan $\lfloor x\rfloor$, o resto pódese definir como:

$x{\mbox{ mod }}y:=x-y\left\lfloor {\frac {x}{y}}\right\rfloor$

Por exemplo, $4{\mbox{ mod }}5:=4-5\left\lfloor {\frac {4}{5}}\right\rfloor =4-5\cdot 0=4$.

A expresión x mod 0 fica sen definir na maioría dos sistemas numéricos, aínda que algúns a definen como igual a x.

Implementación para o cálculo do resto

Para números pequenos adóitase implementar a función indicada anteriormente, que é moi sinxela. Para a implementación con números grandes, existen métodos moito máis eficientes, como o algoritmo de redución de Montgomery e a redución de Barrett. A redución de Barrett aproveita o feito de que existen números q e r, de maneira que x = mq+r e 0 ≤ r < m (véxase Algoritmo da división), e utilízao para estimar q usando só operacións de percorrido en lugar de divisións.

Redución de Barrett:

Entradas:

$x=\left(x_{2k-1}\cdots x_{1}x_{0}\right)_{b}$ ($x$ en forma de lista de díxitos). $m=\left(m_{k-1}\cdots m_{1},m_{0}\right)_{b}$ con $m_{k-1}\neq 0$ ($m$ en forma de lista de díxitos).

$\mu =\left\lfloor {\frac {b^{2k}}{m}}\right\rfloor$.

Saída: $x{\mbox{ mod }}m\,$

---

1. $q_{1}\gets \left\lfloor x/b^{k-1}\right\rfloor$
2. $q_{2}\gets q_{1}\times \mu$
3. $q_{3}\gets \left\lfloor q_{2}/b^{k-1}\right\rfloor$
4. $r_{1}\gets x{\mbox{ mod }}b^{k+1}$
5. $r_{2}\gets q_{3}\times m{\mbox{ mod }}b^{k+1}$
6. $r\gets r_{1}-r_{2}$
7. Se $r<0\,$ entón:
   1. $r\gets r+b^{k-1}$
8. Mentres $r\geq m$ faga o seguinte:
   1. $r\gets r-m$
9. Devolva $r$

Véxase tamén

Bibliografía

• Ore, Oystein (1988) [1948]. Number Theory and Its History. Dover. ISBN 978-0-486-65620-5. 

Outras lecturas

• Davenport, Harold (1999). The higher arithmetic: an introduction to the theory of numbers. Cambridge, UK: Cambridge University Press. p. 25. ISBN 0-521-63446-6. 
• Katz, Victor, ed. (2007). The mathematics of Egypt, Mesopotamia, China, India, and Islam : a sourcebook. Princeton: Princeton University Press. ISBN 9780691114859. 
• Zuckerman, Martin M (December 1998). Arithmetic: A Straightforward Approach. Lanham, Md: Rowman & Littlefield Publishers, Inc. ISBN 0-912675-07-1. 

Outros artigos

• aritmética modular.
• división longa.

Ligazóns externas

• Weisstein, Eric W. "Remainder". MathWorld.