# Find p primes odds for Legendre symbol $(-3|p)=+1$ or $(-3|p)=-1$

First time calculating this and I apologize if I result a little bit confused; so I want to find p primes odds for Legendre symbol $$(-3|p)=+1$$ or $$(-3|p)=-1$$.

I know from Legendre's original definition that $$(-3)^{{p-1} \over {2}}=\pm 1$$ and that, to be this Legendre symbol valid, must be $$-3\not |p$$, so $$p\not=3$$ right?

If $$(-3|p)=+1$$ so $$-3$$ must be a quadratic residue $$\mod p$$ (in Gauss notation $$-3Rp$$).

Is this equivalent to find $$p$$ : $$q$$ be a square and $$q \equiv -3 \mod p$$, trying $$q = 1,4,9,16,15...$$ and solving by trying p?

• $\frac{1+\sqrt{-3}}{2} = \zeta$ satisfies $\zeta^3 = 1,\zeta \ne 1$ thus (for $p \ne 2$) $\sqrt{-3} \in \mathbb{F}_p$ iff $\zeta \in \mathbb{F}_p$ which is easy to tell (since $\mathbb{F}_p^\times$ is cyclic) – reuns Nov 28 '18 at 10:12
• @reuns thanks, and I apologize but I'm novice and I don't know yet what ζ means in this particular context, so I can't really grasp the meaning of the answer. Can you provide some detail in order for me to understand? – Alessar Nov 28 '18 at 10:30
• Because $3 | 13-1$ there is a $\zeta\bmod 13$ satisfying $\zeta^3 \equiv 1 \bmod 13,\zeta \not \equiv 1 \bmod 13$ and hence $(2\zeta-1)^2 \equiv -3 \bmod 13$. – reuns Nov 28 '18 at 11:08
• $(2 \zeta -1)^2 \equiv -3 (\mod 13)$ comes from a particular theorem? The first part of the explanation is clear – Alessar Nov 28 '18 at 14:37

If you work out that $$\left(\frac{-1}{p}\right)=1$$ when $$p\equiv 1\pmod{4}$$ and $$\left(\frac{3}{p}\right) =1$$ when $$p\equiv \pm 1 \pmod{12},$$ then the multiplicativity gives you that $$\left(\frac{-3}{p}\right)=1$$ when $$p\equiv 1 \pmod{12}.$$ One continues doing cases. If $$p\equiv -1 \pmod{12}$$ then $$p\equiv 3 \pmod{4}$$ so one has $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = (-1)(-1)=1.$$ Etc.
To work out $$\left(\frac{3}{p}\right)$$ we use quadratic reciprocity. If $$p$$ is prime and not $$3$$, then it is congruent to one of $$1, 5, 7, 11 \pmod{12}$$. Say $$p\equiv 5 \pmod{12}$$ then $$\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right) =\left(\frac{2}{3}\right) = -1.$$ Etc.
• $(3|p)=1$ when $p \equiv \pm 1 (\mod 12)$ (this is a definition or can be calculated directly?) is because if we take $p = 13$ the condition is met; but now we are saying that $(3|13)=1$. According to the definition of quadratic residue, exist a number that is a square $x^2 = 3 (\mod 13)$. In this case, that number must be : $13 |(x^2 -3)$ for some $x \in (1,2,3,...12)$, and this is verified for the subset $(4,9)$. Only after this is assured we can work on the QR on $(3|p)$, or other conditions must be met? – Alessar Nov 28 '18 at 14:30
• My last paragraph is the calculation for this. Since $13\equiv 1 \pmod{4}$ we have $(3|13) = (13|3) = (1|3)=1.$ – B. Goddard Nov 28 '18 at 14:36
• $(3|13)=(13|3)=(1|3)=1$ here is thanks to the fact that 3 and 13 are coprime that we can "invert" the Legendre symbol? And I know, I'm repeating myself and I apologize for this, is $(3|p)=1$ $p \equiv \pm 1(\mod 12)$ derivable or it's some kind of definition by theorem like $(-1|p)$? Thank you so much – Alessar Nov 28 '18 at 14:57
• My para IS the proof. The calculation works not just for $13$ but for any prime congruent to $1 \mod{12}$. Similar calculations work for the other classes modulo $12.$ – B. Goddard Nov 28 '18 at 14:59