O Algoritmo da Divisão

Nesta aula desenvolveremos o algoritmo da divisão como o princípio que formaliza, para inteiros, a decomposição única b=qa+r com 0\le r<|a|. Demonstra-se primeiro a existência do quociente e do resto e, em seguida, a sua unicidade. Por fim, interpreta-se o significado do resto, relaciona-se a teoria com o algoritmo longo da divisão como procedimento de cálculo e antecipa-se a sua conexão natural com a aritmética modular e aplicações computacionais.

Objetivos de Aprendizagem

Ao completar esta aula, o estudante será capaz de:

1. Identificar os conceitos e papéis básicos da divisão inteira (dividendo, divisor, quociente, resto) e a noção de divisibilidade como caso exato.
2. Explicar o enunciado do algoritmo/teorema da divisão euclidiana, incluindo as condições que fixam o resto (0\le r<|a|) e o seu propósito para evitar ambiguidades.
3. Aplicar a decomposição euclidiana b=qa+r para determinar q e r em exemplos concretos, verificando a cota do resto.
4. Analisar o tratamento de casos de acordo com o sinal do dividendo e do divisor, justificando por que a convenção euclidiana mantém um resto não negativo.
5. Executar o algoritmo longo da divisão como procedimento mecânico baseado na representação posicional para obter q e r.

ÍNDICE DE CONTEÚDOS:
Divisão e divisibilidade
Teorema da divisão euclidiana
Demonstração da divisão euclidiana
Interpretação do quociente e do resto
Algoritmo longo da divisão
Conclusão
Exercícios propostos e resolvidos

Divisão e divisibilidade

Em aritmética, a divisibilidade descreve o caso «exato»: a\mid b significa que b se escreve exatamente como múltiplo de a. No entanto, embora nem sempre haja divisibilidade entre dois inteiros quaisquer, ainda podemos perguntar-nos «quantas vezes um número cabe dentro de outro e, se não o faz exatamente, o que é que sobra». Este é o contexto em que surge o algoritmo da divisão, que garante que um inteiro qualquer b pode ser escrito como um múltiplo de a mais um «resto».

Como exemplo, consideremos a=3 e b=16. É claro que 3 não divide 16. No entanto, é possível encontrar um quociente e um resto para a operação de divisão, pois

16 = 5\cdot 3 + 1

Em consequência, ao dividir b=16 por a=3 (onde b é o dividendo e a é o divisor), representado por 16/3 ou 16\div 3, obtém-se como quociente q=5 e como resto r=1. Em geral, o algoritmo da divisão afirma que, para quaisquer inteiros a (divisor) e b (dividendo) com a\neq 0, existem inteiros únicos q e r tais que

b=qa+r,\qquad 0\le r<|a|

Neste exemplo, 16=3\cdot 5+1, e a condição 0\le r<|a| é satisfeita porque 0\le 1<3. Essa formulação evita ambiguidades quando o divisor (ou o dividendo) pode ser negativo e garante que o resto seja sempre não negativo e estritamente menor que o valor absoluto do divisor.

Teorema da divisão euclidiana

O resultado de aplicar o algoritmo da divisão é o que se conhece como divisão euclidiana e fundamenta-se no seguinte resultado.

Teorema: Sejam a,b\in\mathbb{Z} com a\neq 0. Então existem q,r\in\mathbb{Z} únicos tais que

b=qa+r,\qquad 0\le r<|a|.

O inteiro q chama-se quociente e r chama-se resto da divisão de b por a.

Demonstração da divisão euclidiana

Esta demonstração divide-se em duas partes: primeiro demonstra-se que o quociente e o resto existem; e, em seguida, dado que existem, são únicos.

Existência

Sejam a,b\in\mathbb{Z} com a\neq 0 e definamos d=|a|, de modo que d>0. Provaremos primeiro o caso b\ge 0: mostraremos que existem q,r\in\mathbb{Z} tais que b=dq+r e 0\le r<d. Em seguida, trataremos o caso b<0. Ao final, substituiremos d por |a| para obter a forma b=qa+r com 0\le r<|a|.

Para b\in\mathbb{Z} com b\ge 0, estabelecemos a proposição P(b): «existem q,r\in\mathbb{Z} tais que b=dq+r e 0\le r<d». Demonstraremos por indução que P(b) é válida para todo b\ge 0.

Caso base: Para b=0, tomando q=0 e r=0 obtém-se 0=d\cdot 0+0 e 0\le 0<d. Portanto, P(0) é verdadeira.

Passo indutivo: Seja k\ge 0 e suponhamos que P(k) é verdadeira. Então existem q,r\in\mathbb{Z} tais que

k=dq+r,\qquad 0\le r<d.

Somando 1 a ambos os lados, obtém-se

k+1=dq+(r+1).

Além disso, de 0\le r<d segue-se que r+1\le d. Em consequência, apenas podem ocorrer os casos r+1<d ou r+1=d.

Caso 1: Se r+1<d, definimos q'=q e r'=r+1. Então

k+1=dq'+r',\qquad 0\le r'<d.

Caso 2: Se r+1=d, então k+1=dq+d=d(q+1)+0. Definimos q'=q+1 e r'=0, e verifica-se que

k+1=dq'+r',\qquad 0\le r'<d.

Em ambos os casos, construímos inteiros q',r' tais que k+1=dq'+r' e 0\le r'<d. Portanto, P(k+1) é verdadeira. Concluímos por indução que P(b) vale para todo b\ge 0.

Agora consideremos o caso b<0. Então -b>0. Aplicando o resultado anterior a -b, existem q,r\in\mathbb{Z} tais que

-b=dq+r,\qquad 0\le r<d.

Multiplicando por -1, obtém-se

b=-dq-r.

Se r=0, basta tomar q_1=-q e r_1=0, com o que b=dq_1+r_1 e 0\le r_1<d.

Se r>0, definimos q_1=-q-1 e r_1=d-r. Como 0<r<d, tem-se 0<d-r<d, isto é, 0\le r_1<d. Além disso,

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

Em consequência, para todo b\in\mathbb{Z} existem q_1,r_1\in\mathbb{Z} tais que b=dq_1+r_1 e 0\le r_1<d.

Por fim, recordemos que d=|a|. Se a>0, então d=a e a igualdade b=dq_1+r_1 escreve-se como b=aq_1+r_1, com 0\le r_1<|a|.

Se a<0, então d=-a e b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. Definindo q=-q_1 e r=r_1, obtém-se

b=qa+r,\qquad 0\le r<|a|.

Com isso, fica provada a existência de q e r para quaisquer a,b\in\mathbb{Z} com a\neq 0.

Unicidade

Suponha-se que existam q,q',r,r'\in\mathbb{Z} tais que

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

Subtraindo ambas as expressões, obtém-se

a(q-q')=r'-r.

Como 0\le r,r'<|a|, verifica-se |r'-r|<|a|. Por outro lado, o membro esquerdo é múltiplo de a e, portanto, também é múltiplo de |a|. O único múltiplo inteiro de |a| com valor absoluto estritamente menor que |a| é 0; de fato, se |a| m \neq 0 com m\in\mathbb{Z}, então \big| |a| m \big| \ge |a| . Consequentemente, r'-r=0, isto é, r=r', e ao substituir em b=qa+r deduz-se q=q'. Assim, a decomposição é única.

Interpretação do quociente e do resto

• O que significa «resto». Se b=qa+r, então r=b-qa é o que «sobra» ao retirar de b o múltiplo qa. Em outras palavras, r é o resíduo de ajustar b à grelha de múltiplos de a.
• Por que se exige 0\le r<|a|. Sem essa condição, o par (q,r) não seria único. De fato, se b=qa+r, então também b=a(q+1)+(r-a). A condição 0\le r<|a| força o resto a pertencer a uma janela fixa \{0,1,2,\dots,|a|-1\}, e isso bloqueia as infinitas «re-rotulações» do mesmo número.
• O que acontece se a é negativo. O teorema continua válido sem alterações: o resto mantém-se não negativo e limitado por |a|. Isso é relevante porque algumas linguagens de programação utilizam truncamento em direção a zero e podem produzir restos negativos, enquanto em matemática adota-se a convenção 0\le r<|a| para que o resto seja um representante «padrão».

  Além disso, quando a>0, o quociente coincide com o piso:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Algoritmo longo da divisão

A partir da divisão euclidiana é possível implementar o algoritmo longo da divisão, aproveitando a representação posicional dos números. Este algoritmo é uma técnica de cálculo que permite encontrar rapidamente os valores q e r quando se deseja calcular b\div a com a,b\in\mathbb{Z} e a\neq 0.

Para descrevê-lo, revisemos primeiro alguns exemplos que ilustram o processo e as possíveis situações durante a execução do algoritmo.

1. Suponhamos que queremos calcular 57\div 4. Aqui, 57 é o dividendo e 4 é o divisor. Para isso, realizaremos a seguinte sequência de cálculos:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Escrever a operação de divisão.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Separar o primeiro prefixo (a partir da esquerda) do dividendo que}\\ &\text{seja maior ou igual ao divisor, neste caso 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{Pensar no maior número que, multiplicado por $4$,}\\ &\text{seja menor ou igual a $5$ e escrevê-lo à direita da igualdade. É 1.}\\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Multiplicar o resultado pelo divisor e subtraí-lo do valor selecionado.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Selecionar e «baixar» o próximo dígito.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Repetir a sequência com o último número obtido.} \end{array}

   O algoritmo termina quando se esgotam os dígitos a «baixar», fornecendo como resultado o quociente q=14 e o resto r=1. Em particular, o resto será sempre menor que o divisor.

