next up previous contents
Next: Excerses Up: Quadratic Residues Previous: Exercises

Quadratic Reciprocity


Proof. With Theorem gif, tex2html_wrap_inline3041 , where n is the number of least positive residues of a, 2a, tex2html_wrap_inline3049 , tex2html_wrap_inline3051 that are greater than tex2html_wrap_inline2959 . In other words, n is the number of terms of a, 2a, tex2html_wrap_inline3049 , tex2html_wrap_inline3051 that appear in the following intervals:


where tex2html_wrap_inline3067 . (why this k is big enough?) Since the integers under consideration are all multiples of a, n is equal to the number of integers in the following intervals:


Suppose that q=4ah+p for some integer h. Replacing p with 4ah+q in (gif), we see that n is equal to an even integer plus the number tex2html_wrap_inline1609 of integers in the following intervals


According to the argument above, tex2html_wrap_inline3089 . Therefore, tex2html_wrap_inline3091 . Similarly, we can prove the following lemma.



Proof. Suppose first that tex2html_wrap_inline3113 . We may assume without loss of generality that p>q, and p=q+4a for some positive integer a. Then




It follows from Lemma gif that tex2html_wrap_inline3125 . Therefore,


Noting that tex2html_wrap_inline3113 , we see that tex2html_wrap_inline2909 and tex2html_wrap_inline3133 have the same parity, proving (gif).

Suppose next that tex2html_wrap_inline3135 . Assume that p=-q+4a. Then


This implies that tex2html_wrap_inline3155 . Noting that tex2html_wrap_inline3157 implies that tex2html_wrap_inline3133 is always even. Therefore, the proof is complete. The Low of Quadratic Reciprocity can be used to compute Legendre symbols. For instance,


Therefore 257 is not a quadratic residue modulo 137.

Although the theory above is simple and beautiful, it is nevertheless rather negative. It tells you if the quadratic congruence is soluble, it does not tell you the solutions nor the a method to find the solutions. It is in fact a very difficult problem to determine the solutions. However, some special cases can be easily done.

Donald Hazlewood and Carol Hazlewood
Wed Jun 5 14:35:14 CDT 1996