## 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{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}

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

You have no rights to post comments