Mostre que:
\quad 21^{n} \equiv 6(\bmod 15) para todo inteiro
.
\quad 21^{n} \equiv 6(\bmod 15) para todo inteiro
Passo 1
O enunciado pede para mostrar que, para todo inteiro
, a congruência
é verdadeira.
Informações dadas: a expressão e o módulo
. A tarefa é provar que o resto da divisão de
por
é sempre
, para qualquer
.
Informações dadas: a expressão
Passo 2
Primeiro fato útil (fácil de verificar): podemos reduzir a base módulo
. Calcule:
logo
. Isto significa que ao trabalhar com potências de
módulo
podemos, sem perder informação, substituir
por
.
Passo 3
Propriedade de congruências que vamos usar: se
então, para todo inteiro
,
Explicando por que isso vale: multiplique a congruência
por ela mesma
vezes (ou faça indução). Como a congruência é preservada por multiplicação, o resultado é
.
Passo 4
Aplicando a propriedade ao caso concreto: de
segue
Passo 5
Agora mostramos que
para todo
. Observe que
e
logo
, isto é,
A partir daqui fazemos uma breve indução: para
a afirmação é verdadeira (
). Suponha
para algum
; então
Portanto, por indução,
para todo
. (Uma observação alternativa e rápida: como
, multiplicando ambos os lados por
obtemos
para todo
, e o caso
é trivial.)
Passo 6
Concluímos unindo os passos:
(Passo 4) e
(Passo 5). Assim,