every prime in the form $3k+1$ can be written as the sum of a square and three times a square

Question

i'm having trouble getting started

every prime in the form $3k+1$ can be written as the sum of a square and three times a square. verify this for all appropriate primes less than $100$.

hints would be greatly appreciated!

Answer 1

Proof for all $p$'s.

Recall Thue's result.

Thue's Lemma: Let $n>1$ be an integer, and $a$ be an integer coprime to $n$. Then, there exists $x,y$ with $0<x,y<\sqrt{n}$ so that, $x\equiv ay\pmod{n}$.

In some sense, $(a,n)=1$ can be represented as a fraction, both of whose numerator and denominator is at most $\sqrt{n}$. The proof is available in many places, and I omit herein.

---

Now, we will apply Thue's lemma. The key point is the well-known fact, if $p\equiv 1\pmod{6}$ a prime, then $-3$ is a quadratic residue modulo $p$ (that is, there exists an $x$ so that $x^2\equiv -3\pmod{p}$). Now, let $0<x'<p$ be such a number, with $x'<p/2$ (note that, both $x'$ and $p-x'$ are so, and one of them is less than $p/2$, which, I assume to be $x'$ without any loss of generality).

Now, there is $0<a,b<\sqrt{p}$ with $a\equiv x'b\pmod{p}$. With this, $a^2+3b^2 \equiv b^2(x'^2+3)\equiv 0\pmod{p}$. It now suffices to show $a^2+3b^2=p$. Clearly, $a^2+3b^2<4p$, hence the possibilities are $a^2+3b^2=p,2p,3p$. If $a^2+3b^2=3p$, then in modulo $3$ we see that $3\mid a$. Letting $a=3a_1$, we have $3a_1^2+b^2=p$, and therefore, $p$ can be represented in the desired manner.

If $a^2+3b^2=2p$, then we observe that $a$ and $b$ are of same parity. In both cases, you may see that $a^2+3b^2\equiv 0\pmod{4}$, while $4\nmid 2p$, a contradiction.

We are done.