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.^[1] 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,^[2] e aritmética modular, para a qual apenas restos são considerados.^[3] A operação que consiste em calcular apenas o resto é chamada de operação módulo,^[4] e é frequentemente usado em matemática e ciência da computação.

Teorema da divisão

Dados dois inteiros ${\displaystyle a}$ e ${\displaystyle b}$, com ${\displaystyle b\neq 0}$, existem inteiros únicos ${\displaystyle q}$ e ${\displaystyle r}$ tais que

${\displaystyle a=bq+r}$

e

${\displaystyle 0\leq r<|b|}$,

onde ${\displaystyle |b|}$ denota o valor absoluto de ${\displaystyle b}$.^[5]

No teorema acima, cada um dos quatro inteiros tem um nome próprio: ${\displaystyle a}$ é chamado de dividendo, ${\displaystyle b}$ é chamado de divisor, ${\displaystyle q}$ é chamado de quociente e ${\displaystyle r}$ é chamado de resto.^[1]

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 ${\displaystyle q}$ e ${\displaystyle r}$.

A divisão não é definida no caso em que ${\displaystyle b=0}$; (veja a divisão por zero).

Para o resto e a operação módulo, existem convenções diferentes de ${\displaystyle 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.^[6] 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 ${\displaystyle 4\times 2=8}$ fatias foram dadas no total. Adicionando 1 fatia restante, o resultado são 9 fatias. Em resumo: ${\displaystyle 9=4\times 2+1}$.

Em geral, se o número de fatias é denotado por ${\displaystyle a}$ e o número de pessoas é denotado por ${\displaystyle b}$, então pode-se dividir a torta igualmente entre as pessoas, de modo que cada pessoa receba ${\displaystyle q}$ fatias (o quociente), com algum número de fatias ${\displaystyle r<b}$ sendo a sobra (o resto). Nesse caso, a equação ${\displaystyle 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;^[1] por exemplo, ${\displaystyle -9=4\times (-3)+3}$, o que significa que −9 dividido por 4 é −3 com resto 3.

Exemplos

• Se ${\displaystyle a=7}$ e ${\displaystyle b=3}$, então ${\displaystyle q=2}$ e ${\displaystyle r=1}$, já que ${\displaystyle 7=3\times 2+1}$.
• Se ${\displaystyle a=7}$ e ${\displaystyle b=-3}$, então ${\displaystyle q=-2}$ e ${\displaystyle r=1}$, já que ${\displaystyle 7=-3\times (-2)+1}$.
• Se ${\displaystyle a=-7}$ e ${\displaystyle b=3}$, então ${\displaystyle q=-3}$ e ${\displaystyle r=2}$, já que ${\displaystyle -7=3\times (-3)+2}$.
• Se ${\displaystyle a=-7}$ e ${\displaystyle b=-3}$, então ${\displaystyle q=3}$ e ${\displaystyle r=2}$, já que ${\displaystyle -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 ${\displaystyle q}$ e ${\displaystyle 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.^[7]

Existência

Considere primeiro o caso ${\displaystyle b<0}$. Definindo ${\displaystyle b'=-b}$ e ${\displaystyle q'=-q}$, a equação ${\displaystyle a=bq+r}$ pode ser reescrita como ${\displaystyle a=b'q'+r}$ e a desigualdade ${\displaystyle 0\leq r<|b|}$ pode ser reescrita como ${\displaystyle 0\leq r<|b'|}$. Isso reduz a existência do caso ${\displaystyle b<0}$ àquela do caso ${\displaystyle b>0}$.

Da mesma forma, se ${\displaystyle a<0}$ e ${\displaystyle b>0}$, definindo ${\displaystyle a'=-a}$, ${\displaystyle q'=-q-1}$ e ${\displaystyle r'=b-r}$, a equação ${\displaystyle a=bq+r}$ pode ser reescrita como ${\displaystyle a'=bq'+r'}$, e a desigualdade ${\displaystyle 0\leq r<|b|}$ pode ser reescrito como ${\displaystyle 0\leq r'<|b|}$. Assim, a prova da existência fica reduzida ao caso ${\displaystyle a\geq 0}$ e ${\displaystyle b>0}$ — que será considerado no restante da prova.

Sejam ${\displaystyle q_{1}=0}$ e ${\displaystyle r_{1}=a}$, então esses são números não negativos tais que ${\displaystyle a=bq_{1}+r_{1}}$. Se ${\displaystyle r_{1}<b}$, então a divisão está completa, então suponha que ${\displaystyle r_{1}\geq b}$. Então, definindo ${\displaystyle q_{2}=q_{1}+1}$ e ${\displaystyle r_{2}=r_{1}-b}$, temos ${\displaystyle a=bq_{2}+r_{2}}$ com ${\displaystyle 0\leq r_{2}<r_{1}}$. Como existem apenas ${\displaystyle r_{1}}$ inteiros não negativos menores que ${\displaystyle r_{1}}$, basta repetir este processo no máximo ${\displaystyle r_{1}}$ vezes para atingir o quociente final e o resto. Ou seja, existe um número natural ${\displaystyle k\leq r_{1}}$ tal que ${\displaystyle a=bq_{k}+r_{k}}$ e ${\displaystyle 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 ${\displaystyle a/b}$.

Unicidade

O par de inteiros ${\displaystyle r}$ e ${\displaystyle q}$ tais que ${\displaystyle 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 ${\displaystyle a}$ por ${\displaystyle b}$, digamos ${\displaystyle a=bq'+r'}$ com ${\displaystyle 0\leq r'<|b|}$, então devemos ter isso

${\displaystyle q'=q}$ e ${\displaystyle r'=r}$.

Para provar esta afirmação, primeiro começamos com as suposições de que

${\displaystyle 0\leq r<|b|}$

${\displaystyle 0\leq r'<|b|}$

${\displaystyle a=bq+r}$

${\displaystyle a=bq'+r'}$

Subtraindo as duas equações resulta

${\displaystyle b(q-q')=r'-r}$.

Portanto, ${\displaystyle b}$ é um divisor de ${\displaystyle r'-r}$. Como

${\displaystyle |r'-r|<|b|}$

pelas desigualdades acima, obtém-se

${\displaystyle r'-r=0}$,

e

${\displaystyle b(q-q')=0}$.

Como ${\displaystyle b\neq 0}$, obtemos que ${\displaystyle r=r'}$ e ${\displaystyle 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.^[1] 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 ${\displaystyle d}$ como divisor, o resto deve pertencer ao intervalo ${\displaystyle [0,d)}$ de comprimento ${\displaystyle |d|}$. Qualquer outro intervalo de mesmo comprimento pode ser usado. Mais precisamente, dados inteiros ${\displaystyle m}$, ${\displaystyle a}$, ${\displaystyle d}$ com ${\displaystyle m>0}$, existem inteiros únicos ${\displaystyle q}$ e ${\displaystyle r}$ com ${\displaystyle d\leq r<m+d}$ tal que ${\displaystyle a=mq+r}$.

Em particular, se ${\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }$ então ${\displaystyle -\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 ${\displaystyle 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 ${\displaystyle a}$, ${\displaystyle m}$ e ${\displaystyle R,}$ com ${\displaystyle m>0}$ e ${\displaystyle \mathrm {mdc} (R,m)=1,}$ seja ${\displaystyle R^{-1}}$ o inverso multiplicativo modular de ${\displaystyle R}$ (i.e., ${\displaystyle 0<R^{-1}<m}$ com ${\displaystyle R^{-1}R-1}$ sendo um múltiplo de ${\displaystyle m}$), então existem inteiros únicos ${\displaystyle q}$ e ${\displaystyle r}$ com ${\displaystyle 0\leq r<m}$ tal que ${\displaystyle a=mq+R^{-1}\cdot r}$. Este resultado generaliza a divisão ímpar de Hensel (1900).^[8]

O valor ${\displaystyle r}$ é o ${\displaystyle N}$-ésimo resíduo definido na redução de Montgomery.

Em domínios euclidianos

Domínios euclidianos (também conhecidos como anéis euclidianos)^[9] são definidos como domínios integrais que suportam a seguinte generalização da divisão euclidiana:

Dado um elemento ${\displaystyle a}$ e um elemento ${\displaystyle b}$ diferente de zero em um domínio euclidiano ${\displaystyle R}$ equipado com uma função euclidiana ${\displaystyle d}$ (também conhecida como avaliação euclidiana^[10] ou função de grau^[9]), existem ${\displaystyle q}$ e ${\displaystyle r}$ em ${\displaystyle R}$ tais que ${\displaystyle a=bq+r}$ e ${\displaystyle r=0}$ ou ${\displaystyle d(r)<d(b)}$.

A exclusividade de ${\displaystyle q}$ e ${\displaystyle r}$ não é necessária.^[2] Ocorre apenas em casos excepcionais, normalmente para polinômios univariados e para inteiros, se a condição adicional ${\displaystyle 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.

Notas

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 

• Portal da matemática