How do I use the Law of Quadratic Reciprocity to solve a congruence?

Question

If I have a congruence like the following:

$$3x^2 + 5x + 1 \equiv 0 \pmod{q}$$

How would I use the law of quadratic reciprocity to determine if it has a solution? I really have no idea where to go with this. The law of quadratic reciprocity is that:

$$\left( \frac{p}{q} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \left( \frac{q}{p} \right) $$

So what is $p$ in this problem? And once I have it, how do I know if there is a solution? Is it when $\left( \frac{p}{q} \right) = 1$?

Answer 1

An illustration of the use of the law

Let us calculate $(\frac{37}{73})$ :

We have two primes, both of the form $4k+1$, hence we have

$$(\frac{37}{73})=(\frac{73}{37})=(\frac{-1}{37})=1$$

Note that $73\equiv -1\mod 37$ and that $(\frac{-1}{p})=1$ holds for $p=2$ and for $p=4k+1$. Not always are we lucky to get the result so fast, but with several steps, we usually get the result much faster than by checking the possible quadratic residues.

In your example, we have $$(\frac{13}{q})=(\frac{q}{13})=(\frac{q\mod 13}{13})$$

Answer 2

You don't have to use the law of quadratic reciprocity to solve this equation: multiply it by $9$ to obtain $$9(3x2+5x+1)\equiv x^2+6x+9=(x+3)^2\equiv 0\mod 13.$$ As $\mathbf Z/13\mathbf Z$ is a field, the only solution is $\;x\equiv -3\equiv 10$.