# Divisão euclidiana

Na aritmética, a divisão euclidiana (ou divisão com resto) é o processo de dividir um inteiro (o dividendo) por outro (o divisor), de forma que produza um quociente e um resto menor que o divisor. Uma propriedade fundamental é que o quociente e o resto existem e são únicos, sob algumas condições. Por causa dessa singularidade, a divisão euclidiana é frequentemente considerada sem referência a nenhum método de cálculo e sem calcular explicitamente o quociente e o resto. Os métodos de computação são chamados de algoritmos de divisão de inteiros, sendo o mais conhecido deles a divisão longa.
A divisão euclidiana e os algoritmos para calculá-la são fundamentais para muitas questões relativas a inteiros, como o algoritmo euclidiano para encontrar o maior divisor comum de dois inteiros, e aritmética modular, para a qual apenas restos são considerados. A operação que consiste em calcular apenas o resto é chamada de operação módulo, e é frequentemente usado em matemática e ciência da computação.

## Teorema da divisão

Dados dois inteiros $a$ e $b$, com $b\neq 0$, existem inteiros únicos $q$ e $r$ tais que
    $a=bq+r$
e
    $0\leq r<|b|$,
onde $|b|$ denota o valor absoluto de $b$.
No teorema acima, cada um dos quatro inteiros tem um nome próprio: $a$ é chamado de dividendo, $b$ é chamado de divisor, $q$ é chamado de quociente e $r$ é chamado de resto.
O cálculo do quociente e do resto do dividendo e do divisor é chamado de divisão ou — em caso de ambiguidade — divisão euclidiana. O teorema é frequentemente referido como algoritmo de divisão (embora seja um teorema e não um algoritmo), porque sua demonstração, conforme fornecida a seguir, se presta a um algoritmo de divisão simples para calcular $q$ e $r$.
A divisão não é definida no caso em que $b=0$; (veja a divisão por zero).
Para o resto e a operação módulo, existem convenções diferentes de $0\leq r<|b|$.

## História

