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 {p} and {q} be distinct odd primes. Then
\displaystyle \displaystyle\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}


\displaystyle G:= ( ({\mathbb Z}/p{\mathbb Z})^* \times ({\mathbb Z}/q{\mathbb Z})^* )/ U

where {U= \{ (1,1), (-1,-1) \}} is a normal subgroup of {G}. We count the product {\pi} of cosets of {U} in three ways and equate them. The two products so obtained will be, upto a sign, be equal.
Clearly, {\mathcal S:= \{ (i,j) | i = 1,2,\dots ,(p-1) \text{ and } j=1,2,\dots,(\frac{q-1}{2})\}} is a system of representatives for the cosets of {U}.

[For example, if {j=\frac{q+r}{2}}, then (i,\frac{q+r}{2})U = (i,\frac{q+r}{2}).(-1,-1)U = (-i,q-\frac{q+r}{2})U = (p-i,\frac{q-r}{2})U \in \mathcal S .]

The left product is
\displaystyle\prod_{i=1}^{p-1} \prod_{j=1}^{\frac{q-1}{2}} i = \displaystyle\left(\prod_{i=1}^{p-1}i\right)^{\frac{q-1}{2}} = \displaystyle((p-1)!)^{\frac{q-1}{2}} .
\displaystyle\prod_{i=1}^{p-1} \prod_{j=1}^{\frac{q-1}{2}} j = \displaystyle\left(\prod_{j=1}^{\frac{q-1}{2}}j\right)^{p-1} = \displaystyle\left(\left(\frac{q-1)}{2}\right)!\right)^{p-1} .
Now note that

\displaystyle\left(\left(\frac{q-1)}{2}\right)!\right)^2 = (1.2.\cdots . (\frac{q-1}{2}))^2
= 1.2.\cdots .(\frac{q-1}{2}).(\frac{q-1}{2}).(\frac{q-3}{2}).\cdots .1
\equiv 1.2.\cdots .(\frac{q-1}{2}).(\frac{q-1}{2}-q).(\frac{q-3}{2}-q).\cdots .(1-q) (\mod q)
\equiv 1.2.\cdots .(\frac{q-1}{2}).(-1).(q-\frac{q-1}{2}).(-1).(q-\frac{q-3}{2}).\cdots .(-1)(q-1) (\mod q)
\equiv 1.2.\cdots .(\frac{q-1}{2}).(-1)^{\frac{q-1}{2}} .(\frac{q+1}{2}).(\frac{q+3}{2}).\cdots .(q-1) (\mod q)
\equiv (-1)^{\frac{q-1}{2}} . (q-1)! (\mod q).

Using this,

\boxed{\pi = \displaystyle\left( ((p-1)!)^{\frac{q-1}{2}} , (-1)^{\frac{q-1}{2}\frac{p-1}{2}} . ((q-1)!)^{\frac{p-1}{2}} \right) U}.

We now claim that that

\displaystyle \mathcal T := \{ (k \mod p, k \mod q) | k=1,2,\dots, \textstyle(\frac{pq-1}{2}) \text{ such that } (k,pq)=1 \}

is another set of representatives of cosets of {U}. Here, we invoke the Chinese Remainder Theorem which asserts that

\displaystyle ({\mathbb Z}/p{\mathbb Z})^*\times ({\mathbb Z}/q{\mathbb Z})^* \cong ({\mathbb Z}/pq{\mathbb Z})^* = \{ k \mod pq| \text{ with } (k,pq)=1\}

The product of {k}, modulo {p} is,

\frac{ (\prod_{i=1}^{p-1} i) . (\prod_{i=1}^{p-1} p+i) .\cdots . (\prod_{i=1}^{p-1} (\frac{q-1}{2}-1)p+i)(\prod_{i=1}^{\frac{p-1}{2}} \frac{q-1}{2}p+i)}{q.2q.\cdots.\frac{p-1}{2}q}
\equiv  \frac{ ((p-1)!)^{\frac{q-1}{2}} }{ q^{\frac{p-1}{2}} } (\mod p)
\equiv  \frac{ ((p-1)!)^{\frac{q-1}{2}} q^{\frac{p-1}{2}} }{ q^{p-1} } (\mod p)
\equiv \frac{ ((p-1)!)^{\frac{q-1}{2}} (\frac{q}{p}) }{1} (\mod p),

where the first step is justified after observing that {\frac{p-1}{2}q} (respectively, {\frac{q-1}{2}p}) is the highest multiple of {q} (resp. {p}) which is less than {\frac{pq-1}{2}} and the last step follows from Euler’s criterion and Fermat’s little theorem. Similarly, we have a similar expression for {k} modulo q and hence, {\pi} now becomes, \boxed{\pi = \Large\left( ((p-1)!)^{\frac{q-1}{2}} \large\left(\frac{q}{p} \right) , ((q-1)!)^{\frac{p-1}{2}} \large\left(\frac{p}{q} \right) \right) U}

Comparing the above two expressions for {\pi} gives,

\displaystyle \large\left(1,(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\right)U = \large\left( \large\left(\frac{q}{p}\right), \large\left(\frac{p}{q}\right) \right) U

and hence, the reciprocity law,
\displaystyle \large\left(\frac{q}{p}\right) = \large\left(\frac{p}{q}\right) (-1)^{\frac{p-1}{2}\frac{q-1}{2}}