Factoring rational primes over the Eisenstein integers - when can a prime be written as $j^2+3k^2$?

There is a demon in charge of obfuscating the mathematics education of humans, sometimes called Apasmara or Maluyakan, and Betsy DeVos is his prophet.

When human mathematicians started discovering facts about quadratic rings a few centuries ago, my colleague demon made a decision made that when $d \equiv 1 \pmod 4$, humans should be guided to always figure in a number $$\theta = \frac{1 + \sqrt d}{2}$$ and use that number for all calculations in $\mathcal O_{\mathbb Q(\sqrt d)}$ whether it makes sense to do so or not. Especially when the latter is the case. Deliciously diabolical!

This often prevents a human math student from realizing that to factor $p$, it might be easier to find $4p = a^2 - db^2$. In the case of $d = -3$ for $\mathbb Z[\omega]$ (where we use $\omega$ instead of $\theta$ just to be arbitrary), this sometimes means figuring out if $a^2 + 3b^2 = 4p$. If $p \equiv 2 \pmod 3$, then $4p \equiv 2 \pmod 3$, but $a^2$ is never $2 \pmod 3$ and $3b^2 \equiv 0 \pmod 3$ always. But if $p \equiv 1 \pmod 3$, then... I better leave it at that, don't want to cross Mulayakan.

So for example $(5 - \sqrt{-3})(5 + \sqrt{-3}) = 28$ and $$\left(\frac{5 - \sqrt{-3}}{2}\right) \left(\frac{5 + \sqrt{-3}}{2}\right) = 7.$$

I don't know what proof you're referring to for the case of the Gaussian integers, but in that case the proof I remember uses the Galois norm map from $\mathbb Z[i]$ to $\mathbb Z$, by $N:a+bi\to a^2+b^2$. The idea is that if $p$ is not still a prime in the Gaussian integers, then it factors (because $\mathbb Z[i]$ is Euclidean) $p=\alpha\cdot \beta$ with neither $\alpha$ nor $\beta$ a prime. Taking norms, $p^2=Np=N\alpha\cdot N\beta$. Neither $N\alpha$ nor $N\beta$ can be $\pm 1$, and in fact cannot be negative in any case, so both must be $p$. That is, with $\alpha=a+bi$, $a^2+b^2=1$, as desired. EDIT: forgot to add: for $p$ to remain prime in $\mathbb Z[i]$, it is necessary and sufficient that $\mathbb Z[i]/p$ is a field. Well, $\mathbb Z[i]/p\cong \mathbb Z/p[i]\cong \mathbb F_p[x]/\langle x^2+1\rangle$. For $p=1\mod 4$, the polynomial $x^2+1$ factors over $\mathbb F_p$, so this is not a field... and $p$ is a sum of two squares.

$N(a+b\omega)=a^2+ab+b^2$, with $\omega$ a cube root of unity, functions exactly analogously, because $\mathbb Z[\omega]$ is Euclidean. EDIT: a prime $p$ remains prime in $\mathbb Z[\omega]$ if and only if $\mathbb Z[\omega]/p$ is a field. Since $\mathbb F_p$ contains a cube root of unity if and only if $p=1\mod 3$, we get the analogous result.

The general question about $a^2+b^2N=p$ is of a different nature. David A. Cox wrote a whole book about it: "Primes of the form $a^2+b^2n$".

I just want to fill in a few details glossed over in the previous answers. These details might be very obvious to some, but not at all obvious to others.

First, the symmetry of the Gaussian integers is square, while the symmetry of the Eisenstein integers is hexagonal.

For example, in the case of numbers with norm 13, we see that $(2 + 3i)i = -3 + 2i$, $(-3 + 2i)i = -2 - 3i$, $(-2 - 3i)i = 3 - 2i$ and one more multiplication by $i$ brings us right back to where we started. If you prefer to go clockwise instead, use $-i$ rather than $i$.

A much easier example is 7, with norm 49. We see that $7 \times i = 7i$, $(7i)i = -7$, $-7 \times i = -7i$ and one more multiplication by $i$ brings us right back to where we started.

Moving over to the Eisenstein integers, our "main" unit would be $$\omega = -\frac{1}{2} + \frac{\sqrt{-3}}{2},$$ which has the property that $\omega^3 = 1$.

If a rational prime $p$ can be written as $p = 3m + 1$, then we can express it in the form $p = j^2 + 3k^2$. (Here $j$ and $k$ are rational integers.) Then, I realized that norms don't work that way in Eisenstein ...

They certainly do work that way, but we have to keep in mind the distinction between algebraic numbers that are also algebraic integers and those that are not. To use the example of 7, we see that $7 = 2^2 + 3 \times 1^2$ and indeed $N(2 + \sqrt{-3}) = 7$. We can readily locate $2 + \sqrt{-3}$ on the complex plane.

