Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Look up Thue's lemma – TheOscillator Feb 22 '14 at 13:06
up vote 11 down vote accepted

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.

share|cite|improve this answer
+1 Nice :) Fermat's Descent !! – r9m Feb 22 '14 at 13:23
Interesting. I've seen this method for Fermat's Christmas theorem but didn't expect it would work in general. – barto Feb 22 '14 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 '14 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. – barto Feb 23 '14 at 12:06


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

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

Consider the lattice defined by $L=\{(a,b)\in\mathbb{Z}^2|a\equiv ub\mod 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$ deined by $x^2+3y^2=n$, then the area of $E_n=\frac{\pi n}{\sqrt3}>1.8n$

Choose, $n=2.3p$, 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 \mod 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 \mod 3 \equiv 2 \mod 3$ contradiction !!

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

share|cite|improve this answer
How did you reach your very first equality?? – DonAntonio Feb 22 '14 at 14:17
@DonAntonio : Edited. – r9m Feb 22 '14 at 14:47
Thank you for your answer! giving this one to Jack – Eliran Koren Feb 22 '14 at 15:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.