Divisão euclidiana

17 é dividido em 3 grupos de 5, com 2 como sobras. Aqui, o dividendo é 17, o divisor é 5, o quociente é 3 e o resto é 2 (que é estritamente menor que o divisor 5) ou, mais simbolicamente, $17=(5\times 3)+2$

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.

A torta tem 9 fatias, então cada uma das 4 pessoas recebe 2 fatias e 1 sobra

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.^{[carece de fontes]}

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

Ver artigo principal: Multiplicação modular 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 campos, anéis polinomiais em uma variável sobre um campo e os inteiros gaussianos. A divisão euclidiana de polinômios tem sido objeto de desenvolvimentos específicos.

Referências

• Fraleigh, John B. (1993), A First Course in Abstract Algebra, ISBN 978-0-201-53467-2 5th ed. , Addison-Wesley 
• Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications, ISBN 978-0-13-186267-8 3rd ed. , Prentice-Hall