Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$.

share|cite|improve this question
+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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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
Yes agree with that, but what are the consequences of that l depends on a? I mean why I could not choose l as a = 2l+1, as a is odd? – alvoutila Sep 20 '11 at 11:34
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.