# Gaussian prime factorization.

I have a hard time on factorizing elements from $\mathbb{Z}[i]$, especially $-19+43i$.

I know that the primes in $\mathbb{Z}[i]$ are:

1. $1+i$.
2. $p$ from $\mathbb{N}$, $p=4k+3$ , $k$ integer ( $p\equiv 3\pmod{4}$ ).
3. $a+bi$ from $\mathbb{Z}[i]$, $p=N(a+bi)=a^2 + b^2$ and $p=4k+1$, $k$ integer ( $p\equiv1\pmod{4}$).

I wonder if there is an algorithm that tells you how to factorize or something. I would like to see this working on $-19+43i$.

• Yes, there are such algorithms, some more efficient than others. You could use norms to "port" trial division from $\mathbb{Z}$ to $\mathbb{Z}[i]$. You'd need a list of primes in $\mathbb{Z}[i]$ having a smaller norm than the number you're trying to factorize. This probably would be the least efficient algorithm.
– Lisa
Commented Dec 9, 2015 at 22:40

Here is one algorithm to factor $$a + bi$$ when $$a \neq 0$$, $$b \neq 0$$ and $$\textrm{gcd}(a, b) = 1$$:

1. Compute the norm of $$a + bi$$, which is a purely real integer $$n$$.
2. Factor $$n$$ into $$\mathbb{Z}$$ primes and if possible further into Gaussian primes.
3. From the Gaussian prime factorization of $$n$$, identify the conjugate pairs. In each conjugate pair, there is one number that belongs in the factorization of $$a + bi$$ and one that does not. At this point I wish I had something more clever than telling you to try each combination, by dividing $$a + bi$$ by each number of the conjugate pair and discarding those numbers which don't give Gaussian integers; if both divisions give Gaussian integers, discard one number of the pair arbitrarily.
4. If necessary, prefix the factorization with a Gaussian unit (other than 1) to get the signs right.

The most important thing to remember is that the norm function is multiplicative: $$N(pq) = N(p) N(q)$$. This is something that you can carry over to many real and imaginary rings. Also, if the norm is a number that is prime in $$\mathbb{Z}$$, that means the corresponding number is prime (or at least irreducible) in the particular domain at hand.

In $$\mathbb{Z}[i]$$ we have the additional wrinkle that since $$d = -1$$ the norm function works out to $$a^2 + b^2$$, which can be occasionally confusing, compared to something more helpful like $$a^2 + 2b^2$$ in the case of $$\mathbb{Z}[\sqrt{-2}]$$ or $$a^2 - 3b^2$$ in the case of $$\mathbb{Z}[\sqrt{3}]$$.

Review the norm function of $$\mathbb{Z}[i]$$: $$N(a + bi) = (a - bi)(a + bi) = a^2 + b^2.$$ Thus $$N(-19 + 43i) = (-19 - 43i)(-19 + 43i) = 2210$$ and $$2210 = 2 \times 5 \times 13 \times 17$$.

Fermat stated and Euler proved that if positive $$p = 2$$ or $$p \equiv 1 \pmod 4$$, then $$p = a^2 + b^2$$. This means that such primes in $$\mathbb{Z}$$ are composite in $$\mathbb{Z}[i]$$. The example of $$-19 + 43i$$ seems to have been contrived specifically to use the first four primes of $$\mathbb{Z}^+$$ that are composite in $$\mathbb{Z}[i]$$. We have $$2210 = (1 - i)(1 + i)(1 - 2i)(1 + 2i)(2 - 3i)(2 + 3i)(1 - 4i)(1 + 4i).$$ Since $$(-19 - 43i)(-19 + 43i) = 2210$$, the factorization of $$2210$$ overshoots the factorization of $$-19 + 43i$$ by $$-19 - 43i$$.

So we try $$\frac{-19 + 43i}{1 - i} = -31 + 12i$$ and $$\frac{-19 + 43i}{1 + i} = 12 + 31i;$$ since both of these give Gaussian integers, I arbitrarily choose to discard $$1 + 2i$$. Things are more clear-cut with the conjugate pair for 5: $$\frac{-19 + 43i}{1 + 2i} = \frac{67 + 81i}{5}.$$

This leads to $$(1 - i)(1 - 2i)(2 + 3i)(1 + 4i) = 43 + 19i,$$ which is almost correct. We need to swap the real and imaginary parts and change the sign of the new real part. Clearly $$-1$$ won't do (that would give $$-43 - 19i$$), and less obviously $$-i$$ doesn't work either. Then $$i(1 - i)(1 - 2i)(2 + 3i)(1 + 4i) = -19 + 43i.$$

This has been overly laborious and I'm sure someone will come along with a much cleverer way. But even with the algorithm I have presented here I could have skipped Step 4 if I had made a different choice with the conjugate pair for 2, since $$(1 + i)(1 - 2i)(2 + 3i)(1 + 4i) = -19 + 43i.$$

EDIT: Amended per a comment.

• When you say "In each conjugate pair, there is one number that belongs in the factorization of 𝑎+𝑏𝑖 and one that does not...", why is this true? Commented Sep 13, 2023 at 3:49
• @V.Elizabeth I stipulated that here neither $a$ nor $b$ is equal to 0, but I neglected to also stipulate that $\textrm{gcd}(a, b) = 1$. If $\textrm{gcd}(a, b) > 1$, there could be a divisor that is the product of a conjugate pair, e.g., $5 + 10i$ is divisible by both $2 - i$ and $2 + i$. I will amend my answer accordingly. Commented Sep 16, 2023 at 3:40

In general, factorization, in the integers or in the Gaussian integers, is difficult. We use a procedure that is only feasible for "smallish" Gaussian integers.

Calculate the norm of our number. We have $$(-19)^2+(43)^2=2210=(2)(5)(13)(17).$$ Gaussian prime factors of our number must therefore come from $1+i$, $2\pm i$, $3\pm 2i$, $4\pm i$. And since for example $5$ does not divide our number, exactly one of $2\pm i$ divides our number.

I would probably would start by dividing our number by $1+i$. Let the result be $a_1+b_1 i$. Check whether $2-i$ divides $a_1+b_1 i$. If it does, divide by $2-i$. If not, divide by $2+i$, one of them must work. Let the result be $a_2+b_2 i$. Check whether $3-2i$ divides $a_2+b_2i$. Continue.

• By that logic and the frivolous theorem of arithmetic, factorization in $\mathbb{Z}$ is in general also difficult. That factorization may take too long for practical purposes does not detract from the fact that there are factorization algorithms. Commented Dec 10, 2015 at 3:56
• The answer above describes an algorithm, albeit one that is feasible only when the Gaussian integer is not too "large." Commented Dec 10, 2015 at 4:58