Antes da descoberta do sistema de numeração hindu-arábica, que foi introduzido na Europa durante o século XIII por Fibonacci, a divisão era extremamente difícil, e apenas os melhores matemáticos eram capazes de fazê-la. Atualmente, a maioria dos algoritmos de divisão, incluindo divisão longa, são baseados nesta notação ou em suas variantes, como numerais binários. Uma exceção notável é a divisão Newton-Raphson, que é independente de qualquer sistema numérico.
O termo "divisão euclidiana" foi introduzido durante o século XX como uma abreviação para "divisão dos anéis euclidianos". Foi rapidamente adotado por matemáticos para distinguir esta divisão de outros tipos de divisão de números.$^[$

## Exemplo intuitivo

Suponha que uma torta tenha 9 fatias e elas sejam divididas igualmente entre 4 pessoas. Usando a divisão euclidiana, 9 dividido por 4 é 2 com o resto 1. Em outras palavras, cada pessoa recebe 2 fatias de torta, e sobra 1 fatia.
Isso pode ser confirmado usando a multiplicação—o inverso da divisão: se cada uma das 4 pessoas recebeu 2 fatias, então $4\times 2=8$ fatias foram dadas no total. Adicionando 1 fatia restante, o resultado são 9 fatias. Em resumo: $9=4\times 2+1$.
Em geral, se o número de fatias é denotado por $a$ e o número de pessoas é denotado por $b$, então pode-se dividir a torta igualmente entre as pessoas, de modo que cada pessoa receba $q$ fatias (o quociente), com algum número de fatias $r<b$ sendo a sobra (o resto). Nesse caso, a equação $a=bq+r$ permanece válida.
Como um exemplo alternativo, se 9 fatias fossem divididas entre 3 pessoas em vez de 4, cada uma receberia 3 e nenhuma fatia sobraria, o que significa que o resto seria zero, levando à conclusão de que 3 divide 9 igualmente, ou que 3 divide 9.
A divisão euclidiana também pode ser estendida para dividendo negativo (ou divisor negativo) usando a mesma fórmula; por exemplo, $-9=4\times (-3)+3$, o que significa que −9 dividido por 4 é −3 com resto 3.

## Exemplos

* Se $a=7$ e $b=3$, então $q=2$ e $r=1$, já que $7=3\times 2+1$.
* Se $a=7$ e $b=-3$, então $q=-2$ e $r=1$, já que $7=-3\times (-2)+1$.
* Se $a=-7$ e $b=3$, então $q=-3$ e $r=2$, já que $-7=3\times (-3)+2$.
* Se $a=-7$ e $b=-3$, então $q=3$ e $r=2$, já que $-7=-3\times 3+2$.

## Prova

A seguinte prova do teorema da divisão se baseia no fato de que uma sequência decrescente de inteiros não negativos para eventualmente. Ele é separado em duas partes: uma para existência e outra para unicidade de $q$ e $r$. Outras provas usam o princípio de boa ordenação (ou seja, a afirmação de que todo conjunto não vazio de inteiros não negativos tem um menor elemento) para tornar o raciocínio mais simples, mas têm a desvantagem de não fornecer diretamente um algoritmo para resolver a divisão.

### Existência

Considere primeiro o caso $b<0$. Definindo $b'=-b$ e $q'=-q$, a equação $a=bq+r$ pode ser reescrita como $a=b'q'+r$ e a desigualdade $0\leq r<|b|$ pode ser reescrita como $0\leq r<|b'|$. Isso reduz a existência do caso $b<0$ àquela do caso $b>0$.
Da mesma forma, se $a<0$ e $b>0$, definindo $a'=-a$, $q'=-q-1$ e $r'=b-r$, a equação $a=bq+r$ pode ser reescrita como $a'=bq'+r'$, e a desigualdade $0\leq r<|b|$ pode ser reescrito como $0\leq r'<|b|$. Assim, a prova da existência fica reduzida ao caso $a\geq 0$ e $b>0$ — que será considerado no restante da prova.
Sejam $q_{1}=0$ e $r_{1}=a$, então esses são números não negativos tais que $a=bq_{1}+r_{1}$. Se $r_{1}<b$, então a divisão está completa, então suponha que $r_{1}\geq b$. Então, definindo $q_{2}=q_{1}+1$ e $r_{2}=r_{1}-b$, temos $a=bq_{2}+r_{2}$ com $0\leq r_{2}<r_{1}$. Como existem apenas $r_{1}$ inteiros não negativos menores que $r_{1}$, basta repetir este processo no máximo $r_{1}$ vezes para atingir o quociente final e o resto. Ou seja, existe um número natural $k\leq r_{1}$ tal que $a=bq_{k}+r_{k}$ e $0\leq r_{k}<|b|$.
Isso prova a existência e também fornece um algoritmo de divisão simples para calcular o quociente e o restante. Porém, este algoritmo não é eficiente, pois seu número de passos é da ordem de $a/b$.

### Unicidade

O par de inteiros $r$ e $q$ tais que $a=bq+r$ é único, no sentido de que não pode haver outro par de inteiros que satisfaça a mesma condição no teorema da divisão euclidiana. Em outras palavras, se temos outra divisão de $a$ por $b$, digamos $a=bq'+r'$ com $0\leq r'<|b|$, então devemos ter isso
    $q'=q$ e $r'=r$.
Para provar esta afirmação, primeiro começamos com as suposições de que
    $0\leq r<|b|$
    $0\leq r'<|b|$
    $a=bq+r$
    $a=bq'+r'$
Subtraindo as duas equações resulta
    $b(q-q')=r'-r$.
Portanto, $b$ é um divisor de $r'-r$. Como
    $|r'-r|<|b|$
pelas desigualdades acima, obtém-se
    $r'-r=0$,
e
    $b(q-q')=0$.
Como $b\neq 0$, obtemos que $r=r'$ e $q=q'$, o que prova a parte da unicidade do teorema da divisão euclidiana.

## Eficácia

Em geral, uma prova de existência não fornece um algoritmo para calcular o quociente existente e o resto, mas a prova acima fornece imediatamente um algoritmo, embora não seja muito eficiente, pois requer tantos passos quanto o tamanho do quociente. Isso está relacionado ao fato de que utiliza apenas adições, subtrações e comparações de inteiros, sem envolver multiplicação, nem qualquer representação particular dos inteiros, como notação decimal.
Em termos de notação decimal, a divisão longa fornece um algoritmo muito mais eficiente para resolver as divisões euclidianas. Sua generalização para notação binária e hexadecimal fornece mais flexibilidade e possibilidade de implementação em computador. No entanto, para grandes entradas, algoritmos que reduzem a divisão à multiplicação, como Newton-Raphson, são geralmente preferidos, porque eles só precisam de um tempo que é proporcional ao tempo da multiplicação necessária para verificar o resultado—independentemente do algoritmo de multiplicação que é usado.

## Variantes

A divisão euclidiana admite uma série de variantes, algumas das quais estão listadas abaixo.

### Outros intervalos para o resto

Na divisão euclidiana com $d$ como divisor, o resto deve pertencer ao intervalo $[0,d)$ de comprimento $|d|$. Qualquer outro intervalo de mesmo comprimento pode ser usado. Mais precisamente, dados inteiros $m$, $a$, $d$ com $m>0$, existem inteiros únicos $q$ e $r$ com $d\leq r<m+d$ tal que $a=mq+r$.
Em particular, se $d=-\left\lfloor {\frac {m}{2}}\right\rfloor$ então $-\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor$ . Essa divisão é chamada de divisão centralizada e seu resto $r$ é chamado de resto centralizado ou o menor resto absoluto.
Isso é usado para aproximar números reais: a divisão euclidiana define o truncamento e a divisão centralizada define o arredondamento.

### Divisão de Montgomery

Dados inteiros $a$, $m$ e $R,$ com $m>0$ e $\mathrm {mdc} (R,m)=1,$ seja $R^{-1}$ o inverso multiplicativo modular de $R$ (i.e., $0<R^{-1}<m$ com $R^{-1}R-1$ sendo um múltiplo de $m$), então existem inteiros únicos $q$ e $r$ com $0\leq r<m$ tal que $a=mq+R^{-1}\cdot r$. Este resultado generaliza a divisão ímpar de Hensel (1900).
O valor $r$ é o $N$-ésimo resíduo definido na redução de Montgomery.

## Em domínios euclidianos

Domínios euclidianos (também conhecidos como anéis euclidianos) são definidos como domínios integrais que suportam a seguinte generalização da divisão euclidiana:
    Dado um elemento $a$ e um elemento $b$ diferente de zero em um domínio euclidiano $R$ equipado com uma função euclidiana $d$ (também conhecida como avaliação euclidiana ou função de grau), existem $q$ e $r$ em $R$ tais que $a=bq+r$ e $r=0$ ou $d(r)<d(b)$.
A exclusividade de $q$ e $r$ não é necessária. Ocorre apenas em casos excepcionais, normalmente para polinômios univariados e para inteiros, se a condição adicional $r\geq 0$ for adicionada.
Exemplos de domínios euclidianos incluem corpos, anéis polinomiais em uma variável sobre um corpo e os inteiros gaussianos. A divisão euclidiana de polinômios tem sido objeto de desenvolvimentos específicos.