Proof. With Theorem , , where n is the number of least positive residues of a, 2a, , that are greater than . In other words, n is the number of terms of a, 2a, , that appear in the following intervals:
where . (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 (), we see that n is equal to an even integer plus the number of integers in the following intervals
According to the argument above, . Therefore, . Similarly, we can prove the following lemma.
Proof. Suppose first that . We may assume without loss of generality that p>q, and p=q+4a for some positive integer a. Then
It follows from Lemma that . Therefore,
Noting that , we see that and have the same parity, proving ().
Suppose next that . Assume that p=-q+4a. Then
This implies that . Noting that implies that 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.