Induction: prove $\,a^{2^n} \equiv 1\pmod{2^{n+2}}\,$ via congruences Prove that:
$$a^{2^n} \equiv 1\pmod{2^{n+2}}$$
I have done the base case, and then have an assumption that:
$$a^{2^k} \equiv 1 \pmod {2^{k+2}}$$
I wish to prove the last step, that:
$$a^{2^{k+1}} \equiv 1 \pmod{2^{k+3}}$$
How would I do this?
 A: First of all, you should specify that $a$ is odd, and $n > 0$. 
And then, use the definition of the congruence relation
$$
a^{2^k} \equiv 1 \pmod{2^{k+2}} 
$$
to write
$$
a^{2^{k}} = 1 + c 2^{k+2},
$$
for some $c$, then take the square. 
A: I'm assuming the you forgot to specify that $a$ is odd. From the induction hypothesis you know that $a^{2^{k}}=t 2^{k+2} + 1$ for some integer $t$. From this we get
$$a^{2^{k+1}}=(a^{2^{k}})^{2}=(t 2^{k+2} + 1)^2=t^2 2^{2k+4} + t2^{k+3} + 1$$
But $2^{2k+4} \equiv 0 \mod(2^{k+3})$ and so $$t^2 2^{2k+4} + t2^{k+3} + 1 \equiv 1 \mod(2^{k+3})$$
A: Lemma $\rm\ k>0,\,\ 2^k\!\mid b-1\:\Rightarrow\: 2^{k+1}\!\mid b^2-1$
$\begin{eqnarray}\rm{\bf Proof}\quad k>0,\,\ \color{#0A0}{2^k}\!&\mid&\rm\color{#0A0}{b-1}\:\Rightarrow\: \color{#C00}2\cdot \color{#0A0}{2^{k}}\!\mid \color{#0A0}{(b-1)}(\color{#C00}{b+1})\,=\,b^2\!-1\\  \\
\rm since\ \ \ \ 2&\mid&\rm b-1\:\Rightarrow\:\color{#C00}2\mid\color{#C00}{b+1} =(b-1) + 2\end{eqnarray}$
Remark $\ $ Yours is the special case $\rm\, b = a^{2^n},\,\ k = n+2.$
