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

Barring mistakes, thanks.

  • $\begingroup$ P.S. [] is the floor function. $\endgroup$ – awllower Mar 27 '13 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.