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.
 A: 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$.
A: 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. 
A: 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.
A: 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
