Let $p$ be prime and $(\frac{-3}p)=1$, where $(\frac{-3}p)$ is Legendre symbol. Prove that $p$ is of the form $p=a^2+3b^2$.

My progress:

$(\frac{-3}p)=1 \Rightarrow$ $(\frac{-3}p)=(\frac{-1}p)(\frac{3}p)=(-1)^{\frac{p-1}2}(-1)^{\lfloor\frac{p+1}6\rfloor}=1 \Rightarrow$ $\frac{p-1}2+\lfloor\frac{p+1}6\rfloor=2k$
I'm stuck here. This is probably not the way to prove that.

Also tried this way:
$(\frac{-3}p)=1$, thus $-3\equiv x^2\pmod{p} \Rightarrow$ $p|x^2+3 \Rightarrow$ $x^2+3=p\cdot k$
stuck here too.

Any help would be appreciated.

  • $\begingroup$ Look up Thue's lemma $\endgroup$ – TheOscillator Feb 22 '14 at 13:06

First part: $$\left(\frac{-3}{p}\right)=1 \text{ if and only if }\; p\equiv{1}\!\!\!\!\pmod{3}.\tag{1}$$ This can be achieved through the Gauss quadratic reciprocity theorem in the most general form, or through the following lines. If $p=3k+1$, by the Cauchy theorem for groups there is an order-3 element in $\mathbb{F}_p^*$, say $\omega$; from $\omega^3=1$ follows $\omega^2+\omega+1\equiv 0\pmod{p}$, hence: $$(2\omega+1)^2 = 4\omega^2+4\omega+1 = 4(\omega^2+\omega+1)-3 = -3,$$ and $-3$ is a quadratic residue $\pmod{p}$. On the other hand, if $-3$ is the square of something $\pmod{p}$, say $-3\equiv a^2\pmod{p}$, then: $$\left(\frac{a-1}{2}\right)^3\equiv\frac{1}{8}(a^3-3a^2+3a-1)\equiv\frac{1}{8}\cdot 8\equiv{1},$$ and $\frac{a-1}{2}$ is an order-3 element in $\mathbb{F}_{p}^*$. From the Lagrange theorem for groups it follows that $3|(p-1)$.

Second part: $$\text{If }p\equiv 1\pmod{3},\qquad p=a^2+3b^2.\tag{2}$$ Since by the first part we know that $-3$ is a quadratic residue $\pmod{p}$, there exists an integer number $c\in[0,p/2]$ such that: $$ c^2+3\cdot 1^2 = k\cdot p.\tag{3}$$ The trick is now to set a "finite descent" in order to have $k=1$. Let $d$ the least positive integer such that $c\equiv d\pmod{k}$. Regarding $(3)$ mod $k$, we have: $$ d^2+3\cdot 1^2 = k\cdot k_1.\tag{4}$$ Since the generalized Lagrange identity states: $$(A^2+3B^2)(C^2+3D^2)=(AC+3BD)^2 + 3(BC-AD)^2,\tag{5}$$ by multiplying $(3)$ and $(4)$ we get: $$ (cd+3)^2 + 3(c-d)^2 = k^2 pk_1.$$ Since $cd+3\equiv c^2+3\equiv 0\pmod{k}$ and $c\equiv d\pmod{k}$, we can rewrite the last line in the following form: $$ \left(\frac{cd+3}{k}\right)^2+3\left(\frac{c-d}{k}\right)^2 = k_1\cdot p.\tag{6}$$ Now a careful analysis of the steps involved in the algorithm reveals that $k_1<k$, so the descent is able to reach $k_i=1$, or: $$ p = a^2 + 3b^2$$ as wanted.

