Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section17.4Quadratic Reciprocity

Now, if we had to do this prime by prime, it would still be horrible.

Instead, we will end up computing all Legendre symbols \(\left(\frac{a}{p}\right)\) with \(a\neq -1,2\) by reducing them to \(\left(\frac{-1}{p}\right)\) or \(\left(\frac{2}{p}\right)\) using techniques from Section 17.1 and the following theorem.

As we've already alluded more than once, this theorem is venerable. Parts of it were conjectured and proved by Euler, and all of it was conjectured by Legendre in terms of remainders (some commentators say he proved it as well). Carl Friedrich Gauss provided no fewer than eight proofs over the course of his lifetime. See Subsection 17.6.3 for a few more comments.

Subsection17.4.1The theorem

Proof
Remark17.4.2

We can multiply the fractions to rewrite it in a way some authors prefer: \begin{equation*}\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\end{equation*}

Example17.4.3Computing with QR

We immediately apply this to vastly simplify the calculations in Section 17.3. Let \(q=3\) and \(p>3\).

Let's write the theorem out for this case. Since \((3-1)/2=1\), we have \begin{equation*}\left(\frac{3}{p}\right)\left(\frac{p}{3}\right)=(-1)^{(p-1)/2}\text{, or }\left(\frac{3}{p}\right)=(-1)^{(p-1)/2}\left(\frac{p}{3}\right)\, .\end{equation*} There are two parts to this:

  • Since \(1\in Q_3\) and \(2\notin Q_3\), the Legendre symbol on the right is: \begin{equation*}\left(\frac{p}{3}\right)=1\text{ if }p\equiv 1\text{ (mod }3)\text{ and }\left(\frac{p}{3}\right)=-1\text{ if }p\equiv 2\text{ (mod }3)\, .\end{equation*}

  • We can also compute the power of \(-1\): \begin{equation*}(-1)^{(p-1)/2}=1\text{ if }p\equiv 1\text{ (mod }4)\text{ and }(-1)^{(p-1)/2}=-1\text{ if }p\equiv 3\text{ (mod }4)\, .\end{equation*}

Combine these together and we get that \(\left(\frac{3}{p}\right)=1\) exactly when one of these two cases occurs:

  • \(p\equiv 1\text{ (mod }3)\text{ and mod }(4)\)

  • \(p\equiv 3\text{ (mod }4)\text{ and }\equiv 2\text{ (mod }3)\)

This is precisely \(p\equiv 1,11\equiv \pm 1\) (mod \(12\)) as in Proposition 17.3.4!

It's amazing that this can work so easily.

Subsection17.4.2Why is this theorem different from all other theorems?

Subsubsection17.4.2.1What does it mean?

What does the term “quadratic reciprocity” even mean?

It means that there is a reciprocating relationship between Legendre symbols, and hence between whether there is a square root of two primes modulo each other.

For instance, it says that usually the following matrix is symmetric – and that we have a simple formula for when it isn't.

Here is another way to say it. For odd primes \(p\) and \(q\), \begin{equation*}\left(\frac{p}{q}\right)= \left(\frac{q}{p}\right)\end{equation*} except when \(p\equiv q\equiv 3\text{ (mod }4)\).

Subsubsection17.4.2.2What does it do?

What does quadratic reciprocity do?

It makes computation of Legendre symbols very, very easy if you have a prime factorization of \(p\) (and all the intermediate steps). You just need to use the following facts we already proved, in addition to quadratic reciprocity.

  • \(\left(\frac{-1}{p}\right)=1\iff p\equiv 1\text{ (mod }4)\)

  • \(\left(\frac{2}{p}\right)=1\iff p\equiv \pm 1\text{ (mod }8)\)

Proof
Example17.4.5

