If
\[p\]
is an odd prime then \[(a/p)=(-1)^{\alpha (a, \; p)}\]
where \[\alpha (a, \; p)= \sum_{k=1}^{(p-1)/2} int (\frac{ka}{p} )\]
Proof
Let
\[S= \{a, \; 2a, \; 3a,..., \; \frac{p-1}{2} \}\]
. Replace each element of \[S\]
by its least residue modulo \[p\]
and list the results in ascending order to give \[S'= \{ b_1, \; b_2, \; b_3,..., \; b_m, \; c_1, \; c_2,..., \; c_n \}\]
where \[b_m \lt \frac{p}{2} \lt c_1\]
. According to the The Division Algorithm Proof we can write \[ka = p \times int (\frac{ka}{p})+r\]
where \[r \in S'\]
. Let \[k\]
run from 1 to \[\frac{p-1}{2}\]
and adding up the resulting equations we get\[\sum_{k=1}^{(p-1)/2} ka = \sum_{k=1}^{(p-1)/2} p \times int (\frac{ka}{p}) + \sum_{i=1}^m b_i + \sum_{i=1}^n c_n\]
(1)From
\[S'\]
we can construct the set \[S''= \{b_1, \; b_2,..., \; b_m, \; p-c_1, \; p-c_2,..., \; p-c_n \} = \{1, \; 2,..., \frac{p-1}{2} \}\]
by reordering.Adding the elements of
\[S''\]
gives\[\sum_{k=1}^{(p-1)/2}k= \sum_{i=1}^mb_i+ \sum_{i=1}^n(p-c_i)=\sum_{i=1}^mb_i+mp - \sum_{i=1}^n c_i\]
(2)(1)-(2) gives
\[\sum_{k=1}^{(p-1)/2}ka - \sum_{k=1}^{(p-1)/2}k=\sum_{k=1}^{(p-1)/2} p \times int (\frac{ka}{p}) +2 \sum_{i=1}^n c_i-pn\]
We can write this as
\[(a-1) \sum_{k=1}^{(p-1)/2} =p \times \alpha (a, \; p) +2 \sum_{i=1}^n c_i-pn\]
Writing this equation modulo 2 we get
\[p \times \alpha (a, \; p)-pn=0 \; (mod \; 2)\]
.\[p\]
is odd so we can write \[p \times \alpha (a, \; p)=n \; (mod \; 2)\]
.Now use Gauss's Lemma for Congruences give
\[(a/p)=(-1)^{\alpha (a, \; p)}\]
.