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

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

My progress:

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

Also tried this way:
$$\left(\frac{-3}p\right)=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.

• Look up Thue's lemma Feb 22, 2014 at 13:06
• I hihgle recommend "Primes of the form $x^2+ny^2$" by David Cox for discussion of similar questions. Oct 9, 2022 at 7:24

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.

• Interesting. I've seen this method for Fermat's Christmas theorem but didn't expect it would work in general. Feb 22, 2014 at 15:04
• @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. :)
– r9m
Feb 22, 2014 at 15:31
• 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. Feb 23, 2014 at 12:06
• Hi, if you don't mind: What does $\left(\frac{-3}{p}\right)=1$ mean? Surely it's not just a fraction.
– Ovi
May 28, 2017 at 17:20
• @Ovi: that is a Legendre symbol. $\left(\frac{-3}{p}\right)=1$ means that $-3$ is a quadratic residue $\pmod{p}$. May 28, 2017 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$$.

• 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$. Dec 31, 2018 at 5:21
• In fact, $p \equiv 1 \pmod{3}$, $1^2 \equiv p \pmod{3} \implies \left( {{p} \over {3}} \right) = 1$. Dec 31, 2018 at 5:25
• May I ask you something? ..How to know $L$ is generated by $(0,p)$ and $(1,u)$ ? For example, let $a-ub=p$ and $(a,b)=m(u,1)+n(0,p)$ for some $m,n$. Then $a=mu, b=m+np$ so $-un=1$. This imply $u= \pm 1$. Also, how to know that the index is $p$? .
– hew
Dec 16, 2020 at 18:27

Let $$\omega\in\Bbb C$$ satisfy $$\omega^2+\omega+1$$. Then $$\Bbb Z[\omega]$$ is a UFD, since $$N(a+b\omega)=a^2-ab+b^2$$ defines an Euclidean norm.

Since $$\left(\frac{-3}{p}\right)=1$$, there is an $$s$$ such that $$p\mid s^2+3$$. Working over $$\Bbb Z[\omega]$$ we have $$p\mid (s+1+2\omega)(s+1+2\omega^2)$$ If $$p$$ is prime we would have both $$p\mid s+1$$ and $$p\mid 2$$. This is impossible, so $$p$$ cannot be prime. Therefore we must have $$p=\alpha\beta$$, where $$\alpha,\beta\in\Bbb Z[\omega]$$. Taking norms, we get $$p^2=N(p)=N(\alpha)N(\beta)$$ Since neither $$\alpha,\beta$$ are units, we have $$N(\alpha),N(\beta)\neq 1$$. This forces $$N(\alpha)=N(\beta)=p$$. Let $$\alpha=m+n\omega$$, then $$p=N(\alpha)=m^2-mn+n^2$$ Without loss of generality we may assume that $$n$$ is even, as $$p$$ is an odd prime. We can then write:

$$4p=4m^2-4mn+n^2+3n^2\\4p=(2m-n)^2+3n^2\\p=\left(m-\frac{n}{2}\right)^2+3\left(\frac{n}{2}\right)^2$$ Choose $$a=m-\frac{n}{2}$$ and $$b=\frac{n}{2}$$ and we get $$p=a^2+3b^2$$

• I don't know how to see the pairty of $n$ by considering modulo 2. Another way: Let $K=\mathbb{Q}[\omega]$. $Tr(p)=2p=2m+nTr(\omega)=2m-n$, so $n$ must be even.
– Doug
Jul 5, 2022 at 7:43