# Gauss Lemma for quadratic residues

For any odd prime $p$ let $a$ be an integer that is coprime to $p$. Consider the integers $$a,2a 3a,\ldots \frac{p-1}{2}a$$ and their least positive residues modulo $p$. Let $\nu$ be the number of these residues that are greater than $\frac{p}{2}$. Then Gauss Lemma says that $$\left(\frac{a}{p}\right)=(-1)^{\nu}$$ where $\left(\frac{a}{p}\right)$ is the Legendre symbol.

I can obviously apply this Lemma when $a$ and $p$ are known, but I can't use it for generic $a,p$. For example, how can I use Gauss Lemma to find all odd primes $p\neq 3$ such that $3$ is a square modulo $p$, i.e. $\left(\frac{3}{p}\right)=1$, i.e. $\nu$ is even?

Note: I want to use Gauss Lemma, I already can find such $p$ using quadratic reciprocity law.

$\textbf{EDIT:}$ I can solve the problem with $2$ in place of $3$. Indeed, let $$S:=\{-\frac{p-1}{2},\ldots,-1,1,\ldots,\frac{p-1}{2}\}$$ be a set of representatives of integers modulo $p$, call $S_{-}$ the subset of negative integers in $S$, $S_{+}$ the set of positive. Then $\nu$ is precisely

$$\nu=\#\{n\in S_{+}: 2n\in S_{-}\}$$ We can consider variuos cases, namely $p=1\pmod{4}$ and $p=3\pmod{4}$ to conclude that $2$ is a square modulo $p$ iff $p=\pm 1\pmod{8}$. I would like to do something similar for $3$, but it seems more difficult.

• Yes, you are right. This is exactly the way, and for $p>2$ this way leads to quadratic reciprocity. – Dietrich Burde Sep 19 '13 at 20:40

The Gauß Lemma is an extremely powerful tool, and we can prove quadratic reciprocity with it (as it is done in chapter $5$, §2 in Ireland and Rosen). As you already have said, with the reciprocity law we can, for an arbitrary integer $a$ say, for what primes $p$ this $a$ is a quadratic residue modulo $p$. So it seems to me that the natural way to use Gauß lemma here really is the quadratic reciprocity law.