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.^[1] Equivalentemente, é o número resultante da diferenza do dividendo co produto do divisor polo cociente.

${\displaystyle {\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 ${\displaystyle \textstyle x{\mbox{ mod }}y}$. Por exemplo ${\displaystyle \textstyle 2=17{\mbox{ mod }}5}$.

En aritmética modular escríbese ${\displaystyle x\equiv r{\pmod {y}}}$, onde x é o residuo e lese "x é equivalente a r módulo y". Por exemplo ${\displaystyle 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 ${\displaystyle \lfloor x\rfloor }$, o resto pódese definir como:

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

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

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:

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

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

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

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

Wikimedia Commons ten máis contidos multimedia na categoría:  Resto

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

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

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

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