Squaring any odd number $k-2$ times produces $1$ modulo $2^k$

Question

If $k>2$, show that if $a$ is odd, then $$a^{2^{k-2}}\equiv 1\pmod{2^k}$$

Being very honest, do not even know where to start!!

Answer 1

Perhaps you can use induction on this question (but I feel that using modulo congruence should be faster but I currently have no idea)

The base case for $k=3$ is true.

Suppose for some $k=n$, the statement is true.

$$\therefore 2^n | a^{2^{n-2}}-1$$ Now, $$a^{2^{n-1}}-1=(a^{2^{n-2}}-1)(a^{2^{n-2}}+1)$$ The terms in the first parenthesis is divisible by $2^n$, whereas the second terms in the second parenthesis is an even number ($\because a$ is odd), hence divisible by $2$. By induction, the statement holds. :) $$\therefore 2^{n+1} | a^{2^{n-1}}-1$$

Answer 2

Consider the multiplicative group of odd integers modulo $2^k$. It has order $2^{k-1}$.

The property you're trying to prove is that every element of the group has an order that divides $2^{k-2}$ -- in other words there is no element of order $2^{k-1}$, which is the same as saying that the group is not cyclic.

The squares of $1$, $2^k-1$ and $2^{k-1}+1$ are all congruent to 1 modulo $2^k$. Does this prevent the multiplicative group from being cyclic?