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?

  • 1
    $\begingroup$ $\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) $\endgroup$ – reuns Nov 28 '18 at 10:12
  • $\begingroup$ @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? $\endgroup$ – Alessar Nov 28 '18 at 10:30
  • 1
    $\begingroup$ 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$. $\endgroup$ – reuns Nov 28 '18 at 11:08
  • $\begingroup$ $(2 \zeta -1)^2 \equiv -3 (\mod 13)$ comes from a particular theorem? The first part of the explanation is clear $\endgroup$ – 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.

  • $\begingroup$ $(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? $\endgroup$ – Alessar Nov 28 '18 at 14:30
  • 1
    $\begingroup$ My last paragraph is the calculation for this. Since $13\equiv 1 \pmod{4}$ we have $(3|13) = (13|3) = (1|3)=1.$ $\endgroup$ – B. Goddard Nov 28 '18 at 14:36
  • $\begingroup$ $ (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 $\endgroup$ – Alessar Nov 28 '18 at 14:57
  • 1
    $\begingroup$ 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.$ $\endgroup$ – B. Goddard Nov 28 '18 at 14:59
  • $\begingroup$ Thanks for your patience and for your explanations $\endgroup$ – Alessar Nov 28 '18 at 17:26

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.