Gaussian prime factorization.

Question

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$.

Answer 1

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.

Answer 2

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.