Defintion (9-2) (Least Residue)
If \(n\) is any integer, then the least residue of \(n\) modulo \(m\) is the integer \(x\) in the interval \((-m/2, m/2]\) such that \(n \equiv x \pmod{m}\). We denote the least residue of \(n\) modulo \(m\) by \(LR_{m}(n)\).
Example: Take \(m = 11\). Then the interval \((-5.5, 5.5]\) contains
$$
\begin{align}
\{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5\}
\end{align}
$$
Then for any integer \(n\), the least residue modulo \(11\) is an integer from the list above. For example, even though \(21 \bmod{11} = 10\), we have \(LR_{11}(21) = -1\).
Defintion (9-3)
We define \(sgn(x)\) (read signum of \(x\) by
$$
\begin{align}
sgn(x) =
\begin{cases}
+1, & \text{if } x > 0, \\
0, & \text{if } x = 0, \\
-1, & \text{if } x < 1.
\end{cases}
\end{align}
$$
In general, we note that \(x = |x| sgn(x)\).
Theorem 9-3 (Gauss's Lemma)
Let \(\gcd(m,p) = 1\) where \(p\) is an odd prime, and let \(\mu\) be the number of integers in the set
$$
\begin{align}
\left\{m, 2m, \ldots, \frac{1}{2}(p-1)m\right\}
\end{align}
$$
whose least residues modulo \(p\) are negative. Then
$$
\begin{align}
\left(\frac{m}{p}\right) = (-1)^{\mu}
\end{align}
$$
Proof
First note that none of the integers \(m,2m,\ldots,\frac{1}{2}(p-1)m\) is divisible by \(p\). By definition (9-2), we know that
$$
\begin{align}
nm \equiv LR_{p}(nm) \pmod{p} \quad \quad \quad \quad (1)
\end{align}
$$
We also know that by definition (9-3) that
$$
\begin{align}
LR_{p}(nm) = sgn(LR_{p}(nm)) \cdot |LR_{p}(nm)| \quad \quad \quad \quad (2)
\end{align}
$$
Hence by (1) and (2),
$$
\begin{align}
nm \equiv sgn(LR_{p}(nm)) \cdot |LR_{p}(nm)|
\end{align}
$$
Observe now that by definition of the least residue
$$
\begin{align}
0 < |LR_{p}(nm)| < p/2
\end{align}
$$
Now suppose that \(n=1\), then
$$
\begin{align}
m \equiv sgn(LR_{p}(m)) \cdot |LR_p(m)| \pmod{p}
\end{align}
$$
If \(n = 2\), then
$$
\begin{align}
2m \equiv sgn(LR_{p}(2m)) \cdot |LR_p(2m)| \pmod{p}
\end{align}
$$
and so on. Consequently
$$
\begin{align}
m(2m)(3m)\ldots ((p-1)m/2) \equiv sgn(LR_{p}(m)) \cdot sgn(LR_{p}(2m)) \cdots sgn(LR_{p}((p-1)m/2)) \\ \cdot |LR_p(m)| \cdot |LR_p(2m)| \cdots |LR_p((p-1)m/2)| \pmod{p}
\end{align}
$$
But note here that the left hand side consists of \(1 \cdot 2 \cdot 3 \cdot \cdots (p-1)/2 = ((p-1)/2)!\) and what’s left is exactly \(m^{(p-1)/2}\). Hence
$$
\begin{align}
((p-1)/2)! \cdot m^{(p-1)/2} \equiv sgn(LR_{p}(m)) \cdot sgn(LR_{p}(2m)) \cdots sgn(LR_{p}((p-1)m/2)) \\ \cdot |LR_p(m)| \cdot |LR_p(2m)| \cdots |LR_p((p-1)m/2)| \pmod{p} \quad \quad (3)
\end{align}
$$
What about the right hand side? Recall that \(n\) itself goes from \(1\) to \(\frac{p-1}{2}\). Thus, we claim the following elements
$$
\begin{align}
\{ |LR_p(m)|, |LR_p(2m)|, \cdots, |LR_p((p-1)m/2)| \} \quad \quad \quad (4)
\end{align}
$$
are distinct.
Why? Suppose not, then
$$
\begin{align}
|LR_p(mn_1)| = |LR_p(mn_2)|
\end{align}
$$
This implies that
$$
\begin{align}
mn_1 = \pm mn_2 \pmod{p}
\end{align}
$$
But recall that \(\gcd(p,m) = 1\). Hence, we can cancel \(m\) to get
$$
\begin{align}
n_1 =\pm n_2 \pmod{p}
\end{align}
$$
But \(n_1\) and \(n_2\) are between \(1\) and \((p-1)/2\) by construction. Hence \(n_1 = n_2\). This is a contradiction. Thus, the elements are distinct.
Since the elements in (4) are distincts, then
$$
\begin{align}
|LR_p(m)| \cdot |LR_p(2m)| \cdots |LR_p((p-1)m/2)| \equiv 1 \cdot 2 \cdot 3 \cdots (p-1)/2 \equiv ((p-1)/2)! \pmod{p}
\end{align}
$$
Hence (3) becomes
$$
\begin{align}
((p-1)/2)! \cdot m^{(p-1)/2} \equiv sgn(LR_{p}(m)) \cdot sgn(LR_{p}(2m)) \cdots sgn(LR_{p}((p-1)m/2)) \cdot ((p-1)/2)!
\end{align}
$$
Note now that \(((p-1)/2)!\) is coprime to \(p\) since every number in the product \(((p-1)/2)!\) is less than \((p-1)/2\) and recall that if a prime divides a product then \(p\) must at least divide one of the factors. But that’s impossible since they are all less than \(p\). Hence \(\gcd(((p-1)/2)!, p) = 1\). Therefore, we can cancel \(((p-1)/2)!\) from both sides as follows
$$
\begin{align}
m^{(p-1)/2} \equiv sgn(LR_{p}(m)) \cdot sgn(LR_{p}(2m)) \cdots sgn(LR_{p}((p-1)m/2))
\end{align}
$$
By Theorem \(9-2\), we know that \(\left(\frac{m}{p}\right) \equiv m^{\frac{p-1}{2}}\) (Proof Link?). Hence
$$
\begin{align}
\left(\frac{m}{p}\right) \equiv sgn(LR_{p}(m)) \cdot sgn(LR_{p}(2m)) \cdots sgn(LR_{p}((p-1)m/2))
\end{align}
$$
Now, let \(\mu\) be the number of negative least residues among
$$
\begin{align}
\{ LR_p(m), LR_p(2m), \cdots, LR_p((p-1)m/2) \}
\end{align}
$$
Then
$$
\begin{align}
\left(\frac{m}{p}\right) \equiv (-1)^{\mu} \pmod{p}. \quad \blacksquare
\end{align}
$$
References
- Number Theory by Georege Andrews