3
$\begingroup$

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$?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$)

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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