In this section, I present a simple proof of Gauss’ Quadratic Reciprocity due to G. Rousseau that uses the Chinese Remainder theorem, simple congruences and counting arguments and evades the Gauss’ Lemma!
Theorem Let and be distinct odd primes. Then
where is a normal subgroup of . We count the product of cosets of in three ways and equate them. The two products so obtained will be, upto a sign, be equal.
Clearly, is a system of representatives for the cosets of .
[For example, if , then .]
The left product is
Now note that
We now claim that that
is another set of representatives of cosets of . Here, we invoke the Chinese Remainder Theorem which asserts that
The product of , modulo is,
where the first step is justified after observing that (respectively, ) is the highest multiple of (resp. ) which is less than and the last step follows from Euler’s criterion and Fermat’s little theorem. Similarly, we have a similar expression for modulo q and hence, now becomes,
Comparing the above two expressions for gives,
and hence, the reciprocity law,