Divisão euclidiana

teorema

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.

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,

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.

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

Teorema da divisãoEditar

Dados dois inteiros   e  , com  , existem inteiros únicos   e   tais que

 

e

 ,

onde   denota o valor absoluto de  .[5]

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.[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   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óriaEditar

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 intuitivoEditar

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;[1] por exemplo,  , o que significa que −9 dividido por 4 é −3 com resto 3.

ExemplosEditar

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

ProvaEditar

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.[7]

ExistênciaEditar

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  .

UnicidadeEditar

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áciaEditar

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.

VariantesEditar

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

Outros intervalos para o restoEditar

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 MontgomeryEditar

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).[8]

O valor   é o  -ésimo resíduo definido na redução de Montgomery.

Em domínios euclidianosEditar

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

A exclusividade de   e   não é necessária.[2] 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 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.

NotasEditar

  1. a b c d «The Definitive Higher Math Guide to Long Division and Its Variants — for Integers». Math Vault (em inglês). 24 de fevereiro de 2019. Consultado em 15 de novembro de 2019 
  2. a b «Division and Euclidean algorithms». www-groups.mcs.st-andrews.ac.uk. Consultado em 15 de novembro de 2019 
  3. «What is modular arithmetic?». Khan Academy (em inglês). Consultado em 15 de novembro de 2019 
  4. «Fun With Modular Arithmetic – BetterExplained». betterexplained.com. Consultado em 15 de novembro de 2019 
  5. Burton, David M. (2010). Elementary Number Theory. [S.l.]: McGraw-Hill. pp. 17–19. ISBN 978-0-07-338314-9 
  6. «Fibonacci - Medieval Mathematics - The Story of Mathematics». www.storyofmathematics.com. Consultado em 15 de novembro de 2019 
  7. Durbin, John R. (1992). Modern Algebra : an Introduction 3rd ed. New York: Wiley. p. 63. ISBN 0-471-51001-7 
  8. Haining Fan; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). «Obtaining More Karatsuba-Like Formulae over the Binary Field». IET Information Security. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576 . doi:10.1049/iet-ifs.2010.0114 
  9. a b Rotman 2006, p. 267
  10. Fraleigh 1993, p. 376

ReferênciasEditar

  • 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