Mostrar código-fonte de Divisão euclidiana

[[Ficheiro:Euclidean_division_example.svg|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, <math>17 = (5 \times 3) + 2</math>]]
Na [[aritmética]], a '''divisão euclidiana''' (ou '''divisão com resto''') é o processo de [[Divisão|dividir]] um [[Número inteiro|inteiro]] (o dividendo) por outro (o divisor), de forma que produza um quociente e um resto menor que o divisor.<ref name=":0">{{citar web|último = |primeiro = |url=https://mathvault.ca/long-division/ |título=The Definitive Higher Math Guide to Long Division and Its Variants — for Integers |data=2019-02-24 |website=Math Vault |língua=en-US |arquivourl= |arquivodata= |urlmorta= não|acessodata=2019-11-15}}</ref> 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 [[Máximo divisor comum|maior divisor comum]] de dois inteiros,<ref name=":1">{{citar web|url=http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L6.html |título=Division and Euclidean algorithms |website=www-groups.mcs.st-andrews.ac.uk |acessodata=2019-11-15}}</ref> e [[aritmética modular]], para a qual apenas restos são considerados.<ref>{{citar web|url=https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic |título=What is modular arithmetic? |website=Khan Academy |língua=en |acessodata=2019-11-15}}</ref> A operação que consiste em calcular apenas o resto é chamada de ''[[operação módulo]]'',<ref>{{citar web|url=https://betterexplained.com/articles/fun-with-modular-arithmetic/ |título=Fun With Modular Arithmetic – BetterExplained |website=betterexplained.com |acessodata=2019-11-15}}</ref> e é frequentemente usado em [[matemática]] e [[ciência da computação]].

[[Ficheiro:Pie_division.svg|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 <math>a</math> e <math>b</math>, com <math>b \neq 0</math>, existem inteiros únicos <math>q</math> e <math>r</math> tais que

: <math>a = bq + r</math>

e

: <math>0 \leq r < |b|</math>,

onde <math>|b|</math> denota o [[Valor absoluto (álgebra)|valor absoluto]] de <math>b</math>.<ref>{{citar livro|título=Elementary Number Theory|último =Burton|primeiro =David M.|isbn=978-0-07-338314-9|ano=2010|publicado=McGraw-Hill|páginas=17–19}}</ref>

No [[teorema]] acima, cada um dos quatro inteiros tem um nome próprio: <math>a</math> é chamado de ''dividendo'', <math>b</math> é chamado de ''divisor'', <math>q</math> é chamado de ''quociente'' e <math>r</math> é chamado de ''resto''.<ref name=":0" />

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 <math>q</math> e <math>r</math>.

A divisão não é definida no caso em que <math>b = 0</math>; <small>(veja a [[divisão por zero]])</small>.

Para o resto e a [[operação módulo]], existem convenções diferentes de <math>0 \leq r < |b|</math>.

== História ==
Antes da descoberta do sistema de [[Sistema numérico hindu-arábico|numeração hindu-arábica]], que foi introduzido na [[Europa]] durante o [[século XIII]] por [[Leonardo Fibonacci|Fibonacci]], a divisão era extremamente difícil, e apenas os melhores matemáticos eram capazes de fazê-la.<ref>{{citar web|url=https://www.storyofmathematics.com/medieval_fibonacci.html |título=Fibonacci - Medieval Mathematics - The Story of Mathematics |website=www.storyofmathematics.com |acessodata=2019-11-15}}</ref> Atualmente, a maioria dos algoritmos de divisão, incluindo divisão longa, são baseados nesta notação ou em suas variantes, como [[Sistema de numeração binário|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 [[Domínio euclidiano|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|data=novembro de 2019}}

== 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 <math>4 \times 2 = 8</math> fatias foram dadas no total. Adicionando 1 fatia restante, o resultado são 9 fatias. Em resumo: <math>9 = 4 \times 2 + 1</math>.

Em geral, se o número de fatias é denotado por <math>a</math> e o número de pessoas é denotado por ''<math>b</math>'', então pode-se dividir a torta igualmente entre as pessoas, de modo que cada pessoa receba ''<math>q</math>'' fatias (o quociente), com algum número de fatias <math>r < b</math> sendo a sobra (o resto). Nesse caso, a equação <math>a = bq + r</math> 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;<ref name=":0" /> por exemplo, <math>-9 = 4 \times (-3) + 3</math>, o que significa que −9 dividido por 4 é −3 com resto 3.

== Exemplos ==

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

== 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 <math>q</math> e <math>r</math>. Outras provas usam o [[Princípio da boa ordenaçã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.<ref>{{citar livro|url=http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP000258.html|título=Modern Algebra : an Introduction|último =Durbin|primeiro =John R.|isbn=0-471-51001-7|ano=1992|publicado=Wiley|local=New York|página=63|edição=3rd}}</ref>

=== Existência ===

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

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

Sejam <math>q_1 = 0</math> e <math>r_1 = a</math>, então esses são números não negativos tais que <math>a = bq_1 + r_1</math>. Se <math>r_1 <b</math>, então a divisão está completa, então suponha que <math>r_1 \geq b</math>. Então, definindo <math>q_2 = q_1 + 1</math> e <math>r_2 = r_1 - b</math>, temos <math>a = bq_2 + r_2</math> com <math>0 \leq r_2 <r_1</math>. Como existem apenas <math>r_1</math> inteiros não negativos menores que <math>r_1</math>, basta repetir este processo no máximo <math>r_1</math> vezes para atingir o quociente final e o resto. Ou seja, existe um número natural <math>k \leq r_1</math> tal que <math>a = bq_k + r_k</math> e <math>0 \leq r_k < |b|</math>.

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 <math>a / b</math>.

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

: <math>q' = q</math> e <math>r' = r</math>.

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

: <math>0 \leq r < |b|</math>
: <math>0 \leq r' < |b|</math>
: <math>a = bq + r</math>
: <math>a = bq' + r'</math>

Subtraindo as duas equações resulta

: <math>b(q - q') = r' - r</math>.

Portanto, <math>b</math> é um divisor de <math>r' - r</math>. Como

: <math>|r' - r| < |b|</math>

pelas desigualdades acima, obtém-se

: <math>r' - r = 0</math>,

e

: <math>b(q - q') = 0</math>.

Como <math>b \neq 0</math>, obtemos que <math>r = r'</math> e <math>q = q'</math>, 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ção|adições]], [[Subtração|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 [[Sistema de numeração binário|notação binária]] e [[Sistema de numeração hexadecimal|hexadecimal]] fornece mais flexibilidade e possibilidade de implementação em [[computador]].<ref name=":0" /> 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 <math>d</math> como divisor, o resto deve pertencer ao intervalo <math>[0, d)</math> de comprimento <math>| d |</math>. Qualquer outro intervalo de mesmo comprimento pode ser usado. Mais precisamente, dados inteiros <math>m</math>, <math>a</math>, <math>d</math> com <math>m>0</math>, existem inteiros únicos <math>q</math> e <math>r</math> com <math>d \le r < m+d </math> tal que <math>a = mq+r</math>.

Em particular, se <math> d=- \left\lfloor \frac{m}{2} \right\rfloor </math> então <math> - \left\lfloor \frac{m}{2} \right\rfloor  \le r < m-\left\lfloor \frac{m}{2} \right\rfloor </math> . Essa divisão é chamada de ''divisão centralizada'' e seu resto <math>r</math> é chamado de ''resto centralizado'' ou o ''menor resto absoluto''.

Isso é usado para aproximar [[Número real|números reais]]: a divisão euclidiana define o [[truncamento]] e a divisão centralizada define o [[arredondamento]].

=== Divisão de Montgomery ===
{{main|Multiplicação modular de Montgomery}}
Dados inteiros <math>a</math>, <math>m</math> e <math>R,</math> com <math>m >0</math> e <math>\mathrm{mdc}(R,m) =1,</math> seja <math>R^{-1}</math> o [[inverso multiplicativo]] modular de <math>R</math> (i.e., <math> 0<R^{-1}<m</math> com <math>R^{-1}R-1</math> sendo um múltiplo de <math>m</math>), então existem inteiros únicos <math>q</math> e <math>r</math> com <math>0 \le r < m </math> tal que <math> a = mq+R^{-1} \cdot r </math>. Este resultado generaliza a divisão ímpar de [[Kurt Hensel|Hensel]] (1900).<ref>{{citar periódico|autor1 =Haining Fan |autor2 =Ming Gu |autor3 =Jiaguang Sun |autor4 =Kwok-Yan Lam |título=Obtaining More Karatsuba-Like Formulae over the Binary Field |periódico=IET Information Security |volume=6 |número=1 |páginas=14–19 |ano=2012 |citeseerx=10.1.1.215.1576 |doi=10.1049/iet-ifs.2010.0114}}</ref>

O valor <math>r</math> é o <math>N</math>-ésimo resíduo definido na [[redução de Montgomery]].

== Em domínios euclidianos ==
[[Domínio euclidiano|Domínios euclidianos]] (também conhecidos como '''anéis euclidianos''')<ref name="Rot06">{{harvnb|Rotman|2006|loc=p. 267}}</ref> são definidos como domínios integrais que suportam a seguinte generalização da divisão euclidiana:

: Dado um elemento <math>a</math> e um elemento <math>b</math> diferente de zero em um domínio euclidiano <math>R</math> equipado com uma '''função euclidiana''' <math>d</math> (também conhecida como '''avaliação euclidiana'''<ref>{{harvnb|Fraleigh|1993|loc=p. 376}}</ref> ou '''função de grau'''<ref name="Rot06" />), existem <math>q</math> e <math>r</math> em <math>R</math> tais que <math>a = bq + r</math> e <math>r = 0</math> ou <math>d (r) <d (b)</math>.

A exclusividade de <math>q</math> e <math>r</math> não é necessária.<ref name=":1" /> Ocorre apenas em casos excepcionais, normalmente para [[Polinômio univariado|polinômios univariados]] e para inteiros, se a condição adicional <math>r \geq 0</math> for adicionada.

Exemplos de domínios euclidianos incluem [[Corpo (matemática)|corpos]], [[Anel de polinômios|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 ==
{{reflist}}

== Referências ==

* {{citation|primeiro =John B.|último =Fraleigh|título=A First Course in Abstract Algebra|edição=5th|ano=1993|publicado=Addison-Wesley|isbn=978-0-201-53467-2}}
* {{citation|primeiro =Joseph J.|último =Rotman|título=A First Course in Abstract Algebra with Applications|edição=3rd|ano=2006|publicado=Prentice-Hall|isbn=978-0-13-186267-8}}
{{Portal3|matemática}}
[[Categoria:Aritmética]]