No primitive root modulo $2^n$ for $n\ge 3$

Question

Prove that there is no primitive root modulo $2^n$.

I'm not sure how to begin proving this. I know $\varphi(2^n)=2^{n-1}$, thus a primitive root $a\in\left(\dfrac{\mathbb{Z}}{2^n\mathbb{Z}}\right)^*$ has order $2^{n-1}$. How do I show that no such roots exist?

Additionally, how can I prove that $\left(\dfrac{\mathbb{Z}}{2^n\mathbb{Z}}\right)^*$ is generated by $-1$ and $5$?

Answer 1

First, prove that there is no primitive root modulo $8$.

For your second claim, check by induction that the order of $5$ modulo $2^n$ is $2^{n-2}$ and that $-1$ is never in the subgroup generated by $5$ (because it isn't so modulo $8$)

Answer 2

Hint: If there is a primitive root module $2^{n+1}$ there is a primitive root modulo $2^n$.

(More generally, if there is a primitive root modulo $n$ and $d\mid n$, then there is a primitive root modulo $d$.)

Answer 3

It is enough to prove that $x^m \equiv 1 \bmod 2^n$ for $m=2^{n-2}$ and $x$ odd.

This can be proved by fixing $x$ and using induction on $n$.