| cite | improve this answer | |
  • $\begingroup$ Interesting. I've seen this method for Fermat's Christmas theorem but didn't expect it would work in general. $\endgroup$ – Bart Michels Feb 22 '14 at 15:04
  • 4
    $\begingroup$ @barto: A similar proof using descent can be used to prove $a^2+2b^2=p$ iff $p=2$ or $p\equiv 1,3\pmod{8}$. $a^2+5b^2=p$ iff $p\equiv 1,9\pmod{20}$ and $a^2+5b^2=2p$ iff $p\equiv 3,7\pmod{20}$ are similar results. :) $\endgroup$ – r9m Feb 22 '14 at 15:31
  • 1
    $\begingroup$ Yes, that's what I was thinking. It also works for proving that $p=4k+3$ is the sum of $4$ squares. I guess it won't work for sums of $3$ squares because there is no nice symmetric identity for products of sums of $3$ squares. $\endgroup$ – Bart Michels Feb 23 '14 at 12:06
  • $\begingroup$ Hi, if you don't mind: What does $\left(\frac{-3}{p}\right)=1$ mean? Surely it's not just a fraction. $\endgroup$ – Ovi May 28 '17 at 17:20
  • 1
    $\begingroup$ @Ovi: that is a Legendre symbol. $\left(\frac{-3}{p}\right)=1$ means that $-3$ is a quadratic residue $\pmod{p}$. $\endgroup$ – Jack D'Aurizio May 28 '17 at 17:21

$(\frac{p}{3})=(\frac{-3}{p})(\frac{p}{3})=(\frac{-1}{p})(\frac{3}{p})(\frac{p}{3})=(-1)^{\frac{p-1}{2}}(\frac{3}{p})(\frac{p}{3})=(-1)^{\frac{p-1}{2}}(-1)^{\frac{p-1}{2}\frac{3-1}{2}} = 1$

Hence,$(\frac{-3}{p})=1$ iff, $p\equiv1\mod3$.

Since, there is $u \in \mathbb{Z}$ such that, $-3\equiv u^2\pmod{p}$

Consider the lattice defined by $L=\{(a,b)\in\mathbb{Z}^2\, : \,a\equiv ub\pmod p\}$ generated by $(u,1)$ and $(0,p)$. $L$ has index $p$ in $\mathbb{Z}^2$, and area of its fundamental domain is $p$. Now, consider an ellipse $E_n$ defined by $x^2+3y^2=n$, then the area of $E_n=\frac{\pi n}{\sqrt3}>1.8n$

Choose, $n=2.3 p$, then Area of $E_{n}>4p$ and $E_n\cap L$ has a non zero point $(a,b)$.

Now, $a^2+3b^2\equiv(ub)^2+3b^2\equiv b^2(u^2+3)\equiv0 \pmod p$.

Since, $(a,b)\in E_n \implies a^2+3b^2<2.3p$ we have $a^2+3b^2=p,2p$.

But, $a^2+3b^2=2p \implies a^2\equiv 2p \pmod 3 \equiv 2 \pmod 3$ contradiction !!

Therefore, $a^2+3b^2=p$.

| cite | improve this answer | |
  • $\begingroup$ How did you reach your very first equality?? $\endgroup$ – DonAntonio Feb 22 '14 at 14:17
  • $\begingroup$ @DonAntonio : Edited. $\endgroup$ – r9m Feb 22 '14 at 14:47
  • 1
    $\begingroup$ Thank you for your answer! giving this one to Jack $\endgroup$ – Eliran Koren Feb 22 '14 at 15:24
  • 1
    $\begingroup$ Did you use Gauss quadratic reciprocity at first eqaulity? Right derivation is $\left( {{3} \over {p}} \right) \left( {{p} \over {3}} \right) = (-1)^{ {{p-1} \over {2}} {{3-1} \over {2}} } = 1$, not $\left( {{3} \over {p}} \right) \left( {{p} \over {3}} \right) = (-1)^{ {{p-1} \over {2}} } (-1)^{ {{3-1} \over {2}} } = -1$. $\endgroup$ – Ryu Dae Sick Dec 31 '18 at 5:21
  • 1
    $\begingroup$ In fact, $p \equiv 1 \pmod{3} $, $1^2 \equiv p \pmod{3} \implies \left( {{p} \over {3}} \right) = 1$. $\endgroup$ – Ryu Dae Sick Dec 31 '18 at 5:25

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.