# Primes congruent to $1$ modulo $6$ are of the form $3a^2+b^2$

I am asked to prove that primes of the form $6k+1$, where $k$ is an integer can be written as $3a^2 + b^2$, where $a$ and $b$ are integers by using the fact that $\textbf Z[\omega]$ is a UFD, where $\omega^2 + \omega + 1 = 0$. However, I cannot see any connection. How can one connect these two seemingly unrelated facts? Thanks in advance.

• Have you by a chance seen a proof that if $p\equiv 1\pmod 4$, then $p=a^2+b^2$? You can prove similarly that if $p\equiv 1\pmod 6$, then $p=a^2+ab+b^2$. From there it's not too hard to get $3a^2+b^2$. – Wojowu Mar 12 '18 at 19:52
• The argument will depend on how much you know. You want to think about the norm of the integers in that ring, and about which primes are quadratic residues mod $3$. – Ethan Bolker Mar 12 '18 at 19:52
• I know the norm, it is given by $a^2-ab+b^2$, but don't have any idea as to how to proceed. – Mrtired Mar 12 '18 at 19:54
• For another solution, see here, Exercise $0.14$. – Dietrich Burde Mar 12 '18 at 20:05
• This answer contains an elementary approach through Legendre symbols and Fermat's descent. – Jack D'Aurizio Mar 12 '18 at 20:17

Hint: The norm in this ring is $$N(a+b\omega) = (a+b\omega)(a+b\omega^2) = a^2 - ab + b^2 = \frac{(2a-b)^2 + 3b^2}{4}$$

The main work has been done here already:

Primes congruent to 1 mod 6

If $p \equiv 1 \pmod 6$ then $\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)(-1)^{\frac{p-1}{2}\frac{3-1}{2}} = \left(\frac{p}{3}\right)=1$ so $-3$ is a perfect square mod $p$.

Therefore there exists a solution to the equation $x^2 + 3 = 0$ in $\mathbb{F}_p$.

Since $\omega = \frac{1 + \sqrt{-3}}{2}$, the polynomial $x^2 + x + 1$ will also have a root in $\mathbb{F}_p$.

By the third isomorphism theorem we know $\mathbb{F}_p[x]/\langle x^2 + x + 1 \rangle \simeq \mathbb{Z}[x]/\langle p, x^2 + x + 1 \rangle \simeq \mathbb{Z}[\omega]/(p)$.

Since $x^2 + x + 1$ is not irreducible in $\mathbb{F}_p$, this means $\mathbb{F}_p[x]/\langle x^2 + x + 1 \rangle$ is not an integral domain, and therefore $\mathbb{Z}[\omega]/(p)$ is not an integral domain either.

Therefore $(p)$ is not a prime ideal in $\mathbb{Z}[\omega]$ and hence not maximal either, and since $\mathbb{Z}[\omega]$ is a Dedekind domain and a UFD (and hence a PID), this means $(p)$ is properly contained in some ideal $(a + b\omega) \neq (1)$ and so $p$ is divisible by the non-unit $a + b\omega$ and $p$ is not an irreducible element in $\mathbb{Z}[\omega]$.

Therefore there exists a nontrivial factorization $p = u(a + b\omega)(c + d\omega)$, where $u$ is a unit in $\mathbb{Z}[\omega]^*$ and $p^2 = N(p) = N(u)N(a+b\omega)N(c+d\omega)=\pm(a^2-ab+b^2)(c^2-cd+d^2)$. The nontrivial factorization means that neither factor is a unit and so $p = a^2-ab+b^2$ (note that the quadratic form is positive-definite so it cannot be $-p$).

If $a$ is even and $b$ is odd, then by symmetry we can permute $a$ and $b$. If $a$ is odd and $b$ is odd then let $a' = b$ and $b' = b - a$. We see that $a'^2 - a'b' + b'^2 = b^2 - b(b-a) + (b-a)^2 = b^2 - b^2 + ab + b^2 - 2ab + a^2 = a^2 - ab + b^2$ so $p = a'^2 - a'b' + b'^2$ where $b'$ is now even.

Hence w.l.o.g. we can assume $b$ is even and we can rewrite the expression as $p = \left(a-\frac{b}{2}\right)^2 + 3\left(\frac{b}{2}\right)^2$.

• It would have been better if you explicitly expressed completely the last part because it could not be correctly interpreted by some readers. – Piquito Mar 12 '18 at 22:50
• I realized I did not correctly prove that either $a$ or $b$ be must be even. – Tob Ernack Mar 12 '18 at 23:18
• This is obvious because if not $3a^2+b^2$ is even if both $a$ and $b$ are odd. – Piquito Mar 12 '18 at 23:27
• But what we've shown is that $p = a^2 - ab + b^2$. Parity considerations do not prevent $a$ and $b$ from being odd here. I must be missing something... We could try showing that all values of $a^2 - ab + b^2$ also occur as values of $a^2 + 3b^2$. – Tob Ernack Mar 12 '18 at 23:42
• I found a substitution that makes $b$ even while preserving the value, so it works. (I used the fact that if $a + b\omega$ divides $p$, then so does $-\omega(a + b\omega) = b + (b-a)\omega$). – Tob Ernack Mar 13 '18 at 0:03

What is $\omega$ anyway? By the fundamental theorem of algebra, it is one of two solutions to $x^2 + x + 1 = 0$. Probably $$\omega = -\frac{1}{2} + \frac{\sqrt{-3}}{2}.$$

The other solution is different only in the sign of the imaginary part. Then it's called the conjugate and denoted by an overline. Thus the conjugate of $\omega$ is $\overline \omega$.

And $$\omega \overline \omega = \frac{1}{4} + \frac{3}{4} = 1,$$ and more generally $$(a + b \omega) \overline{(a + b \omega)} = \frac{a^2}{4} + \frac{3b^2}{4}.$$

I hope this makes the connection more obvious.

Consider the order $\mathbb{Z}[\sqrt{-3}] \subset \mathbb{Z}[\omega]$. Then the norm $N$ on $\mathbb{Z}[\omega]$ restrict to $\mathbb{Z}[\sqrt{-3}]$ as $$N\left(a+b\sqrt{-3}\right) = a^2 + 3b^2$$ Let's prove that the images $N(\mathbb{Z}(\sqrt{-3})$ and $N(\mathbb{Z}[\omega])$ are equal. Indeed, one inclusion is obvious since $\mathbb{Z}[\sqrt{-3}] \subset \mathbb{Z}[\omega]$. In the other direction, suppose we have $x = N(\alpha)$ for $\alpha \in \mathbb{Z}[\omega]$. Write $$\alpha = a+b\omega$$ then at least one of the numbers $\alpha, \omega \alpha,\omega^2\alpha$ will be in $\mathbb{Z}[\sqrt{-3}]$: the coefficient at $\omega$ will be $b, a-b,a$ respectively, so one of them is even. Since $N(\alpha) = N(\omega \alpha) = N(\omega^2\alpha)$, we see that $x$ is also the norm of an element in $\mathbb{Z}[\sqrt{-3}]$, so the result follows.

This shows that an integer $n$ is of the form $a^2-ab+b^2$ if and only if it is of the form $a^2+3b^2$. The result follows from the other question, quoted already in the answer by Dietrich Burde.