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$?


  • $\begingroup$ 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. $\endgroup$ – TRY Oct 30 '11 at 23:50
  • 5
    $\begingroup$ +1 for showing that you have thought about the problem yourself before posting! Unfortunately it's not something that many new users do :) $\endgroup$ – 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}. $$


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}. $$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.