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}}$

Proof:

$\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}}$.
Similarly,
$\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}}$

$\blacksquare$