Factoring a number of complex integers?

Factorization over the gaussian integers (complex numbers $a+bi$ where $a$ and $b$ are integers) is unique, just as it is over the regular integers. So for any two factorizations of the same number, say $$(16+11i)(16-11i) = 29\cdot 13$$ there must be a common refinement—a further factorization of each side that is the same.

In this case, you should observe that $29 = 5^2+2^2 = (2-5i)(2+5i)$, and $13 = 3^2+2^2 = (3+2i)(3-2i)$. So by refining the right-hand side we get

$$(16+11i)(16-11i) = (2-5i)(2+5i)(3+2i)(3-2i).$$

The unique factorization theorem for gaussian integers tells us that $16+11i$ and $16-11i$ must split into the same factors as on the right-hand side. And in fact, $16-11i = (2-5i)(3+2i)$ and $16+11i = (2+5i)(3-2i)$.

So once you have the $16\pm 11i$ factorization, you continue to factor until you reach a product of gaussian primes, and then you can see if which of the gaussian primes in the product are conjugate pairs.

Unfortunately, this is less than useful, because how can you tell whether something like $16-11i$ is a gaussian prime? There is a theorem: $a+bi$ is a gaussian prime if either:

• one of $a$ or $b$ is zero and the other is a prime of the form $4k+3$, which doesn't apply here, or
• neither $a$ nor $b$ is zero, and $a^2 + b^2$ is prime.

which means that to find out whether $16+11i$ is a gaussian prime, and therefore whether it can be factored further, you calculate $16^2+11^2 = 377$ and check if 377 is prime, so you are right back where you started.

There is something else you can do, but you have to notice a little more. You observed that $$377 = 16^2 + 11^2.$$

But what you didn't mention was that $$377 = 19^2 + 4^2.$$

When you have the same number as a sum of two squares in two ways like this, you can factor it as follows: Calculate ${19 + 11\over 2} = 15$ and ${19 -11\over 2}= 4$ and call those $ac$ and $bd$. And then calculate ${16+4\over 2} = 10$ and ${16-4\over 2} = 6$ and call those $ad$ and $bc$. Then you have:

$$\begin{align} ac & = 15\\ bd & = 4 \\ ad & = 10 \\ bc & = 6 \end{align}$$

Then you can solve these to get $$\begin{align} a & = 5 \\ b & = 2 \\ c & = 3 \\ d & = 2 \end{align}$$

and here is where the magic happens: $$\begin{align} 377 & = (a^2 + b^2)(c^2 + d^2) \\ & = 29\cdot 13 \end{align}$$

This is a consequence of the two-square identity, which Wikipedia calls the "Brahmagupta–Fibonacci identity", even though it was known to Diophantus much earlier.