Sejam
inteiros positivos tais que
divide
. Mostre que
divide
para todo
.
Passo 1
Resumindo: temos inteiros positivos
tais que
e queremos mostrar que
para todo
. Vamos usar indução em
e manipular congruências módulo
.
Passo 2
(Base da indução) Para
temos
que é divisível por
exatamente pela hipótese do problema. Logo a propriedade vale para
.
Passo 3
(Passo indutivo) Suponha que para algum
já tenhamos
isto é,
Queremos mostrar que então
Passo 4
Multiplicando a congruência indutiva por
, obtemos
Logo
Passo 5
Como
, temos
Então
Substituindo,
Logo esse resíduo é múltiplo de
, ou seja
Isto completa a etapa indutiva.
Resposta
Portanto, por indução,
divide
para todo
.