Prove que:
Se
tal que
, então
.
Se
Passo 1
O que o enunciado dá e o que pede:
- Dado:
e . - Pedido: provar que
.
Ou seja, a tarefa é mostrar que
deixa resto
na divisão por
(equivalente a mostrar que
divide
) sabendo que o maior divisor comum entre
e
é
.
Passo 2
Lembretes e definições que vou usar (explicadas de forma bem direta):
- "
" significa que é um divisor comum de e e é o maior com essa propriedade; em particular e . - "
" significa que divide , ou seja existe um inteiro tal que . - "
" significa que (ou seja e deixam o mesmo resto na divisão por ).
Vou usar também a propriedade simples: se
então
. Vou justificar essa propriedade no próximo passo.
Passo 3
Do dado
deduzo imediatamente que
(porque
é um divisor comum) e que
(porque se
então
seria um divisor comum maior ou igual a
, contradizendo
). Portanto
é par, mas não é múltiplo de
.
Para trabalhar com isso escrevo
como múltiplo de
. Ou seja existe
tal que
Passo 4
Vou usar a propriedade citada: se
então
. Aplicando ao nosso caso,
Justificativa curta: se
fosse um número
, então
dividiria
e também dividiria
, logo
seria um divisor comum de
e
maior que
, contradizendo
. Logo
.
Da igualdade
segue que
não é par, ou seja
é ímpar.
Passo 5
Como
é ímpar, existe
tal que
. Substituindo em
obtemos
Isso mostra que
, ou seja
. Pela definição de congruência modular, isso é exatamente
.
Passo 6
Conclusão direta do passo anterior: a partir de
mostramos que
é da forma
, portanto deixa resto
na divisão por
. Isso completa a prova.