# $-3$ is a quadratic residue iff $p \equiv 1 \pmod 3$ [closed]

So this is the question: Let $p$ be an odd prime, prove that $-3$ is a quadratic residue modulo $p$ iff $p \equiv 1 \pmod 3$.

My idea was: $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\cdot \left(\frac{3}{p}\right)$$

also: $$\left(\frac{-3}{p}\right)= (-3)^a$$ when $a$ stands for $\frac{p-1}{2}$.

No idea how to continue... I would appreciate any help. Thanks!

## closed as off-topic by anomaly, Xander Henderson, Taroccoesbrocco, Brahadeesh, José Carlos SantosAug 22 '18 at 14:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – anomaly, Xander Henderson, Taroccoesbrocco, Brahadeesh, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

• That isn't an attempt to solve the problem; you just wrote out one of the definitions of $(\cdot/p)$. Use quadratic reciprocity. – anomaly Aug 21 '18 at 16:05

Your idea is right! But note that

$$\left (\frac{-3}{p}\right)=1\iff p\equiv_61$$

is a stronger and better condition than $$p\equiv_3 1$$, why? Look at all the numbers $$n\equiv_3 1$$ (that is, $$n=1+3k$$): $$1,\color{red}{4},7,\color{red}{10},13,\color{red}{16},19,\color{red}{22},\dots$$ Cool, now what? Notice that you alternate between even and odd numbers, so you can just discard the even numbers, because none of them are prime. This happens because adding an odd number of $$3$$'s to $$1$$ gives an even number. But no even number on the form $$1+3k$$ can be prime! Therefore you need to add an even number of $$3$$'s, that is, adding $$6$$. Therefore you should look at $$p\equiv_6 1$$ instead: $$1,7,13,19,\dots$$ Now, back to business!

You can write $$\left (\frac{-3}{p}\right)=\left (\frac{-1}{p}\right)\left (\frac{3}{p}\right)$$, now we know that $$\left (\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$$, so we only have to worry about what $$\left (\frac{3}{p}\right)$$ is.

For this, you can use a theorem known as quadratic reciprocity:

For $$p,q$$ distinct odd primes$$\left (\frac{p}{q}\right)\left (\frac{q}{p}\right)=(-1)^{\frac{q-1}{2}\frac{p-1}{2}}$$

Then you have to check two cases:

• $$\left (\frac{-1}{p}\right)=1$$ and $$\left (\frac{3}{p}\right)=1$$
• $$\left (\frac{-1}{p}\right)=-1$$ and $$\left (\frac{3}{p}\right)=-1$$

Can you take it from here?

(Edit)

I'll help you with the first case.

If we want $$\left (\frac{-1}{p}\right )=1$$, then $$(-1)^{\frac{p-1}{2}}=1$$, which means that $$\frac{p-1}{2}$$ must be even. This is the same as saying: $$\frac{p-1}{2}=2k\iff p=1+4k\iff p\equiv_4 1$$ From quadratic reciprocity we know that: $$\left( \frac{3}{p}\right) \left( \frac{p}{3}\right )=(-1)^{\frac{p-1}{2}}=1$$ Thus, $$\left( \frac{3}{p}\right)=\left( \frac{p}{3}\right)$$ (we can multiply and divide by $$\left( \frac{3}{p}\right)$$, since $$\left( \frac{3}{p}\right)=\pm 1$$)

Now we need to find out what $$\left( \frac{p}{3}\right)$$ is. Since we want $$\left( \frac{3}{p}\right)=1$$, we need to have $$\left( \frac{p}{3}\right)=1$$, that is, we need to find the primes $$p$$ such that $$p$$ is a quadratic residue modulo $$3$$. Let us look at the residues: \begin{align}1^2=1\\(-1)^2=1\end{align} So the only quadratic residue modulo $$3$$ is $$1$$, therefore we want $$p=1+3n\iff p\equiv_3 1$$

We now have two conditions on $$p$$:

• $$p\equiv_3 1$$
• $$p\equiv_4 1$$

This means that $$p\equiv_{12}1$$. Now you only have to check the second case! Combining both cases you should get: $$p\equiv_6 1$$ which is stronger than $$p\equiv_3 1$$.

• First of all thanks for the help, but if p is odd, cant i just ignore the second case? because (p-1)/2 would be even, so $(\frac{-3}{p})$= $(\frac{3}{p})$=1 or am i wrong? and after i finish proving it, how can i conclude that p=1 (mod 3)? im sorry if my question sound stupid, but i just didnt understand that subject at all.. – LonelyStudent Aug 21 '18 at 13:58
• @LonelyStudent Not a stupid question, number theory is hard, and we have all struggled with it some time! $p$ is a prime, so $p$ is always odd unless $p=2$. But $\frac{p-1}{2}$ is not always even, for instance, $\frac{19-1}{2}=9$. I will expand my answer and help you some more. – cansomeonehelpmeout Aug 21 '18 at 14:02

The idea to use $\left(\dfrac{-1}p\right)$ and $\left(\dfrac3p\right)$ to calculate $\left(\dfrac{-3}p\right)$ is a natural one...

But, IMHO it works BETTER if you go the opposite direction, and calculate $\left(\dfrac3p\right)$ using the other two!!

This is because $-3$ happens to be the discriminant of the polynomial $$\Phi_3(x)=x^2+x+1.$$ And, coincidentally, the presence of zeros of $\Phi_3$ modulo a prime $p$ can be decided by other means. Namely, we have the factorization $\Phi_3(x)(x-1)=x^3-1$. Implying that modulo $p>3$ the integer $a$ is a zero of $\Phi_3$ if and only if $a\not\equiv1\pmod p$ and $a^3\equiv1\pmod p$. In other words, $a$ is a zero if and only if it has order three in the group $\Bbb{Z}_p^*$. This group is cyclic of order $p-1$ (recall the existence of primitive roots modulo $p$), so, by Lagrange, such numbers $a$ exist if and only if $3\mid(p-1)$.

OTOH, by quadratic formula, $\Phi_3(x)$ has zeros modulo $p$ if and only if the discriminant $-3$ is a quadratic residue.

It follows that $\left(\dfrac{-3}p\right)=1$ if and only if $p\equiv1\pmod3$.

• Marking this CW because I am positive that this is a dupe. I need to commute next, so can search for one only later. – Jyrki Lahtonen Aug 22 '18 at 6:34