Represent a prime number $p$ congruent to $1$ $\pmod{3}$ by a sum of a square and $3$ times a square

Question

I want to have a proof of the fact that each prime number is the sum of a square and three times a square (Euler).

Context

I read the answer to my former question about the number of points on an elliptic curve over $\mathbb F_p$, and in the answer $p=a^2+3b^2$ is used.

I have looked in a Latin version of Gauss' Disquisitiones but I'm not familiar with Latin. And there are a lot of relations between (prime) numbers and squares but I can't see which one will lead to a prove of this question.

Answer 1

You might like David A. Cox, Primes of The Form $x^2 + n y^2$

Anyway, if you believe in quadratic reciprocity, $(-3|p) = (p|3)$ which you are saying is $1.$ The equation uses $3 \equiv 3 \pmod 4.$ That is, $(-7|p) = (p|7),$ but don't replce the $7$ by $5.$ So we can solve $$ \beta^2 \equiv -12 \pmod p. $$ Now, if $\beta$ is odd, replce it by $b=p-\beta$ which is even, so now $$ b^2 \equiv -12 \pmod {4p}. $$ So $$ b^2 = -12 + 4pc $$ and $$ b^2 - 4pc = -12. $$ There is a (positive) binary quadratic form $$ \langle p,b,c \rangle $$ This reduces to $$ \langle 1,0,3 \rangle $$ The inverse of the 2 by 2 matrix that accomplishes the reduction gives a representation of $p=u^2 + 3 v^2,$ as the left column.

Answer 2

An elementary proof. The ideas here can quickly be generalized to other cases such as $a^2+b^2$ or $a^2+7b^2$. Let $a^2\equiv -3\pmod p$, $q=\lfloor \sqrt p\rfloor$ and consider all numbers $f(x,y)=ax-y$ with $0\leq x, y\leq q$.

There are $(q+1)^2$ such numbers. Since $(q+1)^2\gt p$, there are two numbers $f(x_1,y_1)$ and $f(x_2, y_2)$ that are congruent $\pmod p$. This means $f(x',y')=f(x_1-x_2, y_1-y_2)$ is divisible by $p$. The pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different solutions, so $(x,y)\neq(0,0)$.

Note that this implies that $(a|x_1-x_2|-|y_1-y_2|)(a|x_1-x_2|+|y_1-y_2|)$ is divisible by $p$, so there is a solution $(x,y)$ to $a^2x^2\equiv y^2\pmod p$ that respects $0\lt x,y\leq q$.

This shows a solution to $a^2x^2\equiv-3x^2\equiv y^2\pmod p$ with $0\lt x,y\leq q$. Using this to bound $3x^2+y^2$ gives $0 \lt 3x^2+y^2\leq 3p$. Let us consider three cases:

1. $3x^2+y^2=3p$. Since $3\mid y^2$ we know $9\mid y^2$. Diving by three gives a solution $u^2+3v^2=p$.

2. $3x^2+y^2=2p$. If this is true, $y$ and $x$ must have the same parity. If they were even, $4\mid 2p$, absurd - this shows they are odd. But if they are odd, $x^2\equiv y^2\equiv 1\pmod 8$, so $2p\equiv 4\pmod 8$. Since $p\equiv \pm 1\, \mathrm{or}\pm3\pmod 8$, this is also impossible.

3. $3x^2+y^2=p$. This case is easy, we have already gotten our desired representation.