# proving no primitive roots exist modulo $2^n$ for n $\geq$ 3

Ive been asked to prove by induction that no primitive roots exist modulo $$2^n$$ for n $$\geq$$ 3.

I have proven true for base case $$n=3$$, and assumed to be true for $$n$$. I'm now stuck at this point:

$${x^{2}}^{n-1} \equiv 1 \pmod{2^{n+1}}.$$

thank you :)

• If there were a primitive root mod $2^{n + 1}$ then that same root would be a primitive root mod $2^n$. Oct 31, 2021 at 21:51
• hey man, thanks for the help- im still struggling to see how i can use that to prove the induction as im trying to prove it for $2^{n+1}$ not $2^{n}$? Sorry as you can tell this isnt a strong area of mine, thanks again for the help Oct 31, 2021 at 22:54
• Forward-backward induction of Cauchy? Assume $n$ and prove $n-1$ Oct 31, 2021 at 23:09
• If it exists for $n+1$, it exists for $n$. By the contrapositive and since we know it doesn’t exist for $n$, it doesn’t exist for $n+1$.
– Eric
Oct 31, 2021 at 23:18
• Use induction on $n\ge 3$. Let $n'=n+1$. Show that if $x^{2^n-2}\equiv 1\pmod {2^n}$ whenever $x$ is odd, then $x^{2^{n'}-2}$ $\equiv 1$ $\pmod {2^{n'}}.$ Nov 1, 2021 at 8:39