Prove that $a^{2^n} \equiv 1 \pmod{2^{n+2}},$ where $a$ is an odd integer.

Question

Establish that if $a$ is an odd integer, then for any $n\ge1$ $$a^{2^n}\equiv1\pmod{2^{n+2}}.$$ [Hint: Proceed by induction on $n.$]

This is a problem from Elementary Number Theory by David M. Burton.

For $\underline{n=1},$ this statement is essentially saying that $$a^2\equiv1\pmod{2^3=8},$$ which is true because $a$ is odd. Suppose that this statement is true for $\underline{n=k}$. Then,$$a^{2^k}\equiv 1\pmod{2^{k+2}}.$$ Squaring this congruence, I arrived at $$a^{2^{k+1}}\equiv1\pmod{2^{k+2}},$$ but how do I change the modulus, i.e., $\pmod{2^{k+2}}\to\pmod{2^{k+3}}?$

Answer 1

If $a^{2^k}\equiv1\pmod{2^{k+2}}$

$a^{2^k} =1+c2^{k+2}$ for some integer $c$

$a^{2^{k+1}}=(a^{2^k})^2=(1+c2^{k+2})^2=\cdots\equiv1\pmod{2^{k+3}}$

Answer 2

As suggested in a comment by WhatsUp,

if $2^{k+2}|a^{2^k}-1$, then, since $2|a^{2^k}+1$, it follows that $2^{k+3}|(a^{2^k}-1)(a^{2^k}+1)=a^{2^{k+1}}-1$.