# Computing Legendre symbol value using quadratic reciprocity

I have an example in my lecture notes that says:

Check

$$\left( \frac{31}{1019} \right) = -1$$

where $$\left( \frac{a}{b} \right)$$ is the Legendre symbol.

I said, because $$1019$$ and $$31%$$ are both primes, we can use quadratic reciprocity and get:

$$\left( \frac{31}{1019} \right)\left( \frac{1019}{31} \right) = (-1)^{509 \times 15} = -1$$

and so we get

$$\left( \frac{31}{1019} \right) = - \left( \frac{1019}{31} \right) = - \left( \frac{27}{31} \right).$$

Now I'm a little stuck as $$27 = 3^3$$ and so this isn't $$+1$$ and so I end up with $$-(-1) = +1$$ which isn't the answer. Then I thought of doing quadratic reciprocity on

$$\left( \frac{3}{31} \right)^3$$

which gives me

$$\left( \frac{3}{31} \right) \left( \frac{31}{3} \right) = (-1)^{15 \times 1} = -1$$

and so

$$\left( \frac{3}{31} \right) = - \left( \frac{31}{3} \right) = - \left( \frac{1}{3} \right) = -(+1) = -1$$

so now I have

$$- \left(-1 \right)^3 = -(-1) = +1$$

which, again, is the wrong answer.

Where have I gone wrong?

• $27\equiv -4\pmod{31}$ and, $-1$ is not a quadratic remainder, because $31\equiv 3\pmod{4}$, hence, neither is $-4$ (because $\exists 1/2\pmod{31}$). Apr 18, 2013 at 11:46

$$\left(\frac{27}{31}\right)=\left(\frac{-4}{31}\right)=\left(\frac{2^2}{31}\right)\left(\frac{-1}{31}\right)=\left(\frac{-1}{31}\right)\text{ as } (\pm2)^2\equiv 4\pmod {31}$$
Again, we know, $\left(\frac{-1}p\right)=1\iff$ prime $p\equiv1\pmod 4$
• @Kaish, $31\equiv-1\pmod 4$ Apr 18, 2013 at 12:11