# Factoring a number of complex integers?

Say you are given a number (ex: $377$) and you express it in a form that allows you to factor it over the complex integers:

Notice,

$377 = 16^2 + 11^2$

Thus:

$(16 + 11i)$ and $(16 - 11i)$

Are factors of our number. The way that people can use known rational points on a curve to find others... Is there a way to use known complex integral points on the curve $xy = 377$ to find other integral points?

PS the solution is $(29 \times 13)$

• +1 I like to see people playing with math, no matter what the subject. – Ross Millikan Jun 18 '13 at 4:55

## 2 Answers

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.

• +1 Then if we want to factor in the naturals, we can multiply the conjugates $(3+2i)(3-2i)=11$ and (2+5i)(2-5i)=29$– Ross Millikan Jun 18 '13 at 4:53 • But lets say you know for fact 377 isn't a prime... Then you know that we can factor 16 + 11i – frogeyedpeas Jun 18 '13 at 5:02 • Is that a straightforward task? – frogeyedpeas Jun 18 '13 at 5:03 • Sure. You factor 377 into gaussian integers just like I did, and then the factors that don't multiply together to make 29 and 13 are the ones that do multiply together to make$16\pm 11i$. – MJD Jun 18 '13 at 5:04 • But say a number N can be expressed as dl – frogeyedpeas Jun 18 '13 at 5:19 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. • Omg this just made my night! – frogeyedpeas Jun 18 '13 at 5:26 • Can you do this with sums of cubes as well??? – frogeyedpeas Jun 18 '13 at 5:28 • I thought you might enjoy that! You can't do it with cubes, but you can do it with sums of four squares. – MJD Jun 18 '13 at 5:29 • But for sums of cubes you can play a different trick:a^3 + b^3 = (a+b)(a^2 - ab + b^2)$. So if you have some number like$2^3 +3^3 = 35$, you automatically know it is factorable as$(2+3)(2^2 - 2\cdot 3 + 3^2) = 5\cdot 7\$. – MJD Jun 18 '13 at 5:34
• @frogeyedpeas Pressing the up-arrow on the left is also useful to express appreciation... – Myself Jun 18 '13 at 6:53