Mostre o chamado Algoritmo da Divisão Euclidiana nos inteiros:
Problema 3.19.
Dados inteiros
e
, com
, existe um único par de inteiros
e
tal que
Sugestão: Considere os intervalos da forma
, com
em
.
Problema 3.19.
Dados inteiros
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
e
com
, sempre existe um par único de inteiros
e
que satisfaz a equação:
Para resolver isso, vamos usar a ideia de intervalos do tipo
, onde
é qualquer número inteiro.
Passo 2
Primeiro, vamos entender o que significa o intervalo
. Esse intervalo representa todos os números que ficam entre
e
, incluindo
mas excluindo
. A ideia aqui é encontrar em qual desses intervalos o número
se encaixa.
Passo 3
Vamos chamar o número
que faz com que
esteja dentro desse intervalo específico de
. Ou seja, queremos encontrar um
tal que:
Isso garante que
está no intervalo
.
Passo 4
Agora, definimos o resto
como a diferença entre
e
:
Com essa definição, substituímos
na equação original:
Além disso, pela definição do intervalo, sabemos que:
Isso satisfaz a condição que precisamos para o resto.
Passo 5
Por último, precisamos mostrar que os valores de
e
são únicos. Suponha que existam dois pares
e
que satisfazem a equação
com
. Se subtrairmos as duas equações, teríamos:
Como
, a única maneira de isso acontecer é se
e
. Assim,
e
são únicos.
Resposta
Assim, mostramos que para quaisquer inteiros
e
, existe um único par de inteiros
e
tal que: