Skip to main content

Section 17.4 Quadratic 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 main theorem of the chapter.

As we've already alluded more than once, it is venerable. Parts 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.

Subsection 17.4.1 The theorem

Remark 17.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}}\text{.} \end{equation*}
Example 17.4.3. Computing with QR.

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

Let's write the theorem out for this case. Since \((3-1)/2=1\text{,}\) 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)\text{.} \end{equation*}

There are two parts to this:

  • Since \(1\in Q_3\) and \(2\notin Q_3\text{,}\) 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)\text{.} \end{equation*}

  • We can also compute the power of \(-1\text{:}\)

    \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)\text{.} \end{equation*}

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

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

  • \(\displaystyle 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. Compare to both Exercise 16.8.15 and Proposition 17.3.4.

Subsection 17.4.2 Why is this theorem different from all other theorems?

Subsubsection 17.4.2.1 What 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.

One way to think of this relation is to assert that the following table is almost symmetric about the (empty) diagonal – and that we have a simple formula for finding where it isn't symmetric.

\(p\backslash q\) 3 5 7 11 13 17 19 23 29 31 37
3 -1 -1 1 1 -1 -1 1 -1 -1 1
5 -1 -1 1 -1 -1 1 -1 1 1 -1
7 1 -1 -1 -1 -1 1 -1 1 1 1
11 -1 1 1 -1 -1 1 -1 -1 -1 1
13 1 -1 -1 -1 1 -1 1 1 -1 -1
17 -1 -1 -1 -1 1 1 -1 -1 -1 -1
19 1 1 -1 -1 -1 1 -1 -1 1 -1
23 -1 -1 1 1 1 -1 1 1 -1 -1
29 -1 1 1 -1 1 -1 -1 1 -1 -1
31 1 1 -1 1 -1 -1 -1 1 -1 -1
37 1 -1 1 1 -1 -1 -1 -1 -1 -1
Figure 17.4.4. Quadratic reciprocity as near symmetry of table of \(\left(\frac{p}{q}\right)\)

Try making bigger tables (represented as matrices) in the Sage cell below.

Remark 17.4.5.

Here is another way to say it. For odd primes \(p\) and \(q\text{,}\)

\begin{equation*} \left(\frac{p}{q}\right)= \left(\frac{q}{p}\right) \end{equation*}

except when \(p\equiv q\equiv 3\text{ (mod }4)\text{.}\) Or see Remark 17.4.2 for yet another way; both are often how Theorem 17.4.1 is stated in texts.

Subsubsection 17.4.2.2 What does it do?

What does quadratic reciprocity do?

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

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

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

Example 17.4.7.

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

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

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

Example 17.4.8.

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

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

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

  • \(\displaystyle \left(\frac{646}{877}\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.19 and 17.7.20.

Subsubsection 17.4.2.3 The Jacobi symbol

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

Definition 17.4.9.

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}\text{.} \end{equation*}

Then the Jacobi symbol, \(\left(\frac{a}{n}\right)\text{,}\) 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\) (see Exercise 17.7.12). Moreover, if \(\left(\frac{a}{n}\right)=-1\) then \(a\) is not a QR of \(n\text{.}\) (Showing all this essentially just uses Chinese Remainder Theorem and Hensel's Lemma, but we will not go into details here.)

The only thing not the same as for Legendre symbols is this:

Sage note 17.4.11. Names of functions may vary.

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

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

Instead, you can use the Jacobi symbol to help calculate 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 this leads to an algorithm which needs only about the square of the number of digits of \(p\) steps to evaluate a given symbol. Generically this is far fewer steps than one would need if one had to factor first (as far as we currently know).

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

Example 17.4.12.
\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. Also, this strategy is much easier to implement on a computer for automatic evaluation. (By the way, factoring \(943=23\cdot 41\) is itself not a gimme ‘by hand’.)

Before we go on, 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 you've struggled with some ‘by hand’. It's just the way these things are.

Example 17.4.13.

To put this into practice, let's redo \(\left(\frac{646}{877}\right)\text{:}\)

\begin{equation*} \left(\frac{646}{877}\right)= \left(\frac{2}{877}\right)\left(\frac{323}{877}\right) = (-1)\left(\frac{323}{877}\right) \text{ since }877\equiv 5\text{ (mod }8) \end{equation*}
\begin{equation*} =-\left(\frac{877}{323}\right)=-\left(\frac{231}{323}\right)\text{ since }877\equiv 1\text{ (mod }4) \end{equation*}
\begin{equation*} =-\left(-\left(\frac{323}{231}\right)\right)= \left(\frac{92}{231}\right)\text{ since both are }\equiv 3\text{ (mod }4) \end{equation*}
\begin{equation*} =\left(\frac{4}{231}\right)\left(\frac{23}{231}\right)=(+1)\left(\frac{23}{231}\right)\text{ because }4=2^2 \end{equation*}
\begin{equation*} =-\left(\frac{231}{23}\right)=-\left(\frac{1}{231}\right)=-1\text{ since both are }\equiv 3\text{ (mod }4)\text{.} \end{equation*}

Check again with Sage: