let $3 \le n \in N$ for which there exists a primitive root modulo n. Show that the number of solutions of $x^2 \equiv 1 \pmod n$ is 2

what it tried - i tried showing x and 1 as the primitive root (a) and got to

$a^{x^2} \equiv a^0 \pmod n$


$x^2 \equiv 0 \pmod {\phi (n)}$

and then im stuck ..

any help will be appriciated

  • $\begingroup$ What you said you "got to" makes no sense at all. If there is a primitive root modulo $n$, why do you think $x$ would be a primitive root? $\endgroup$ – user21820 Jun 20 '15 at 14:12

If there is a primitive root $a$, then $\Bbb Z_n^\times$ is cyclic. That is, $$a,a^2,\ldots,a^{\phi(n)}$$ is an exhaustive list of the elements of the group.

Let's say that $a^k$, $1\le k\le\phi(n)$ is a solution, that is, $a^{2k}=1$, or $\phi(n)\mid 2k$. Since $k\le\phi(n)$, then $k$ must be $\phi(n)$ or $\phi(n)/2$. Note that $\phi(n)$ is even for $n\ge 3$.

Remark: you wrote $a^{x^2}$ where it probably should be $a^{2x}$.


Let $g$ be a primitive root modulo $n$.

The map $x \mapsto x^2$ is a group homomorphism $U(n) \to U(n)$.

The image is exactly the set of all even powers of $g$, because $\phi(n)$ is even since $n\ge 3$.

Hence the image has $\phi(n)/2$ elements.

This implies that the kernel has order $2$.

More generally, in cyclic groups of even order, the kernel of the square map has order $2$. In cyclic groups of odd order, the square map is injective.


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.