For which $n$ is $(\mathbb{Z}/2^n\mathbb{Z})^\times$ cyclic?

Question

Denote by $(\mathbb{Z}/2^n\mathbb{Z})^\times$ the multiplicative group of odd congruence classes modulo $2^n$. I need to find for which $n$ this multiplicative group is cyclic. This is homework, so I would appreciate a general direction or a simple outline instead of a full answer. Here's my work so far:

By computing $(\mathbb{Z}/2^n\mathbb{Z})^\times$ for $n$ up to 4, I claimed that the group is not cyclic for $n \geq 3$, which I confirmed later on Wikipedia. I also received a (not proven) formula from the exercise: if $a$ is odd, then $a^{2^{n-2}} \equiv 1 \pmod{2^n}$ for $n \geq 3$. I understood that this formula is a upper bound on the order of the elements of $(\mathbb{Z}/2^n\mathbb{Z})^\times$: it must divide $2^{n-2}$, so it cannot be $\varphi(2^n) = 2^{n-1}$. This basically proves the exercise, but I don't feel like I should use this statement without a proof - it would make this exercise too direct comparing with any other from our exercise list.

So then I went out to prove the formula. I started with Euler's Theorem: $$a^{2^{n-1}} \equiv 1 \pmod{2^n}$$ Then I took the square root: $$a^{2^{n-2}} \equiv 1 \pmod{2^n}\\ \text{or } a^{2^{n-2}} \equiv -1 \pmod{2^n}$$ So I tried to prove the second equation false, but I couldn't get far by doing simple arithmetic and factorization, like $a^{2^{n-2}} \equiv 1 + 2 + 4 + ... + 2^{n-1} \pmod{2^n}$. Induction over $n$ doesn't seem to be the case. What am I missing?

EDIT: I just fiddled around more and now I believe induction is the way. The induction hypotesis would be $a^{2^{n-3}} \equiv 1 \pmod{2^{n-1}}$, which means $a^{2^{n-3}} = 2^{n-1}k + 1$ for some integer $k$. By squaring, I have $a^{2^{n-2}} = 2^{2n - 2}k^2 + 2^nk + 1 \equiv 1 \pmod{2^n}$.

Answer 1

You can prove that for any $a\in (\mathbb Z/2^n\mathbb Z)^\times$, $a^{2^{n-2}}\equiv 1 \pmod {2^n}$ by induction.

The inductive step works as follows. Suppose that for any $a\in (\mathbb Z/2^n\mathbb Z)^\times$, $a^{2^{n-2}}\equiv 1 \pmod {2^n}$, and let $b\in (\mathbb Z/2^{n+1}\mathbb Z)^\times$. Then by induction $$b^{2^{n-2}}\equiv1\pmod {2^n}$$ and hence $$b^{2^{n-2}}\equiv 1 +c2^n\pmod {2^{n+1}}$$for some $c$. Now observe that $b^{2^{n-1}} = (b^{2^{n-2}})^2$. Can you finish from here?

Answer 2

$\textbf{Hint}$: You can try to prove that for $n \geq 3$, $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{n-2}\mathbb{Z} \cong (\mathbb{Z}/2^{n}\mathbb{Z})^{\times}$, where the isomorphism is given by mapping $(\overline{i}, \overline{j})$ to $\overline{(-1)}^{i} \overline{5}^j$. You have to check that this is a well-defined homomorphism. For proving the bijetivity note that it will be enough to prove injectivity for reasons of equal (finite) cardinality.