Let's calculate \(\left(\frac{99}{167}\right)\).

  • Since they are coprime factors, \(\left(\frac{99}{167}\right)=\left(\frac{9}{167}\right)\cdot \left(\frac{11}{167}\right)\).

  • Since both \(11\) and \(167\) are prime and congruent to \(3\) modulo four, \(\left(\frac{9}{167}\right)\cdot \left(\frac{11}{167}\right)=\left(\frac{3^2}{167}\right)\cdot -\left(\frac{167}{11}\right)\)

  • Reducing, we get \(\left(\frac{3^2}{167}\right)\cdot -\left(\frac{167}{11}\right)=-1\cdot \left(\frac{2}{11}\right)\)

  • Finally, we use Theorem 16.7.1 and note that \(11\equiv 3\) (mod \(8\)) to get \(-1\cdot \left(\frac{2}{11}\right)=-1\cdot -1 = 1\) and we see that ninety-nine is a QR modulo one hundred sixty-seven.

Example17.4.6

In a classroom experience, try these. (Else, see Exercise 17.7.15.)

  • \(\left(\frac{83}{103}\right)\)

  • \(\left(\frac{219}{383}\right)\)

And we can check them, of course.

We can also come up with congruence criteria like above for other primes. See the exercises, such as 17.7.5 and 17.7.17.

Subsubsection17.4.2.3The Jacobi symbol

What else does quadratic reciprocity do? Indirectly, it allows us to compute Legendre symbols \(\left(\frac{a}{p}\right)\) without factoring \(a\).

Definition17.4.7

Let \(n\) be an odd number which factors as \begin{equation*}n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\; .\end{equation*} Then the Jacobi symbol, \(\left(\frac{a}{n}\right)\), is just the product of the relevant Legendre symbols: \begin{equation*}\left(\frac{a}{n}\right)=\left(\frac{a}{p_1}\right)^{e_1}\left(\frac{a}{p_2}\right)^{e_2}\cdots \left(\frac{a}{p_k}\right)^{e_k}\end{equation*}

Amazingly, the Jacobi symbol has all the same properties the Legendre symbol has – even quadratic reciprocity and the values for \(a=-1,2\). And if \begin{equation*}\left(\frac{a}{n}\right)=-1\end{equation*} then \(a\) is not a QR of \(n\). The only thing not the same is:

Sage note17.4.9Names of functions may vary

In Sage, this is named after yet another generalization called the Kronecker symbol.

The goal of introducing this is not to use the definition of the Jacobi symbol to do anything. That would be pointless.

Instead, the idea is that you can use the Jacobi symbol to do your calculation of Legendre symbols! After all, they follow almost all the same rules. You'd only need to factor here in order to make sure you don't have an even number in the denominator of the symbol.

It turns out that, unlike factoring (as far as we know), this leads to an algorithm which needs only about the square of the number of digits of \(p\) steps to evaluate the symbol, which is much better than one would need if one had to factor first.

Some examples would be just as fast doing it either way, like \(\left(\frac{83}{103}\right)\). But others would be much slower, because you'd have to factor a few different times. Here's an example; note that \(943\) is not prime.

Example17.4.10

\begin{equation*}\left(\frac{943}{997}\right)=\left(\frac{997}{943}\right)\text{ since }997\equiv 1\text{ (mod }4)\end{equation*} \begin{equation*}=\left(\frac{54}{943}\right)=\left(\frac{2}{943}\right)\left(\frac{27}{943}\right)=(+1)\left(\frac{27}{943}\right)\text{ since }943\equiv -1\text{ (mod }8)\end{equation*} \begin{equation*}=-\left(\frac{943}{27}\right)\text{ since both are }\equiv 3\text{ (mod }4)\end{equation*} \begin{equation*}=-\left(\frac{25}{27}\right)=-1\text{ because }25=5^2\end{equation*}

And we can check this out with Sage:

Compare this example with having to first factor \(943\) and then still do the whole reciprocity dance, and this is much easier and more automatic for a computer to do. (By the way, factoring \(943=23\cdot 41\) is itself not a gimme ‘by hand’.)

Before we go one, if you haven't tried to compute lots of things with quadratic reciprocity, don't go on until you do. You won't appreciate the power and usefulness of the proof until then. It's just the way these things are.