Let $a$ be an odd integer. Using induction, prove: For any $n\in\mathbb{Z}^+$, $a^{2^n}\equiv 1\mod{2^{n+2}}$

Question

I'm having trouble on where to start, I'm not sure if i should express $a$ as $2n-1$ or $2n+1$, and where to go on from that

Answer 1

Hint: For the base case, use the fact that $a^2\equiv 1\bmod 8$ for all odd $a$ (you can prove this using either of the substitutions you suggested).

For the inductive step, note that

$$\frac{a^{2^{n+1}}-1}{a^{2^n}-1}=a^{2^n}+1$$

is even...