<s>[INST] 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.
 [/INST] 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$.
</s>