Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
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}. $$

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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