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?
$\endgroup$ 96 Answers
$\begingroup$$$\begin{array}{rcl} x^2 &\equiv& 1 \pmod{15} \\ (x-1)(x+1) &\equiv& 0 \pmod{15} \end{array}$$
So, $x=1$, $x=-1$, $x=4$, or $x=-4$.
$\endgroup$ $\begingroup$$x^2\equiv 1 \pmod 3$ and $x^2\equiv 1 \pmod 5$. Now, $x\equiv 1 \text{ or } 2 \pmod 3$. There are $2$ solutions. Also $x\equiv 1 \text{ or } 4 \pmod 5$. There are $2$ solutions. By Chinese remainder theorem: $x^2\equiv 1 \pmod {15}$ has $2\cdot 2=4$ incongruent solutions.
$\endgroup$ $\begingroup$We have $U(15) \cong U(3) \times U(5) \cong C_2 \times C_4$.
So the four roots of $x^{2} \equiv 1 \bmod 15$ correspond to $(\pm 1, \pm 1)$, where the signs are chosen independently.
(I'm identifying $C_2$ and $C_4$ as subgroups of $\mathbb C^\times$, that is, roots of unity.)
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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$.
$\endgroup$ $\begingroup$Let $\phi$ denote Euler's totient function.
We have
$\quad \phi(3) = 2$
$\quad \phi(5) = 4$
$\quad \phi(15) = \phi(3) \cdot \phi(5) = 2 \cdot 4 = 8$
So the multiplicative group of integers modulo $15$, ${\displaystyle (\mathbb {Z} /15\mathbb {Z} )^{\times }}$, contains $8$ elements. Since the solutions to
$\tag 1 x^2 \equiv 1\pmod{15}$
forms a subgroup, the number of solutions has to divide $8$.
Since $2^2 \equiv 4 \pmod{15}$, the order of $[2] \in {\displaystyle (\mathbb {Z} /15\mathbb {Z} )^{\times }}$ is greater than $2$. It follows that the number of solutions for $\text{(1)}$ must divide $4$.
Calculating further we determine that the order of $2$ is equal to $4$.
Observing that $-1 \equiv 14 \pmod{15}$, we now have $3$ solutions:
$\quad 1^2 \equiv 1 \pmod{15}$
$\quad 4^2 \equiv 1 \pmod{15}$
$\quad 14^2 \equiv 1 \pmod{15}$
We conclude that there are exactly $4$ solutions for $\text{(1)}$.
$\endgroup$
