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\]
.