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.
Best Answer
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.