Sejam
inteiros positivos tais que
divide
. Mostre que
divide
para todo
.
9) Para todo inteiro positivo
vale que
é divisível por 19 .
9) Para todo inteiro positivo
Passo 1
Temos duas afirmações a provar:
- Sejam
inteiros positivos tais que divide . Provar que, para todo inteiro , também vale
- Para todo inteiro positivo
, mostrar que
é divisível por
.
Passo 2
Prova da primeira afirmação. Note que a condição
equivale a
Queremos então mostrar por indução em
que
Base
: de fato
é múltiplo de
por hipótese.
Passo 3
Passo indutivo. Suponha que para um
já saibamos
Então, usando
, temos
Ao subtrair
, restam só os termos onde
, e cada um desses contém o fator
com
e
. Logo cada termo restante é múltiplo de
. Assim
concluindo a indução.
Passo 4
Portanto, para todo
vale
Passo 5
Prova da segunda afirmação. Queremos mostrar que
é múltiplo de
. Pela pequena teorema de Fermat, para qualquer
não divisível por
vale
Logo
depende apenas de
. Como
é par para todo
, o expoente
mod
pertence ao ciclo
que tem período
. Portanto a sequência
é periódica de período divisor de
. Assim
também é periódica de período
. Basta verificar os primeiros
valores de
.
Passo 6
Cálculo direto módulo
:
Para
,
:
Para
,
:
Para
,
:
Os casos
repetem-se por periodicidade de
, e dão de novo soma congruente a
.
Resposta
- Para quaisquer inteiros positivos
com , vale
- Para todo inteiro
,
é divisível por
.