# 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}$). – Berci Apr 18 '13 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$ – lab bhattacharjee Apr 18 '13 at 12:11