Vtyjkyuk

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-3pright) = left(frac-1pright)cdot left(frac3pright)$$

also:
$$left(frac-3pright)= (-3)^a$$
when $a$ stands for $fracp-12$.

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

Your idea is right! But note that

$$left (frac-3pright)=1iff pequiv_61$$

is a stronger and better condition than $pequiv_3 1$, why? Look at all the numbers $nequiv_3 1$ (that is, $n=1+3k$): $$1,colorred4,7,colorred10,13,colorred16,19,colorred22,dots$$ Cool, now what? Notice that you alternate between even and odd numbers, so you can just discard the even numbers. 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 $pequiv_6 1$ instead: $$1,7,13,19,dots$$ Now, back to business!

You can write $left (frac-3pright)=left (frac-1pright)left (frac3pright)$, now we know that $left (frac-1pright)=(-1)^fracp-12$, so we only have to worry about what $left (frac3pright)$ is.

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

For $p,q$ distinct odd primes$$left (fracpqright)left (fracqpright)=(-1)^fracq-12fracp-12$$

Then you have to check two cases:

• $left (frac-1pright)=1$ and $left (frac3pright)=1$


• $left (frac-1pright)=-1$ and $left (frac3pright)=-1$

Can you take it from here?

(Edit)

I'll help you with the first case.

If we want $left (frac-1pright )=1$, then $(-1)^fracp-12=1$, which means that $fracp-12$ must be even. This is the same as saying: $$fracp-12=2kiff p=1+4kiff pequiv_4 1$$ From quadratic reciprocity we know that: $$left( frac3pright) left( fracp3right )=(-1)^fracp-12=1$$ Thus, $$left( frac3pright)=left( fracp3right)$$ (we can multiply and divide by $left( frac3pright)$, since $left( frac3pright)=pm 1$)

Now we need to find out what $left( fracp3right)$ is. Since we want $left( frac3pright)=1$, we need to have $left( fracp3right)=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: $$beginalign1^2=1\(-1)^2=1endalign$$ So the only quadratic residue modulo $3$ is $1$, therefore we want $p=1+3niff pequiv_3 1$

We now have two conditions on $p$:

• $pequiv_3 1$


• $pequiv_4 1$

This means that $pequiv_121$. Now you only have to check the second case! Combining both cases you should get: $$pequiv_6 1$$ which is stronger than $pequiv_3 1$.

The idea to use $left(dfrac-1pright)$ and $left(dfrac3pright)$ to calculate $left(dfrac-3pright)$ is a natural one...

But, IMHO it works BETTER if you go the opposite direction, and calculate $left(dfrac3pright)$ 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 $anotequiv1pmod p$ and $a^3equiv1pmod p$. In other words, $a$ is a zero if and only if it has order three in the group $BbbZ_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 $3mid(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-3pright)=1$ if and only if $pequiv1pmod3$.