There is a less obvious way to compute the Legendre symbol. This method allows us to easily evaluate $\left(\frac{2}{p}\right)$, among other things. Before stating the method formally, we demonstrate it with an example.

Let $p=17$, and $a=7$. There are $16$ nonzero elements $\{\mathrm{1,...,16}\}$. Consider the first half $\{\mathrm{1,...,8}\}$ and multiply them all by $7$ to get $7,14,4,11,1\mathrm{,8},15,5$. As integers, let us count the number of them that are greater than $p/2$ (that is, $9$ or higher).

Note: even though there is no way to define inequalities modulo $p$, we can view elements of ${\mathbb{Z}}_p$ as integers in $\{0,...,p-1\}$ and look at sizes there, though it is not yet clear why we want to do this.

$14,11$ and $15$ are the only ones in the set that are greater than $p/2$, so there are exactly $3$ of them. Then Gauss' Lemma states that if we take this $3$ and raise $-1$ to this power, then we have $\left(\frac{a}{p}\right)$, that is:

Theorem: Let $p$ be an odd prime, $q$ be an integer coprime to $p$. Consider the set $\{q,2q,...,q(p-1)/2\}$ and view each member is an integer in $\{0,...,p-1\}$. Let $u$ be the number of members in this set that are greater than $p/2$. Then

Proof: Let $b_1,...,b_t$ be the members of the set less than $p/2$, and $c_1,...,c_u$ be the members greater than $p/2$. Then $u+t=(p-1)/2$. Consider the sequence

Each of these are distinct: clearly $b_i\ne b_j$ and $c_i\ne c_j$ whenever $i\ne j$ (since $q$ is invertible), and if $b_i=p-c_j$, then let $b_i=rq,c_j=sq$. Then $r+s=0$, which is a contradiction since

Hence they must be precisely the numbers $1,...,(p-1)/2$ in some order, thus

Dividing both sides by $((p-1)/2))!$ completes the proof.$\blacksquare$

For example, let $p$ be an odd prime and take $q=2$. Consider the sequence $2,2\times \mathrm{2,...,2}(p-1)/2$. Note these are positive least residues. Now $p=8x+y$ for some integer $x$ and $y\in \{\mathrm{1,3,5,7}\}$. By considering each case we see that the number of elements greater than $p/2$ is even when $p=1,7(mod8)$ and odd when $p=3,5(mod8)$. We can restate this as follows.

Theorem: Let $p$ be an odd prime.

Proof: See the last paragraph, and note that $(p^2-1)/8$ is even when $p=\pm 1(mod8)$ and odd otherwise. Similarly for $\lfloor (p+1)/4\rfloor$. $\blacksquare$

Example: By Gauss' Lemma, $\left(\frac{3}{p}\right)=1$ if $p=\pm 1(mod12)$ and $-1$ otherwise ($p=\pm 5(mod12)$). Combining this with the above result for $-1(modp)$ we have $\left(\frac{-3}{p}\right)=1$ if $p=1(mod6)$ and $-1$ otherwise ($p=-1(mod6)$).

Theorem: Let $p$ be an odd prime and $q$ be some integer coprime to $p$. Let $m=\lfloor q/p\rfloor +\lfloor 2q/p\rfloor +...+\lfloor ((p-1)/2)q/p\rfloor$.

Then $m=u+(q-1)mod2$, where as in Gauss' Lemma, $u$ is the number of elements of $\{q,2q,...,q(p-1)/2\}$ which have a residue greater than $p/2$. In particular when $q$ is odd, $m=umod2$.

Proof: For each $i=1,...,(p-1)/2$, the equation $iq=p\lfloor iq/p\rfloor +r_i$ holds for some $0<r_i<p$. Reading the proof of Gauss' Lemma, we see these are preceisely the $b_i$ and $c_i$.

Then summing these equations gives

Since $p$ is odd, we have $m=u+q-1mod2$. $\blacksquare$