miniaturadaimagem|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, 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.

miniaturadaimagem|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 e , com , existem inteiros únicos e tais que

e

,

onde denota o valor absoluto de .

No teorema acima, cada um dos quatro inteiros tem um nome próprio: é chamado de dividendo, é chamado de divisor, é chamado de quociente e é 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 e .

A divisão não é definida no caso em que ; (veja a divisão por zero).

Para o resto e a operação módulo, existem convenções diferentes de .

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 fatias foram dadas no total. Adicionando 1 fatia restante, o resultado são 9 fatias. Em resumo: .

Em geral, se o número de fatias é denotado por e o número de pessoas é denotado por , então pode-se dividir a torta igualmente entre as pessoas, de modo que cada pessoa receba fatias (o quociente), com algum número de fatias sendo a sobra (o resto). Nesse caso, a equação 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, , o que significa que −9 dividido por 4 é −3 com resto 3.

Exemplos

Se e , então e , já que . Se e , então e , já que . Se e , então e , já que . Se e , então e , já que .

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 e . 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 . Definindo e , a equação pode ser reescrita como e a desigualdade pode ser reescrita como . Isso reduz a existência do caso àquela do caso .

Da mesma forma, se e , definindo , e , a equação pode ser reescrita como , e a desigualdade pode ser reescrito como . Assim, a prova da existência fica reduzida ao caso e — que será considerado no restante da prova.

Sejam e , então esses são números não negativos tais que . Se , então a divisão está completa, então suponha que . Então, definindo e , temos com . Como existem apenas inteiros não negativos menores que , basta repetir este processo no máximo vezes para atingir o quociente final e o resto. Ou seja, existe um número natural tal que e .

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 .

Unicidade O par de inteiros e tais que é ú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 por , digamos com , então devemos ter isso

e .

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

Subtraindo as duas equações resulta

.

Portanto, é um divisor de . Como

pelas desigualdades acima, obtém-se

,

e

.

Como , obtemos que e , 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 como divisor, o resto deve pertencer ao intervalo de comprimento . Qualquer outro intervalo de mesmo comprimento pode ser usado. Mais precisamente, dados inteiros , , com , existem inteiros únicos e com tal que .

Em particular, se então . Essa divisão é chamada de divisão centralizada e seu resto é 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 , e com e seja o inverso multiplicativo modular de (i.e., com sendo um múltiplo de ), então existem inteiros únicos e com tal que . Este resultado generaliza a divisão ímpar de Hensel (1900).

O valor é o -é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 e um elemento diferente de zero em um domínio euclidiano equipado com uma função euclidiana (também conhecida como avaliação euclidiana ou função de grau), existem e em tais que e ou .

A exclusividade de e não é necessária. Ocorre apenas em casos excepcionais, normalmente para polinômios univariados e para inteiros, se a condição adicional 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.

Notas

Referências

Categoria:Aritmética