Section17.4Quadratic Reciprocity

Now, if we had to do this prime by prime, it would 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 last time and the following theorem. This theorem is venerable; parts of it were conjectured and proved by Euler, all of it was conjectured by Legendre, and Carl Friedrich Gauss provided no fewer than eight proofs over the course of his lifetime.

Subsection17.4.1The Theorem

Legendre thought of this quite differently, in terms of remainders. Notice also that we can multiply the fractions to rewrite it as \[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\, ,\] though I like the more symmetric version better.

Example17.4.2Computing with QR

We immediately apply this to vastly simplify the calculation we just did.

  • Let \(q=3\) and \(p>3\).
  • Since \((3-1)/2=1\), we have \[\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)\, .\]
  • Since \(1\in Q_3\) and \(2\notin Q_3\), the Legendre symbol on the right evaluates like this: \[\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)\, .\]
  • Likewise, \[(-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)\, .\]
  • Combine these together and we get that \(\left(\frac{3}{p}\right)=1\) exactly \[\text{when }p\equiv 1\text{ mod }(3)\text{ and mod }(4)\text{, or when }p\equiv 3\text{ mod }(4)\text{ and }\equiv 2\text{ mod }(3)\; ,\] which is precisely \(p\equiv 1,11\equiv \pm 1\) mod (12) as above!

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.

We can say it another way. For odd primes \(p\) and \(q\), \[\left(\frac{p}{q}\right)= \left(\frac{q}{p}\right)\] 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)\)
Example17.4.3
  • \(\left(\frac{83}{103}\right)\)
  • \(\left(\frac{219}{383}\right)\)

We can also come up with congruence criteria like above for other primes. See the exercises.

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 \(p\).

Definition17.4.4
Let \(n\) be an odd number which factors as \[n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\; .\] Then the Jacobi symbol\(\left(\frac{a}{n}\right)\) is just the product of the relevant Legendre symbols, \[\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}\]

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 \[\left(\frac{a}{n}\right)=-1\] then \(a\) is not a QR of \(n\). The only thing not the same is that \[\left(\frac{a}{n}\right)=1 \not\Rightarrow a\text{ is a QR of }n\; .\]

Remark17.4.5

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

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

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. \[\left(\frac{943}{997}\right)=\left(\frac{997}{943}\right)\text{ since }997\equiv 1\text{ mod }(4)\] \[=\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)\] \[=-\left(\frac{943}{27}\right)\text{ since both are }\equiv 3\text{ mod }(4)\] \[=-\left(\frac{25}{27}\right)=-1\text{ because }25=5^2\] And we can check this out with Sage:

Compare this 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, \(943=23\cdot 41\) – not a gimme.)

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.