Álgebra I – Divisibilidade
19
3.3 Algoritmo da divisão
Já sabemos que quando um inteiro b não divide um inteiro a, existe um método para dividir a
por b, obtendo um quociente q e um resto r, e que esse processo de divisão termina quando r < b.
Isso pode ser enunciado da seguinte forma:
Teorema. Sejam a e b inteiros, tais que a  0 e b > 0. Então, existem q e r inteiros, únicos, tais que
a = bq + r e 0  r < b.
Prova da existência. Consideremos o seguinte conjunto: S = {a - bx / x  Z e a – bx  0}.
Observe que a  S, pois a = a – b.0 e a  0. Logo S é não vazio.
Assim, temos que S é um subconjunto de números naturais, não vazio. Então, pelo Princípio da Boa
Ordem, existe em S um elemento mínimo, o qual denotaremos por r.
r  S  r  0 e r = a – bq para algum q  Z.
Falta mostrarmos que r < b. De fato, suponha por absurdo que r  b.
r  b  a – bq  b  a – bq – b  0  a – b(q + 1)  0  a – bq – b  S  a – bq – b  r
 r – b  r  - b  0  b  0, o que é um absurdo, pois por hipótese b > 0.
Prova da unicidade. Suponha que existam inteiros q , q’, r e r’, com q  q’ e r  r’, tais que
a = bq + r , a = bq’ + r’ , 0  r < b e 0  r’ < b.
a = bq + r e a = bq’ + r’  bq + r = bq’ + r’  b(q – q’) = r’ – r
0  r < b e 0  r’ < b  | r’ – r| < b
Assim, b(q – q’) = r’ – r  |b(q – q’)| = |r’ – r|  b.|q – q’| = |r’ – r| < b  |q – q’| < 1
Como q – q’ é um número inteiro, temos que q – q’ = 0 e assim, r’ – r = 0  q = q’ e r = r’. 
Exercícios envolvendo o algoritmo da divisão
Problema 1. Considere x um número natural que, dividido por 9, deixa resto 5 e, dividido por 3, deixa
resto 2. Sabendo que a soma destes quocientes é 9, determine x.
Problema 2. (Provão 2002) O resto da divisão de um inteiro n por 20 é 8. Qual é o resto da divisão
de n por 5?
Problema 3. (Provão 2003) Se o resto da divisão do inteiro n por 5 é igual a 3, o resto da divisão de
2
n por 5 é, necessariamente, igual a:
a) 0
b) 1
c) 2
d) 3
e) 4
Problema 4. Em uma divisão o dividendo é 120 e o quociente é 8. Encontre o divisor e o resto.