# Find all odd primes $p$ for which $15$ is a quadratic residue modulo $p$

I want to find all odd primes $p$ for which $15$ is a quadratic residue modulo $p$.

My thoughts so far: I want to find $p$ such that $\left( \frac{15}{p} \right) = 1$. By multiplicativity of the Legendre symbol, this is equivalent to $\left( \frac{5}{p} \right) \left( \frac{3}{p} \right) = 1$. Using the Law of Quadratic Reciprocity, this is equivalent to finding $p$ such that $- \left( \frac{p}{5} \right) \left( \frac{p}{3} \right) = 1$.

So there are two cases:

1. $\left( \frac{p}{5} \right) = -1, \left( \frac{p}{3} \right) = 1$.

2. $\left( \frac{p}{5} \right) = 1, \left( \frac{p}{3} \right) = -1$.

For case (1.), the quadratic residues modulo $5$ are $1$ and $4$, so for $\left( \frac{p}{5} \right ) = -1$, we must have that $p$ is $2$ or $3$ modulo $5$. We must also have that $p$ is $1$ modulo $3$ from the other condition. One of these pairs is incompatible, and we can solve to give $p$ is $13$ modulo $15$.

Similarly for case (2.)

Is this the correct approach? I'm unsure if each step in my working is an "if and only if". If $p$ is $13$ modulo $15$, is $15$ necessarily a quadratic residue modulo $p$?

Thanks!

-
I've noticed a mistake: I've used the law of quadratic reciprocity not quite correctly. I should get the extra condition that $p$ is congruent to 3 modulo 4. – TRY Oct 30 '11 at 23:50
+1 for showing that you have thought about the problem yourself before posting! Unfortunately it's not something that many new users do :) – Zev Chonoles Oct 31 '11 at 0:06

I think the law of quadratic reciprocity hasn't been fully applied. From Quadratic Reciprocity, $$\left(\frac{15}{p}\right)=\left(\frac{3}{p}\right)\left(\frac{5}{p}\right)=(-1)^{(p-1)/2}\left(\frac{p}{3}\right)\left(\frac{p}{5}\right).$$ There are now two cases. If $p\equiv 1\pmod{4}$, you have $(15|p)=(p|3)(p|5)$, so you want $(p|3)$ and $(p|5)$ to have the same sign. Then the squares modulo $3$ and $5$ are $p\equiv 1\pmod{3}$ and $p\equiv 1,4\pmod{5}$, and the nonsquares are $p\equiv 2\pmod{3}$ and $p\equiv 2,3\pmod{5}$. Using the extra condition that $p\equiv 1\pmod{4}$, you can just check that the only possibilities are $$p\equiv 1,17,49,53\pmod{60}$$ based on which conditions you choose.

The second case is $p\equiv 3\pmod{4}$, and you now want $(p|3)$ and $(p|5)$ to have different signs. Again writing out the squares and nonsquares modulo $3$ and $5$, you have $p\equiv 1\pmod{3}$ and $p\equiv 2,3\pmod{5}$, or $p\equiv 2\pmod{3}$ and $p\equiv 1,4\pmod{5}$. Now using the condition that $p\equiv 3\pmod{4}$, the only possibilities are $$p\equiv 7,11,43,59\pmod{60}.$$

-

Note that there is no such thing as conditions mod 3 and mod 5 being incompatible; see The Chinese Remainder Theorem. In particular, 7 is 2 mod 5 and 1 mod 3.

-

You must also consider your primes mod 4, as that alters the behavior of reciprocity. So, in the order I found them, all values are $$1,49; \; 17, 53; \; 11, 59; \; 7, 43 \pmod {60}.$$ In ordinary numerical order, $$1, 7,11,17,43,49, 53,59 \pmod {60}.$$

-