# Computing the Legendre symbol $\bigl(\frac{3}{p}\bigr)$ using Gauss' Lemma

I would like to compute the Legendre symbol $\bigl(\frac{3}{p}\bigr)$, where $p > 3$ is a prime using Gauss' Lemma.

What I got so far is that $p$ can belong the following residue classes $\mod 12$, $[1], [11], [5]$, and $[7]$. I need to prove that in the first two cases, the Legendre symbol will evaluate to $1$ and in the last two cases it will evaluate to $-1$.

By Gauss' lemma, the Legendre symbol will be $(-1) ^\mu$, where $\mu$ is the number of elements of $3P = 3\{1, 2, \dots, (p-1)/2\}$ that are greater than $p/2$. However, I'm not exactly sure how to compute $\mu$, in each case ($p$ belong to different residue classes).

Thank you.

Since $3$ is small enough, we can explicitly compute the symbol by dint of the lemma indeed. Firstly, for $i\in \{[\frac{p-1}{6}]+1,\ldots,[\frac{p-1}{3}]\}$, the residue of $3i$ is certainly $>p/2$, the first set. Next, we look for $i$ such that $3i-p>\frac{p-1}{2}$, i.e. $i>\frac{p}{2}-\frac{1}{6}$. But $\frac{p}{2}-\frac{1}{6}>\frac{p-1}{2}$, so we need only compute the cardinality of the first set.
For $p=12k+1$, we find that the first interval has $2k$ elements, thus $(-1)^{\mu}=1$.
For $p=12k+11$, the cardinality is $(4k+3)-(2k+1)$, and $(-1)^{\mu}=1$.
If $p=12k+5$, then $\mu=(4k+1)-(2k)=2k+1$, and hence $(-1)^{\mu}=-1$.
If $p=12k+7$, then $\mu=(4k+2)-(2k+1)=2k+1$, and again $(-1)^{\mu}=-1$.
Conclusion: the Legendre symbol $\bigg (\dfrac{3}{p}\bigg)$ depends upon the parity of $[\frac{p-1}{3}]-[\frac{p-1}{6}]$.