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

Quadratic Reciprocity

  lemma531

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:

displaymath3065

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:

  equation539

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

displaymath3087

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

lemma558

  theorem1175

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

displaymath3121

Similarly,

displaymath3123

It follows from Lemma gif that tex2html_wrap_inline3125 . Therefore,

displaymath3127

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

eqnarray578

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,

eqnarray586

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