Gauss's Lemma for Congruences

Theorem (Gauss's Lemma)
Let  
\[p\]
  be an odd prime and let  
\[a \neq 0 \; (mod \; p)\]
  be an integer. Let  
\[S= \{ a, \; 2a,..., \; ( \frac{p-1}{2})a \}\]
. If  
\[m\]
  is the number of elements of  
\[S\]
  exceeding  
\[\frac{p}{2}\]
  then  
\[(a/p)=(-1)^n\]
  where  
\[(a/p)\]
  is a Legendre Symbol.
Proof
No two elements of  
\[S\]
  are congruent modulo  
\[p\]
  because if  
\[ra \equiv sa \; (mod \; p), \; r \gt s \gt 0\]
  then  
\[(r-s)a \equiv 0 \; (mod \; p) \rightarrow p| (r-s) \rightarrow r=s \; (mod \; p)\]
  but  
\[1 \le r, \; s \le p-1 \]
  so  
\[r=s\]
.
Let  
\[S'\]
  be the set obtained by replacing each element of  
\[S\]
  it its positive residue modulo  
\[p\]
. Put the elements of  
\[S'\]
  into ascending order to obtain  
\[S'= \{b_1, \; b_2,..., \; b_m, \; c_1, \; c_2,..., \; c_n \}\]
  where  
\[b_m \lt \frac{p}{2} \lt c_1\]
  and  
\[m_n= \frac{p-1}{2}\]
.
Let  
\[S''= \{b_1, \; b_2,..., \; b_m, \; p-c_1, \; p-c_2,..., \; p-c_n \}\]
. We have to show that  
\[S= \{ 1, \; 2,..., \; \frac{p-3}{2}, \; \frac{p-1}{2} \}\]
. The members of  
\[S''\]
  are certainly all positive, there are  
\[\frac{p-1}{2}\]
  of them, and the largest element is either  
\[b_m\]
  or  
\[p-c_1\]
, each less than  
\[\frac{p}{2}\]
. There are then  
\[\frac{p-1}{2}\]
  integers less than  
\[\frac{p}{2}\]
  and we need to show they are all distinct. The elements of  
\[b_1, \; b_2,..., \; b_m'\]
  are distinct, as are the elements  
\[p-c_1, \; p-c_2,..., \; p-c_n\]
. Suppose  
\[b_i = p-c_j\]
  for some  
\[i, \; j\]
. Then  
\[p=b_i+c_j \equiv ra+sa \; (mod \; p)\]
  for some integers  
\[1 \lt r, \; s \lt \frac{p-1}{2}\]
.
But  
\[p \equiv (r+s)a \; (mod \; p)\]
  and  
\[a \neq 0 \; (mod \; p)\]
  we must have  
\[r+s \equiv 0 \; (mod \; p)\]
  which is impossible since  
\[1 \lt r, \; s \lt \frac{p-1}{2} \rightarrow 2 \lt r+s \lt p-1\]
  hence  
\[S''= \{ 1, \; 2,..., \; \frac{p-1}{2} \}\]
.
Multiplying elements of  
\[S''\]
  together,
\[\begin{equation} \begin{aligned} ( \frac{p-1}{2} )! &= b_1b_2...b_m(p-c_1)(p-c_2)...(p-c_n) \\ &\equiv b_1b_2...b_m(-c_1)(-c_2)...(-c_n) \; (mod \; p) \\ &\equiv (-1)^nb_1b_2...b_mc_1c_2...c_n \; (mod \; p) \\ &\equiv (-1)^n a \times 2a \times ... \times \frac{p-1}{2} a \; (mod \; p) \\ &\equiv (-1)^n a^{\frac{p-1}{2}} ( \frac{p-1}{2} )! \; (mod \; p) \end{aligned} \end{equation}\]

\[gcd(p, \; ( \frac{p-1}{2})!)=1\]
  so the factor  
\[( \frac{p-1}{2})!\]
  may be cancelled to give  
\[1 \equiv (-1)^n a^{\frac{p-1}{2}} \; (mod \; p)\]
.
Now use Euler's Criterion,  
\[a^{\frac{p-1}{2}} \equiv (a/p) \; (mod \; p)\]
  and multiply by  
\[(-1)^n\]
  to obtain  
\[(a/p) \equiv (-1)^n\]
.

Add comment

Security code
Refresh