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

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

• If $p$ and $q$ are distinct primes, we have $(\frac{p}{q})=1$ if and only if $x^2\equiv p\mod q$ for some $x\in\mathbb Z$ – Peter Mar 29 '17 at 16:11
• @Peter Okay. So then $p$ is a perfect square modulo $q$ iff $\left( \frac{p}{q} \right)$, right? So the answer to my last question is yes? But how do I solve my problem? – Reed Oei Mar 29 '17 at 16:13
• @Peter Okay, maybe I'm not asking this question very well, but in my book (wstein.org/ent/ent.pdf) it says "Using Theorem 4.1.7 [Quadratic Reciprocity), we can decide whether or not $b^2 − 4ac$ is a perfect square in $Z/pZ$, and hence whether or not $ax^2 + bx + c = 0$ has a solution in $Z/pZ$." But how do you do that? – Reed Oei Mar 29 '17 at 16:26
• @Peter But how do I use quadratic reciprocity to determine whether the discriminant is a quadratic residue modulo $q$? Why is the law of quadratic reciprocity helpful? How is it any improvement on just calculating the normal Legendre symbol? – Reed Oei Mar 29 '17 at 16:31
• @Peter But how? If I want to calculate $( \frac{p}{q} )$, how does knowing the law of quadratic reciprocity help me do that more easily? Isn't this easier: $( \frac{p}{q} ) \equiv p^{\frac{q - 1}{2}} \pmod{q}$? Is that not a correct equation, and if so, what are the limitations that prevent me from using it that way? – Reed Oei Mar 29 '17 at 16:35

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

• If we have to factor the numerator, we need the law $$(\frac{ab}{q})=(\frac{a}{q})\cdot (\frac{b}{q})$$ – Peter Mar 29 '17 at 16:48
• Yes thank you this does help, but I still have some more questions. What if the primes aren't of the form $4k + 1$, like $(\frac{31}{103})$, or if one is but the other isn't? And how did you equate $(\frac{13}{q})$ and $(\frac{q}{13})$? It is my understanding that you got $(\frac{37}{73}) = (\frac{73}{37})$ because both are one more than a multiple of $4$, so both $\frac{p-1}{2}$ and $\frac{q-1}{2}$ are even, therefore you have $(-1)^{\text{even}} = 1$ and that part of the law drops out, but without additional information about $q$ how can you make that assertion? – Reed Oei Mar 29 '17 at 16:49
• In the case of two primes, the sign changes only if BOTH primes are of the form $4k+3$, for example $(\frac{43}{67})=-(\frac{67}{43})$. Otherwise we have equality, so we can simply exchange the primes without changing the value of the symbol. Hence, in the case of $q$ and $13$, it does not matter which remainder $q$ has modulo $4$. If you would have $q$ and $47$, you would have to distinguish whether $q$ is congruent to $1$ or $3$ modulo $4$ – Peter Mar 29 '17 at 16:51
• Ah yes that makes sense, because if either is $4k + 1$, then $\frac{4k + 1}{2}$ is even so the product of it and the other must be even too. So I think I have just one more question, what would I use the law for other than just simplifying the calculation of the Legendre symbol? – Reed Oei Mar 29 '17 at 17:01
• At the moment, nothing else comes in my mind, the law is a tool to handle legendre symbols. – Peter Mar 29 '17 at 17:02

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

• Okay. If I were to change the 13 to $q$ for example, how would I determine if it has a solution? I'm really trying to figure out how to use the law of quadratic reciprocity for anything because I don't understand it. – Reed Oei Mar 29 '17 at 16:22
• Same is in $\mathbf R$: you have to find is the discriminant has a square root. As long as you only want to know if the equation has roots, you can determine whether this square root exists in $\mathbf F_q$ using the law of quadratic reciprocity. This will not give you the value of this square root. – Bernard Mar 29 '17 at 16:26
• I understand that the goal is to determine if the discriminant is a square, but exactly how do I use the law of quadratic reciprocity to do that? What are the $p$ and the $q$ in the equation? – Reed Oei Mar 29 '17 at 16:28
• iF The discriminant is an integer between $2$ and $q-1$, you decompose it as a product of primes, and calculate the value of the Legendre symbol, which is multiplicative for pairwise coprime elements. – Bernard Mar 29 '17 at 16:31
• I understand that too, I guess my problem is I just don't see where the law of quadratic reciprocity comes into it? – Reed Oei Mar 29 '17 at 16:36