Show that the number of solutions of $x^2 \equiv 1 \pmod n$ is 2

Question

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$

then

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

and then im stuck ..

any help will be appriciated

Answer 1

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

Answer 2

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.