But when we try $(2 + \sqrt{-3}) \omega$, things get very interesting: $$(2 + \sqrt{-3}) \omega = (2 + \sqrt{-3})\left(-\frac{1}{2} + \frac{\sqrt{-3}}{2}\right) = -\frac{5}{2} + \frac{\sqrt{-3}}{2}.$$

And then $$\left(-\frac{5}{2} + \frac{\sqrt{-3}}{2}\right) \omega = \frac{1}{2} - \frac{3 \sqrt{-3}}{2}.$$

And then $$\left(\frac{1}{2} - \frac{3 \sqrt{-3}}{2}\right) \omega = 2 + \sqrt{-3}.$$ Oops, I thought that was going to take me around the hexagon. But after all, what is a hexagon but two triangles put together?

For norm 13 on the diagram, I'm going to start on $-1 + 2 \sqrt{-3}$ rather than $1 + 2 \sqrt{-3}$. Then we have $$(-1 + 2 \sqrt{-3}) \omega = -\frac{5}{2} - \frac{3 \sqrt{-3}}{2}.$$

Well, maybe norm 13 was not the best choice for the outer example on this diagram. Plus I should have started with a larger diagram before putting on the dots and arrows.

Nevertheless, this shows that while $j + k \sqrt{-3}$ is the best way to locate Eisenstein integers in the complex plane, it is a little bit awkward for calculations. Maybe there is a way to get the best of both notations?

But before we do that, I'm not entirely liking the use of $j$ and $k$, in part because engineers like to use $j = \sqrt{-1}$. Though engineers use $\omega$ for something else, it doesn't bother me to use it here to mean a complex cubic root of 1.

Okay, so then, with $a$ and $b \in \Bbb Z$, we have $N(a + b \sqrt{-3}) = a^2 + 3b^2$ and $$N\left(\frac{a}{2} + \frac{b \sqrt{-3}}{2}\right) = \frac{a^2}{4} + \frac{3b^2}{4}$$ (however, if $a$ and $b$ don't have matching parities, the norm will be rational but not an integer, meaning the number is an algebraic number but not an algebraic integer).

And then, with the proviso that $\alpha$ and $\beta \in \Bbb Z$, we have $N(\alpha + \beta \omega) = \alpha^2 - \alpha \beta + \beta^2$. Furthermore, for $a + b \sqrt{-3} = \alpha + \beta \omega$, $\alpha = a + b$, $\beta = 2b$, and for $$\frac{a}{2} + \frac{b \sqrt{-3}}{2} = \alpha + \beta \omega,$$ $$\alpha = \frac{a + b}{2},$$ $\beta = b$.

To reverse the conversion, $$\alpha + \beta \omega = \frac{a}{2} + \frac{b \sqrt{-3}}{2},$$ $a = 2 \alpha - \beta$, $b = \beta$; simplify fractions as needed.

For example, $$\frac{-5}{2} + \frac{1 \sqrt{-3}}{2} = -2 + \omega,$$ both of which should give 7 when taken through the relevant norm calculations. Then $(-2 + \omega) \omega = -2 \omega + \omega^2$. Keep in mind that $\omega^2 = -1 - \omega$. This means that $-2 \omega + \omega^2 = -2 \omega + (-1 - \omega) = -1 - 3 \omega$.

Note that $(-1)^2 - (-1 \times -3) + (-3)^2 = 1 - 3 + 9 = -2 + 9 = 7$. Since I'm having an extremely difficult time locating $-1 - 3 \omega$ in the complex plane, I perform the conversion $$-1 - 3 \omega = \frac{-2 - (-3)}{2} + \frac{-3 \sqrt{-3}}{2} = \frac{1}{2} - \frac{3 \sqrt{-3}}{2}.$$

Next, $(-1 - 3 \omega) \omega = -\omega - 3 \omega^2 = -\omega - 3(-1 - \omega) = 3 + 2 \omega$. We check that $3^2 - 3 \times 2 + 2^2 = 9 - 6 + 4 = 3 + 4 = 7$. And lastly we check that $$3 + 2 \omega = \frac{4}{2} + \frac{2 \sqrt{-3}}{2} = 2 + \sqrt{-3}$$ and $N(2 + \sqrt{-3}) = 7$.

If a rational prime $p$ can be written as $p = 3m + 1$, then we can express it in the form $p = j^2 + jk + k^2$ (with $j$ and $k$ in $\Bbb Z$, as above).

Hmm, you seem to have a plus where you should have a minus. This detail probably caused half your confusion. Although I probably also made a similar mistake somewhere in the previous paragraphs.