Obtenha a seguinte versão do Algoritmo da Divisão: Para inteiros a e b, com b
, existem inteiros únicos
e
que satisfazem
, onde
. [Dica: Primeiro escreva
, onde
. Quando $0 \leqslant r^{\prime} \leqslant \frac{1}{2}|\mathbf{b}|, deixe
e
; quando $\frac{1}{2}|b|<r^{\prime}<|b|, deixe
se
ou
se
.]
Passo 1
Primeiro, vamos entender o que a questão está pedindo. Temos dois números inteiros,
e
, onde
. Queremos encontrar dois números inteiros únicos,
e
, que satisfazem a equação
, com a condição de que o resto
esteja no intervalo
.
Para resolver isso, vamos precisar entender o Algoritmo da Divisão e como ajustar o resto
para que ele fique dentro do intervalo desejado.
Passo 2
Começamos aplicando o Algoritmo da Divisão padrão, que nos diz que para quaisquer inteiros
e
(com
), existem inteiros únicos
e
tais que:
onde
.
Aqui,
é o quociente e
é o resto quando dividimos
por
.
Passo 3
Nosso objetivo é ajustar esse resto
para que ele fique no intervalo
. Para isso, analisamos dois casos baseados no valor de
:
-
Caso 1: Se
, mantemos o resto como está: -
Caso 2: Se
, ajustamos o resto subtraindo e ajustamos o quociente de acordo com o sinal de :
Passo 4
Vamos detalhar por que fazemos esses ajustes. Quando
está acima de
, queremos “puxar” o resto para baixo para que ele caia dentro do intervalo desejado. Subtraindo
, garantimos que
seja menor ou igual a
. Porém, ao fazer isso, precisamos ajustar o quociente
para manter a igualdade
. Se
for positivo, aumentamos
em 1; se for negativo, diminuímos
em 1.
Passo 5
Vamos resumir o processo:
- Dividimos
por para obter e usando o Algoritmo da Divisão padrão. - Verificamos onde
está: - Se
está no primeiro caso, mantemos e . - Se
está no segundo caso, ajustamos e conforme explicado.
- Se
Resposta
Seguindo os passos acima, para quaisquer inteiros
e
com
, existem inteiros únicos
e
que satisfazem
, onde
.