Prove, usando indução finita, que se a é um número ímpar e n >= 1 então a^2^n equiv 1(bmod 2^n+2).

Passo 1

Então, o que a gente precisa provar é: “Se a é um número ímpar e n>=1, então
a^2^nequiv1pmod2^,n+2,
Isso é um problema de aritmética modular que a gente vai resolver por indução finita. Para isso, precisamos
- Entender o princípio da indução: mostrar o caso base ( n=1) e depois que, se vale para um n, vale para n+1.
- Saber manipular potências e congruências modulares.
- Usar a expansão binomial para o passo indutivo.
A partir do próximo passo, começamos a prova de verdade.

Passo 2

Precisamos mostrar que, para n=1, vale
a^2^1 = a^2 equiv 1 pmod2^1+2 = pmod8
Como a é ímpar, escrevemos a=2k+1 para algum inteiro k. Então
a^2 = (2k+1)^2 = 4k^2 + 4k +1 = 4k(k+1) +1
Repare que k(k+1) é o produto de dois números consecutivos, logo um deles é par, então k(k+1) é múltiplo de 2. Portanto 4k(k+1) é múltiplo de 8 e podemos escrever
a^2 = 8M +1
para algum inteiro M. Isso significa exatamente
a^2 equiv1pmod8
Logo o caso base está ok.

Passo 3

Suponha que, para um certo n>=1, valha a hipótese de indução:
a^2^nequiv1pmod2^n+2
Isso quer dizer que existe um inteiro m tal que
a^2^n = 1 + m,2^,n+2(*)
Queremos mostrar que então
a^2^n+1equiv1pmod2^,n+3
Começamos elevando (*) ao quadrado, porque 2^n+1=2cdot2^n:
a^2^n+1 = l(a^2^nr)^2 = l(1 + m,2^n+2r)^2
Agora usamos a expansão binomial:
(1 + X)^2 = 1 + 2X + X^2,com X = m,2^n+2
Então
a^2^n+1 = 1 + 2l(m,2^n+2r) + l(m,2^n+2r)^2
;= 1 + m,2^n+3 + m^2,2^2n+4
Repare que tanto o segundo termo m,2^n+3 quanto o terceiro m^2,2^2n+4 são múltiplos de 2^,n+3. Logo podemos escrever
a^2^n+1 = 1 + M',2^,n+3
para algum inteiro M', o que mostra
a^2^n+1equiv1pmod2^,n+3
E isso é exatamente o que queríamos no passo indutivo.

Resposta

Por indução finita, mostramos que para todo inteiro n>=1 e todo a ímpar vale
a^2^nequiv1pmod2^,n+2,

Exercícios relacionados