# How to prove by induction that $a^{2^{k-2}} \equiv 1\pmod {2^k}$ for odd $a$?

Let $a \in$ Z be odd. How to prove by induction that $a^{2^{k-2}} \equiv 1\pmod {2^k}$ for all $k \geq 3$.

My attempt: let $k=3$ \begin{align*} a^{2^{k-2}}-1&= a^{2^{3-2}}-1=a^{2}-1\\ & \stackrel{\text{a is odd}}{=} (2l+1)^2-1=4l^2+4l=4l(l+1)\\ &\stackrel{\text{choose } l=2}{=} 8 \cdot 3 = 8q \end{align*} or $2^3|a^2-1 \Longleftrightarrow a^2 \equiv 1\pmod {2^3}$.

Induction assumption: Let us assume that claim holds when $k=n$ or $2^n|a^{2^{n-2}}-1$ or $a^{2^{n+2}} =q'2^n+1$. Look at the statement $a^{2^{k-2}}-1$ with the value $k=n+1$. Then \begin{align*} a^{2^{n+1-2}}-1 &= a^{2^{n-2}\cdot 2}-1=(a^{2^{n-2}})^2-1\\ &\stackrel{\text{assumption}}{=} (q')^2(2^n)^2+2q'\cdot 2^n +1 -1\\ &= 2^n((q')^22^n+2q')=2^nq''\\ &\Longrightarrow 2^n|a^{2^{n+1-2}}-1. \end{align*} Claim holds, i.e. $a^{2^{k-2}} \equiv 1\pmod {2^k}$.

-
+1 For showing your work. I corrected the TeX a bit to get the $2^k$ inside the parentheses. – Jyrki Lahtonen Sep 20 '11 at 11:27
BTW, this result can be used to prove that the unit group in $\mathbb Z/(2^k)$ is not cyclic for $k\ge3$. – lhf Sep 20 '11 at 13:27

For the case $k=3$, you cannot choose $l$. You must argue that $4l(l+1)$ is a multiple of $8$, which can be done by arguing that $l(l+1)$ must be even.
Your induction step seems ok, but it could be written more simply as $$a^{2^{n+1-2}}-1 = a^{2^{n-2}\cdot 2}-1=(a^{2^{n-2}}-1)(a^{2^{n-2}}+1)$$ and use that $a^{2^{n-2}}+1$ is even.
Why not choose l? Do you mean that not choose $l=2$? – alvoutila Sep 20 '11 at 11:26
@alvoutila, isn't $a=2l+1$? If so, $l$ depends on $a$. – lhf Sep 20 '11 at 11:30
@alvoutila, you're given $a$ and so are given $l$. What happens when $a=7$? – lhf Sep 20 '11 at 11:36
@alvoutila, yes and so you cannot choose $l=2$ in this case. Am I missing something here? – lhf Sep 20 '11 at 11:40