11.5   Quadratic Reciprocity

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:

Your browser does not support java.

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

Hint: This result, which is known as the Quadratic Reciprocity Theorem, is a tough one. You may find the suggestions given below helpful.

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

Your browser does not support java.

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

LS(3, 1000003).

Determining if the equation x2 === 3 (mod 1000003) has solutions is a tall order. However, the Quadratic Reciprocity Theorem will tell us that

LS(3, 1000003) = –LS(1000003, 3)

and since 1000003 === 1 (mod 3), we see instantly that

LS(1000003, 3) = LS(1, 3) = 1.

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.

Section 11.1 | Section 11.2 | Section 11.3 | Section 11.4 | Section 11.5 | Section 11.6

Chapter 11 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company