Section 17.4 Quadratic Reciprocity
Subsection 17.4.1 The theorem
Theorem 17.4.1. Quadratic Reciprocity.
If
Proof.
See Section 17.6.
Remark 17.4.2.
Note that the exponent has fractions, not Legendre symbols! We can multiply them to rewrite the exponent in a way some authors prefer:
Example 17.4.3. Computing with QR.
We immediately apply this to vastly simplify the calculations in Section 17.3. Let
Let's write the theorem out for this case. Since
There are two parts to this:
-
Since
and the Legendre symbol on the right is: -
We can also compute the power of
Combine these together and we get that
This is precisely
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β1β between Legendre symbols, and hence between whether there is a square root of two primes modulo each other.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 |
xxxxxxxxxx
ls=prime_range(3,40)
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.5.
Here is another way to say it. For odd primes
except when
Subsubsection 17.4.2.2 What does it do?
What does quadratic reciprocity do? It makes computation of Legendre symbolsAlgorithm 17.4.6.
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
or 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.7.
Let's calculate
Since they are coprime factors,
Since both
and are prime and congruent to modulo four,Reducing, we get
Finally, we use Theorem 16.7.1 and note that
(mod ) to get 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.)
And we can check them, of course.
xxxxxxxxxx
print(legendre_symbol(83,103))
print(legendre_symbol(219,383))
print(legendre_symbol(646,877))
Subsubsection 17.4.2.3 The Jacobi symbol
What else does quadratic reciprocity do? Indirectly, it allows us to compute Legendre symbolsDefinition 17.4.9.
Let
Then the Jacobi symbol,
Fact 17.4.10.
If
Proof.
See Exercise 17.7.13.
Sage note 17.4.11. 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))
Example 17.4.12.
And we can check this out with Sage:
xxxxxxxxxx
kronecker_symbol(943,997)
Example 17.4.13.
To put this into practice, let's redo
Check again with Sage:
xxxxxxxxxx
kronecker_symbol(646,877)