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?

To make things more interesting, and slightly less susceptible to exhaustive search, we can show that $x^2\equiv  1\bmod 91$ has four incongruent solutions and find them.
The analogy is that both $15=3\cdot 5$ and $91=7\cdot 13$ are composite numbers, the product of two odd primes.
So in my example, $x^2\equiv  1\bmod 91$ $\implies$ $x^2\equiv  1\bmod 7$ and $x^2\equiv  1\bmod 13$. Thus
$x\equiv \pm1\equiv \{1,6\}\bmod 7 \\
x\equiv \pm1\equiv \{1,12\}\bmod 13 $
The Chinese Remainder theorem says that each combination of values from these two equations will have distinct results $\bmod 91$, so that proves the existence of those four roots. Then we can also find them:
$
(1 \bmod 7, 1 \bmod{13}) \to 1\bmod {91}\\
(1 \bmod 7, 12 \bmod{13}) \to 64\bmod {91}\\
(6 \bmod 7, 1 \bmod{13}) \to 27\bmod {91}\\
(6 \bmod 7, 12 \bmod{13})  \to 90\bmod {91}
$
giving $x^2\equiv 1 \implies x \equiv \{1,27,64,90\} \bmod 91$.
