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.

  • $\begingroup$ Yes, you are right. This is exactly the way, and for $p>2$ this way leads to quadratic reciprocity. $\endgroup$ – 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.

  • $\begingroup$ Dear Dietrich - +1. I am self-studying "I&R." If it is not an imposition, perhaps you would answer this question of mine: math.stackexchange.com/questions/211329/… Thanks, $\endgroup$ – user12802 Sep 1 '14 at 16:17

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.