Mostre o chamado Algoritmo da Divisão Euclidiana nos inteiros:
Problema 3.19.
Dados inteiros a e b, com a>0, existe um único par de inteiros q e r tal que
b=a q+r, com 0 <= r<a
Sugestão: Considere os intervalos da forma [n a,(n+1) a), com n em Z.

Passo 1

Beleza, vamos lá! A gente tem um exercício que fala sobre o Algoritmo da Divisão Euclidiana. Basicamente, ele diz que, dado dois números inteiros a e b com a > 0 , sempre existe um par único de inteiros q e r que satisfaz a equação:
b = a q + r, com 0 <= r < a
Para resolver isso, vamos usar a ideia de intervalos do tipo [n a, (n+1) a), onde n é qualquer número inteiro.

Passo 2

Primeiro, vamos entender o que significa o intervalo [n a, (n+1) a). Esse intervalo representa todos os números que ficam entre n a e (n+1) a , incluindo n a mas excluindo (n+1) a . A ideia aqui é encontrar em qual desses intervalos o número b se encaixa.

Passo 3

Vamos chamar o número n que faz com que b esteja dentro desse intervalo específico de q . Ou seja, queremos encontrar um q tal que:
q a <= b < (q + 1) a
Isso garante que b está no intervalo [q a, (q+1) a).

Passo 4

Agora, definimos o resto r como a diferença entre b e q a :
r = b - q a
Com essa definição, substituímos r na equação original:
b = a q + r
Além disso, pela definição do intervalo, sabemos que:
0 <= r < a
Isso satisfaz a condição que precisamos para o resto.

Passo 5

Por último, precisamos mostrar que os valores de q e r são únicos. Suponha que existam dois pares (q1, r1) e (q2, r2) que satisfazem a equação b = a q + r com 0 <= r < a . Se subtrairmos as duas equações, teríamos:
a (q1 - q2) + (r1 - r2) = 0
Como 0 <= r1, r2 < a , a única maneira de isso acontecer é se q1 = q2 e r1 = r2 . Assim, q e r são únicos.

Resposta

Assim, mostramos que para quaisquer inteiros a > 0 e b , existe um único par de inteiros q e r tal que:
b = a q + r, com 0 <= r < a

Exercícios relacionados