NTIC Quadratic Reciprocity

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

🔗

Theorem 17.4.1. Quadratic Reciprocity.

If $p$ and $q$ are odd primes not equal to each other, then

$\begin{equation*} \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\text{.} \end{equation*}$

🔗

Proof.

See Section 17.6.

🔗

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:

$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. 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 matrix is almost symmetric – and that we have a simple formula for finding where it isn't.

xxxxxxxxxx
 
ls=prime_range(3,50)
M=matrix(len(ls),[legendre_symbol(a,b) for a in ls for b in ls])
show(block_matrix(2,[0, matrix(1,len(ls),ls), matrix(len(ls),1,ls), M]))

🔗

Remark 17.4.4.

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.

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

🔗

Algorithm 17.4.5.

Any Legendre symbol can be computed using the following steps, not necessarily in this order and often multiple times:

Factor the top and use Proposition 16.4.7, then computing each one separately.
Reduce modulo the bottom and/or use Proposition 17.1.3 to get convenient tops (especially perfect squares).
When you get to an odd prime on the top and bottom, use Theorem 17.4.1.
When the top is $-1$ or $2\text{,}$ use Example 16.6.2 or Theorem 16.7.1 to finish your computation.

🔗

Proof.

Read the chapter up to this point, plus the proof of Theorem 17.4.1.

🔗

Example 17.4.6.

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

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

$\left(\frac{83}{103}\right)$
$\left(\frac{219}{383}\right)$
$\left(\frac{646}{877}\right)$

And we can check them, of course.

xxxxxxxxxx
 
print(legendre_symbol(83,103))
print(legendre_symbol(219,383))
print(legendre_symbol(646,877))

🔗

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

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{.}$ The only thing not the same as for Legendre symbols is this:

🔗

Fact 17.4.9.

If $n$ is not prime, then $\left(\frac{a}{n}\right)=1$ does not necessarily imply $a$ is a QR of $n\text{.}$

🔗

Sage note 17.4.10. Names of functions may vary.

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

xxxxxxxxxx
 
print(kronecker_symbol(8,15))
print(quadratic_residues(15))

🔗

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

$\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:

xxxxxxxxxx
 
kronecker_symbol(943,997)

🔗

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

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:

xxxxxxxxxx
 
kronecker_symbol(646,877)