Characterize all primes p such that 15 is a square modulo p I was having some difficulty understanding the following parts of this proof:
Proof:
Obviously, 15 is a square mod 2, 3, 5. So suppose p > 5. We compute the Jacobi
symbol:
($\frac{15}{p}$) = ($\frac{3}{p})(\frac{5}{p}$) = $(-1)^\frac{p-1}{2}(\frac{p}{3})(\frac{p}{5}) $
Up to here, all is fine, but now is where I got confused:
"So the answer will depend on p modulo 4 · 15 = 60. Looking at the φ(60) = 2 · 2 · 4 = 16
residue classes mod 60, we see that the RHS is +1 exactly when
$p  \equiv    \pm1   , \pm7  ,  \pm 11,   \pm17 \pmod{60}$ "
I have absolutely no clue why we are working mod 60 nor how they obtained the above numbers.
Any help would be appreciated
 A: This is a fairly standard exercise. As you note, using the Legendre (or Jacobi) symbol and Quadratic Reciprocity, we have
$$\begin{align*}
\left(\frac{15}{p}\right) &= \left(\frac{3}{p}\right)\left(\frac{5}{p}\right)\\
&=(-1)^{(\frac{p-1}{2})(\frac{3-1}{2})}\left(\frac{p}{3}\right)(-1)^{(\frac{p-1}{2})(\frac{5-1}{2})}\left(\frac{p}{5}\right)\\
&= (-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\left(\frac{p}{5}\right).
\end{align*}$$
So we have a number of cases. Excluding $2$, $3$, and $5$ (for which $15$ is a square), we have:

*

*If $p\equiv 1\pmod{4}$, then for $15$ to be a square modulo $p$ we need $\left(\frac{p}{3}\right)=\left(\frac{5}{p}\right)$. That means either $p\equiv 1\pmod{3}$ and $p\equiv \pm 1\pmod{5}$; or $p\equiv 2\pmod{3}$ and $p\equiv \pm2\pmod{5}$. Using the Chinese Remainder Theorem for the three congruences, we get: if $p\equiv 1\pmod{4}$, $p\equiv1 \pmod{3}$, and $p\equiv 1\pmod{5}$, then $p\equiv 1\pmod{60}$. If $p\equiv 1\pmod{4}$, $p\equiv 1\pmod{3}$, and $p\equiv 4\pmod{5}$, then $p\equiv 49\equiv -11\pmod{60}$. Etc. We end up with
$$p\equiv 1,\ -11,\ 17,\  -7\pmod{60}.$$


*If $p\equiv 3\pmod{4}$, then we need $\left(\frac{p}{3}\right)=-\left(\frac{p}{5}\right)$, so either $p\equiv 1\pmod{3}$ and $p\equiv \pm 2\pmod{5}$, or else $p\equiv 2\pmod{3}$ and $p\equiv \pm1\pmod{5}$. These give the other four values modulo $60$:
$$p\equiv 7,\ -17, 11,\ -1\pmod{60}.$$
So this gives that the primes for which $15$ is a square are precisely $p=2$, $3$, $5$, and all primes $p$ such that $p\equiv \pm 1,\ \pm7,\ \pm 11,\ \pm 17\pmod{60}$, as claimed.
