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.
Subsection17.4.1The theorem
Theorem17.4.1.Quadratic Reciprocity.
If \(p\) and \(q\) are odd primes not equal to each other, then
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!
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 3 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 Table 17.4.4 is almost symmetric about the (empty) diagonal – and that we have a simple formula for finding where it isn’t symmetric.
Table17.4.4.Quadratic reciprocity as near symmetry of table of \(\left(\frac{p}{q}\right)\)
\(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
Try making bigger tables (represented as matrices) in the Sage cell below.
Remark17.4.5.
Here is another way to say it. For odd primes \(p\) and \(q\text{,}\)
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.
Subsubsection17.4.2.2What 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.
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.
Example17.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.
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\text{.}\)
Amazingly, the Jacobi symbol has all the same properties 4 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:
Fact17.4.10.
If \(n\) is not prime, then \(\left(\frac{a}{n}\right)=1\) does not necessarily imply \(a\) is a QR of \(n\text{.}\)
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.
Example17.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.
Example17.4.13.
To put this into practice, let’s redo \(\left(\frac{646}{877}\right)\text{:}\)
\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:
There are vast generalizations of these laws that take the reciprocation to a very deep level; see [E.4.23, Chapter 19] for an accessible and engaging take on quadratic reciprocity in this context.