Note: The limitations of typesetting mathematics in web pages makes the use of the usual version of the Legendre symbol impractical. Instead, we shall write LS(p, q) to indicate whether p is a quadratic residue modulo q.
11.5.1 Basics
We will be interested in comparing when p is congruent to a square mod q with whether q is a square mod p, where p and q are odd primes. In other words, we will be comparing the Legendre symbols LS(p, q) and LS(q, p).
The applet below allows us to easily compare the values of LS(p, q) and LS(q, p). Try it out:
The resulting output tells us that 3 is not congruent to a square mod 5, and 5 is not congruent to a square mod 3. Try different combinations of odd primes with this applet.
Research Question 4
Let p and q be odd primes. Conjecture a relationship
between LS(p, q) and LS(q, p). Specifically,
find conditions for p and q that will determine
when LS(p, q) = LS(q, p)
and when LS(p, q) = –LS(q, p).
|
11.5.2 Tabulating Data
To make it easier to spot patterns, we will keep one prime fixed (say p) and use lots of primes q. The following applet allows us to fix the prime p, and compare it with the first B odd primes. The output shows one row for each prime q. After displaying q, it shows the values of LS(p, q) and LS(q, p) for the fixed value of p and the q for that line. For example, if we keep the prime p = 3 fixed and take the first 20 primes for q, we get
11.5.3 Additional Tips
Try different values of p with the preceding applet. The relationship between LS(p, q) and LS(q, p) is subtle and you may not get it all in one shot. Try to find some values of p for which the relationship is simple. Once you can find some primes p for which you are comfortable conjecturing the relationship between LS(p, q) and LS(q, p) for varying q, try to pin down exactly which primes p are easy (i.e., go from a list of "easy values of p" to a conjecture about easy primes).
While it would be wonderful if you are able to prove your conjectures in this section, proofs are somewhat hard to come by. Ironically, there may be more proofs of quadratic reciprocity than of any other theorem in the course. However, they are all significantly more difficult that the theorems we have covered thus far.
11.5.4 What's Quadratic Reciprocity Good For?
A reasonable question. One use is to efficiently compute values of LS(p, q). For example, suppose that you wish to evaluate
Determining if the equation x2
3 (mod 1000003) has solutions is a
tall order. However, the Quadratic Reciprocity Theorem will tell
us that
and since 1000003
1 (mod 3), we see instantly that
Putting this together, we see that
LS(3, 1000003) = –1, and so x2
3 (mod 1000003) has no solutions.
Thus by applying the Quadratic Reciprocity Theorem, we will be able to quickly simplify a complicated calculation. We will return to applications of the Quadratic Reciprocity Theorem in the chapter summary.