**Proof.** With Theorem , , where *n* is
the number of least positive residues of *a*, 2*a*, ,
that are greater than . In
other words, *n* is the number of terms of *a*, 2*a*, ,
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*=4*ah*+*p* for some integer *h*.
Replacing *p* with 4*ah*+*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*+4*a* for some positive
integer *a*. Then

Similarly,

It follows from Lemma that . Therefore,

Noting that , we see that and have the same parity, proving ().

Suppose next that . Assume that *p*=-*q*+4*a*. 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.

Wed Jun 5 14:35:14 CDT 1996