Obtenha a seguinte versão do Algoritmo da Divisão: Para inteiros a e b, com b neq 0, existem inteiros únicos q e r que satisfazem a=q b+r, onde -12|b|. [Dica: Primeiro escreva a=q^prime b+r^prime, onde 0 <= r^prime<|b|. Quando $0 \leqslant r^{\prime} \leqslant \frac{1}{2}|\mathbf{b}|, deixe 0 <= r^prime <= 12|b|, deixe e e ; quando $\frac{1}{2}|b|<r^{\prime}<|b|, deixe ; quando r=r^prime-|b| e se q=q^prime+1 ou b>0 se q=q^prime-1.]

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 a = q' cdot b + r' 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 r = r' para que ele fique no intervalo q = q' . Para isso, analisamos dois casos baseados no valor de r = r' - |b| :
  1. Caso 1: Se q = q' + 1 & se b > 0 q' - 1 & se b < 0 , mantemos o resto como está:
  2. 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:
  1. Dividimos por para obter e usando o Algoritmo da Divisão padrão.
  2. Verificamos onde está:
    • Se está no primeiro caso, mantemos e .
    • Se está no segundo caso, ajustamos e conforme explicado.

Resposta

Seguindo os passos acima, para quaisquer inteiros e com , existem inteiros únicos e que satisfazem , onde .

Exercícios relacionados