Prove que, para cada inteiro positivo
divide
.
Passo 1
O enunciado pede que mostremos que, para todo inteiro positivo
, a potência
divide o número
.
Informações importantes dadas pelo enunciado:
é um inteiro e
.
A queremos provar a divisibilidade
Informações importantes dadas pelo enunciado:
A queremos provar a divisibilidade
ou equivalentemente a congruência
Passo 2
Estratégia escolhida: vamos provar a afirmação por indução em
.
Breve lembrança do que é indução: para provar uma afirmação para todo
fazemos dois passos: (i) mostramos
(base), e (ii) assumimos
e mostramos
(passo indutivo). Se esses dois passos funcionam, então
vale para todo
. Aqui
é a afirmação
.
Breve lembrança do que é indução: para provar uma afirmação
Passo 3
Base da indução (
).
Calculemos .
Como , temos de fato
Calculemos
Como
Então a base
é verdadeira.
Passo 4
Hipótese de indução.
Suponha que para algum vale
Suponha que para algum
ou seja, exista um inteiro
tal que
É conveniente escrever essa hipótese na forma de congruência:
Passo 5
Objetivo do passo indutivo.
Partindo da hipótese , queremos provar
Partindo da hipótese
ou seja
Passo 6
Manipulação algébrica usando desenvolvimento binomial.
Da hipótese, escrevemos
Da hipótese, escrevemos
então existe um inteiro
tal que
Queremos estudar
. Vamos expandir
usando a fórmula do cubo:
Logo
Passo 7
Verificação de divisibilidade por
.
Lembre que . Então
, ou seja
já contém o fator
. Precisamos apenas verificar que o outro fator
é inteiro.
Observe:
Lembre que
Observe:
que é claramente um inteiro porque
. Portanto
é soma de inteiros, logo é inteiro. Portanto
é múltiplo de
:
Em notação de congruência:
Passo 8
Conclusão da indução.
Mostramos a base e que
. Portanto, por indução, a afirmação vale para todo inteiro
: para cada
temos
. (Uma checagem rápida com
dá
, o que confirma o enunciado para
.)
Mostramos a base