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

**Proof:**

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

.

Similarly,

.

Now note that

.

Using this,

.

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,

## 2 comments

Comments feed for this article

December 29, 2009 at 21:49

darijVery nice proof! Some typing mistakes you might want to fix:

- Either $U$ is not a subgroup of $G$, or you want to define $G$ by $G:= ({\mathbb Z}/p{\mathbb Z})^* \times ({\mathbb Z}/q{\mathbb Z})^* $ instead.

- In the formula following the first “Similarly,”, there is one closing bracket too much.

- It would be nice if you made the two meanings of $\left(\frac{a}{b}\right)$ (a fraction in bracket, vs. a Lagrange symbol) better distinguishable. It’s clear for the expert, but the newcomer could be confused. For instance, you can safely leave out the brackets in $\left(\frac{q-1}{2}\right)!$.

darij

December 29, 2009 at 22:21

abhishekparabThanks for the typos. Corrected except for the fraction / Legendre symbol. (PS: it is not Lagrange :P )

Note: In WordPress, we type latex code using latex instead of the standard way of .