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 whetherpis a quadratic residue moduloq.## 11.5.1 Basics

We will be interested in comparing when

pis congruent to a square modqwith whetherqis a square modp, wherepandqare 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

pandqbe odd primes. Conjecture a relationship between LS(p,q) and LS(q,p). Specifically, find conditions forpandqthat 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 primesq. The following applet allows us to fix the primep, and compare it with the firstBodd primes. The output shows one row for each primeq. After displayingq, it shows the values of LS(p,q) and LS(q,p) for the fixed value ofpand theqfor that line. For example, if we keep the primep= 3 fixed and take the first 20 primes forq, we get## 11.5.3 Additional Tips

Try different values of

pwith 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 ofpfor which the relationship is simple. Once you can find some primespfor which you are comfortable conjecturing the relationship between LS(p,q) and LS(q,p) for varyingq, try to pin down exactly which primespare easy (i.e., go from a list of "easy values ofp" 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 evaluateLS(3, 1000003). Determining if the equation

x^{2}3 (mod 1000003) has solutions is a tall order. However, the Quadratic Reciprocity Theorem will tell us thatLS(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

x^{2}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

Copyright © 2001 by W. H. Freeman and Company