2. Suponhamos que queremos calcular 132\div 5. Para isso, realizaremos a seguinte sequência de cálculos:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Separar o primeiro prefixo do dividendo e procurar algum natural que,}\\ & \text{multiplicado por 5, seja menor ou igual a ele. Se não for possível,}\\ & \text{incorporar o próximo dígito até que seja possível.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Quando o passo anterior funcionar, executar o algoritmo normalmente.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. Se o dividendo tiver mais dígitos, o procedimento é executado do mesmo modo. Por exemplo, ao calcular 3521\div 12 obtém-se:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. Se um dos números for negativo, existem duas formas aceitáveis de apresentar o resultado. No entanto, a forma padrão em teoria dos números é aquela em que o resto é positivo e, portanto, consistente com a divisão de Euclides. Por exemplo, se calcularmos -598\div 21, têm-se os seguintes desenvolvimentos possíveis, ambos corretos como identidades:

   • Com resto negativo: Este é obtido eliminando o sinal no início da operação e restaurando-o ao final.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     A partir disso, tem-se que:

     598 = 21 \times 28 + 10

     Em seguida, se multiplicarmos toda a igualdade por -1, obtém-se:

     -598 = 21 \times (-28) - 10

     De modo que, nessa representação, o resultado de -598\div 21 é quociente q=-28 e resto r=-10.

     E se multiplicarmos novamente toda a igualdade por -1, obtém-se:

     598 = (-21)\times(-28) + 10

     De modo que o resultado de 598\div (-21) é quociente q=-28 e resto r=10.

   • Com resto positivo e consistente com a divisão de Euclides: A partir do desenvolvimento anterior, tem-se que:

     -598 = 21 \times (-28) - 10

     Em seguida, somando 0=21-21 ao lado direito dessa igualdade, obtém-se:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Portanto, sendo consistentes com a divisão de Euclides, o resultado de calcular -598\div 21 fornece um quociente q=-29 e o resto r=11.

   No que diz respeito ao que é convencional na divisão de Euclides, apenas o resultado com resto positivo corresponde ao quociente e ao resto euclidianos. No entanto, ambas as expressões são identidades corretas e podem ser úteis em contextos distintos. Embora o algoritmo da divisão longa possa produzir restos negativos, isso é prático para obter resultados de maneira mecânica e realizar manipulações algébricas sem etapas adicionais. Por outro lado, os resultados com resto positivo, consistentes com a divisão de Euclides, permitem fixar um representante canônico de cada classe residual (por exemplo, em \{0,1,\dots,n-1\}), o que facilita a rotulagem dos inteiros de forma precisa e livre de ambiguidade. Cabe salientar que também existem outras convenções de representantes, como os resíduos simétricos, igualmente válidas uma vez fixada a regra.

Conclusão

O algoritmo da divisão garante que toda divisão inteira pode ser expressa de forma única como b=qa+r com 0\le r<|a|, o que estabelece um critério padrão para interpretar o quociente e o resto mesmo quando intervêm números negativos. O algoritmo longo da divisão não é mais do que uma implementação prática dessa decomposição, apoiada na representação posicional, e permite calcular q e r de maneira mecânica. Por fim, essa forma euclidiana não apenas evita ambiguidades, como também se conecta naturalmente com a aritmética modular: o resto r atua como um representante canônico da classe residual de b módulo a, base de muitas técnicas em teoria dos números e em aplicações computacionais que poderão ser revisadas em entregas futuras.

Exercícios propostos e resolvidos

Divisão euclidiana

1. (resolvido) Encontre q e r tais que

   137 = 9q + r,\qquad 0\le r\lt 9.

   Solução: Procure o maior número que, multiplicado por 9, não ultrapasse 137. Temos que 15\times 9 = 135 e 16\times 9 = 144; portanto, o quociente procurado é q=15. Agora calcule o resto r=137-9q e verifique que 0\le r\lt 9. Fazendo a verificação, obtém-se:

   r=137-9\cdot 15=137-135=2.

   Portanto, 137=9\cdot 15+2 com 0\le 2\lt 9.

2. (resolvido) Encontre q e r tais que

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Solução: Procure o maior número que, multiplicado por 37, não ultrapasse 2025. Observe que 37\times 54 = 1998 e 37\times 55 = 2035; portanto, o quociente procurado é q=54. Agora calcule o resto r=2025-37q e verifique que 0\le r\lt 37. Fazendo a verificação, obtém-se:

   r=2025-37\cdot 54=2025-1998=27.

   Portanto, 2025=37\cdot 54+27 com 0\le 27\lt 37.

3. Encontre q e r tais que

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Encontre q e r tais que

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Encontre q e r tais que

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Resto fixado e busca de inteiros. Seja a=12.

   (a) Descreva o conjunto de todos os inteiros b cuja divisão euclidiana por 12 tem resto r=5.

   (b) Encontre o menor inteiro b\gt 1000 que satisfaça o item anterior e determine o quociente q correspondente.

Algoritmo longo da divisão

Em cada caso, aplique o algoritmo longo da divisão para calcular o quociente q e o resto r. Transforme o resultado em divisão euclidiana quando o algoritmo fornecer resto negativo.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.