<s>[INST] Show that $x^{2} \equiv 1 \pmod{15}$ has four incongruent solutions mod 15. Show that $x^{2} \equiv 1 \pmod{15}$ has four incongruent solutions mod 15.
My instinct was to find the primitive root and then use a theorem to directly show the number of incongruent solutions, which follows from knowing the primitive root. But, apparently there are no primitive solutions to $mod 15.$ So what's another option?
 [/INST] By the Chinese remainder theorem, $a\equiv b\pmod{15}$ if and only if
\begin{cases}
a \equiv b\pmod{3}\\[4px]
a \equiv b\pmod{5}
\end{cases}
In the case $a=x^2$ and $b=1$, the first equation gives
$$
x=1+3k \qquad\text{or}\qquad x=2+3k
$$
From $x=1+3k$, we get
$$
1+6k+9k^2\equiv 1\pmod{5}
$$
that is, $k-k^2\equiv0\pmod{5}$, hence $k\equiv0\pmod{5}$ or $k\equiv1\pmod{5}$. Thus we get $x=1$ or $x=4$.
From $x=2+3k$ we similarly get
$$
4+12k+9k^2\equiv1\pmod{5}
$$
that is, $k^2-2k-3\equiv0\pmod{5}$ that yields $k=3$ or $k=4$, so
$x=14$ or $x=11$.
On the other hand, a higher level solution using the fact that the group of (multiplicative) units in $\mathbb{Z}/15\mathbb{Z}$ is the product of the groups of units in $\mathbb{Z}/3\mathbb{Z}$ and $\mathbb{Z}/5\mathbb{Z}$ is preferable.
</s>