# How to factorise a number in $\mathbb {Z}[\sqrt {-5}]$?

I am studying quadratic number fields. I have a question about factorization in $\mathbb {Z}[\sqrt {-5}]$ which seems less trivial than factorization in the Gaussian integers.

Let $w=\sqrt {-5}$. I use $N (a+bw)=a^2+5b^2$ as the norm function in the field. Look at the following example of multiplication of two numbers and their norms. ( Which demonstrates the multiplicativity of the norm function. )

$(2+4w)(3+7w)=(-134+26w)$

$N(2+4w)N(3+7w)=84*254=21336=N(-134+26w)$

What would be the best approach to factorise this number $(-134 + 26w)$ in $\mathbb {Z}[\sqrt {-5}]$, not knowing the factors of course?

The best way? That's a tough question and it deserves a carefully considered answer, and you're not going to get such an answer today. Today I hope to at least point you in the right direction.

I would say that factorization in $\mathbb{Z}[\sqrt{-5}]$ is "more interesting" rather than "less trivial" than factorization in $\mathbb{Z}[i]$. That's because the latter is a unique factorization domain, while the former is not. There is a reason why small semiprimes like 6 are the preferred examples to demonstrate the lack of unique factorization, as you may have already realized.

As you have already surmised, the norm is of great importance here. $N(-134 + 26\sqrt{-5}) = 21336$. There are several ways to go from here.

Given that this number has 32 divisors in $\mathbb{Z}^+$, it seems kind of laborious to check each of them to see if they're norms in $\mathbb{Z}[\sqrt{-5}]$. Here the OEIS is a big help. Looking at A020669, we see that the following divisors are norms: 1, 4, 6, 14, 21, 24, 56, 84, 254, 381, 889, 1016, 1524, 3556, 5334, 21336. So we've cut the list in half.

Of course $21336 = 1 \times 21336$ tells us nothing. But $21336 = 4 \times 5334$ does. Now, the divisors of 5334 in $\mathbb{Z}^+$ which are norms in $\mathbb{Z}[\sqrt{-5}]$ are 1, 6, 14, 21, 254, 381, 889, 5334. This leads to $6 \times 889 = 5334$. Neither 6 nor 889 are prime, but none of their nontrivial divisors are norms in $\mathbb{Z}[\sqrt{-5}]$.

So now we have $21336 = 4 \times 6 \times 889$. Then $2(1 - \sqrt{-5})(22 + 9\sqrt{-5}) = 134 - 26\sqrt{-5}$. Well, I need to tweak the signs, but this is close enough. But this is only one potential factorization. And there's another factorization involving $13 + 12\sqrt{-5}$ but at the moment I can't figure it out.

And I've gotten this just by following one "divisor path." I believe I could obtain different factorizations by going down different paths. The point is that this is very laborious. I believe the concept of ideals can help, that by figuring out the one factorization into prime ideals, you can find all the distinct factorizations into irreducibles. Also, the contrast between factorization into elements and factorization into ideals leads to still more interesting concepts, like the class number. But that's probably later in your book.

• Yet another good use of OEIS.. – nilo de roock Oct 28 '14 at 12:24

Here's how to find all factorizations of $-134 + 26\sqrt{-5}$ in $\mathbf{Z}[\sqrt{-5}]$, using some more theory.

$\mathbf{Z}[\sqrt{-5}]$ is the ring of integers of $\mathbf{Q}(\sqrt{-5})$ and hence it is a Dedekind domain.

We begin by factoring the principal ideal $I = (-134 + 26\sqrt{-5})$ into primes.

Note that $I$ contains the integer $N(-134 + 26\sqrt{-5}) = 21336 = 2^3\cdot 3 \cdot 7 \cdot 127$, so $(21336) = IJ$ for some $J$, and hence the prime factors of $I$ are a subset of those of $(21336)$.

By the Kummer-Dedekind theorem, the primes $2, 3, 7$ and $127$ split into primes in $\mathbf{Z}[\sqrt{-5}]$ as follows:

• $2 = (2, 1 + \sqrt{-5})^2$,

• $3 = (3, 1 + \sqrt{-5})(3, 2 + \sqrt{-5})$,

• $7 = (7, 3 + \sqrt{-5})(7, 4+\sqrt{-5})$, and

• $127 = (127, 54 + \sqrt{-5})(127, 73 + \sqrt{-5})$.

To determine if one of these primes $\mathfrak{p} = (p, r + \sqrt{-5})$ divides $I$, we check whether $I \subset \mathfrak{p}$. That is, whether $-134 + 26\sqrt{-5} = px + (r + \sqrt{-5})y$ has any solutions $x,y \in \mathbf{Z}[\sqrt{-5}]$. Writing $x = a + b\sqrt{-5}$ and $y = c + d\sqrt{-5}$, the equation becomes $$-134 = pa + rc - 5d, \quad 26 = pb + rd + c,$$ which reduces to $-134 - 26r = pa - prb - (r^2 + 5)d$ (using $c = 26 - pb - rd$). This equation has solutions if and only if $134 + 26r \in (p, r^2 + 5) = (p)$. The last equality holds because $r$ was obtained from the Kummer-Dedekind theorem. In conclusion, we have to check whether $134 + 26r \equiv 0 \pmod p$.

For example, $(3, 1 + \sqrt{-5})$ does not divide $I$ because $160 \equiv 1 \pmod 3$, and $(3, 2 + \sqrt{-5})$ does divide $I$ because $186 = 3\cdot 62$. In this way we find that the primes dividing $I$ are $(2, 1 + \sqrt{-5})$, $(3, 2 + \sqrt{-5})$, $(7, 4 + \sqrt{-5})$ and $(127, 73 + \sqrt{-5})$.

Now we compute $\operatorname{ord}_\mathfrak{p}(I)$ for these primes. From the equality $(21336) = IJ$ it follows that for $\mathfrak{p}$ one of $(3, 2 + \sqrt{-5}), (7, 4 + \sqrt{-5})$ and $(127, 73 + \sqrt{-5})$ we have $\operatorname{ord}_\mathfrak{p}(I) = 1$. For $\mathfrak{p} = (2, 1 + \sqrt{-5})$ we know that $1 \leq \operatorname{ord}_\mathfrak{p}(I) \leq 3$, and since $\mathfrak{p}^2 = (2)$, we can see that $\mathfrak{p}^3 = (4, 2 + 2\sqrt{-5})$ divides $I$, as $-134 + 26\sqrt{-5} = 13\cdot(2+2\sqrt{-5}) - 40\cdot 4$.

Hence the factorization of the ideal $I = (-134 + 26\sqrt{-5})$ into primes in $\mathbf{Z}[\sqrt{-5}]$ is given by $$I = (2, 1 + \sqrt{-5})^3(3, 2 + \sqrt{-5})(7, 4 + \sqrt{-5})(127, 73 + \sqrt{-5}).$$

Since all these primes are non-principal and $\mathbf{Q}(\sqrt{-5})$ has class number $2$, any factorization of $I$ into principal ideals must be such that every principal ideal is a product of an even number of these primes.

The proper partitions of $6$ (the number of primes counted with multiplicity) into even numbers are $6 = 2 + 2 + 2$ and $6 = 4 + 2$. The latter partition corresponds to factorizations into reducible elements, so we ignore it.

You can compute the ${4 \choose 2} + 1 = 7$ different products of two of these primes; they are

• $\mathfrak{p}_2\mathfrak{p}_{3} = (1 - \sqrt{-5})$,
• $\mathfrak{p}_2\mathfrak{p}_{7} = (3 - \sqrt{-5})$,
• $\mathfrak{p}_2\mathfrak{p}_{127} = (3 + 7\sqrt{-5})$,
• $\mathfrak{p}_3\mathfrak{p}_{7} = (1 + 2\sqrt{-5})$
• $\mathfrak{p}_3\mathfrak{p}_{127} = (19 + 2\sqrt{-5})$,
• $\mathfrak{p}_7\mathfrak{p}_{127} = (22 + 9\sqrt{-5})$, and
• $\mathfrak{p}_2^2 = (2)$.

Observe (by looking at $\mathfrak{p}_2$) that any factorization of $I$ into principal ideals must either be of the form $\mathfrak{p}_2^2 (\mathfrak{p}_2\mathfrak{p}_i) (\mathfrak{p}_j\mathfrak{p}_k)$ or of the form $(\mathfrak{p}_2\mathfrak{p}_i)(\mathfrak{p}_2\mathfrak{p}_j)(\mathfrak{p}_2\mathfrak{p}_k)$. Hence all the factorizations of $I$ into principal ideals are $\mathfrak{p}_2^2 (\mathfrak{p}_2\mathfrak{p}_3) (\mathfrak{p}_7\mathfrak{p}_{127}), \mathfrak{p}_2^2 (\mathfrak{p}_2\mathfrak{p}_7) (\mathfrak{p}_3\mathfrak{p}_{127}), \mathfrak{p}_2^2 (\mathfrak{p}_2\mathfrak{p}_{127}) (\mathfrak{p}_3\mathfrak{p}_7)$ and $(\mathfrak{p}_2\mathfrak{p}_3)(\mathfrak{p}_2\mathfrak{p}_7)(\mathfrak{p}_2\mathfrak{p}_{127})$.

Writing this out, we get four factorizations

1. $I = (2)(1 - \sqrt{-5})(22 + 9\sqrt{-5})$,
2. $I = (2)(3-\sqrt{-5})(19 + 2\sqrt{-5})$,
3. $I = (2)(3 + 7\sqrt{-5})(1+2\sqrt{-5})$,
4. $I = (1-\sqrt{-5})(3-\sqrt{-5})(3 + 7\sqrt{-5})$.

As the only units in $\mathbf{Z}[\sqrt{-5}]$ are $\pm 1$, this leads (by choosing the right signs) to four factorizations of $-134 + 26\sqrt{-5}$ in $\mathbf{Z}[\sqrt{-5}]$:

1. $-134 + 26\sqrt{-5} = -2(1 - \sqrt{-5})(22 + 9\sqrt{-5})$,
2. $-134 + 26\sqrt{-5} = -2(3-\sqrt{-5})(19 + 2\sqrt{-5})$,
3. $-134 + 26\sqrt{-5} = 2(3 + 7\sqrt{-5})(1+2\sqrt{-5})$,
4. $-134 + 26\sqrt{-5} = -(1-\sqrt{-5})(3-\sqrt{-5})(3 + 7\sqrt{-5})$.

Factorization number 3 is the one from the question. The factorizations into reducible elements (corresponding to the partition $6 = 4 + 2$) are obtained by multiplying out two of the three factors in the products above.

I have some questions for you: Were you the one who came up with that $-134 + 26 \sqrt{5}i$ example? Because its really horrible from a pedagogic standpoint. Also, are you're aware of the difference between primes and irreducibles? Are you going to take your time reading the chapter on ideals? You should, its a useful concept but few explain it well. Do you see why it might seem unclear if you neglect to distinguish between factorization into irreducibles and factorization into ideals?

In a domain like $\mathbb{Z}$, primes and irreducibles are the same thing. All primes are irreducible but not all irreducibles are prime. e.g., If $p$ is prime and $p|ab$, then either $p|a$ or $p|b$. Let's say $p = 2$, $a = 3$, $b = 8$. Clearly $2|(3 \times 8)$, and though $2 \nmid 3$, it does divide $8$.

Now let's look at $\mathbb{Z}[\sqrt{-5}]$. Set $p = 1 + \sqrt{-5}$, keep $a$ and $b$ the same. We see that $(1 + \sqrt{-5})|24$, but $\frac{3}{1 + \sqrt{-5}} \not\in \mathbb{Z}[\sqrt{-5}]$, and likewise $\frac{8}{1 + \sqrt{-5}} \not\in \mathbb{Z}[\sqrt{-5}]$ ether. $1 + \sqrt{-5}$ is irreducible but not prime.

Without knowing about ideals, what would be the best way to find for a given number all factorizations into irreducibles in a non-UFD? Robert gave the answer earlier, though verbosely. I will condense what he said: first you compute the norm, then you build a non-trivial divisor tree, remove the limbs at nodes that are not norms in the given domain, follow the remaining paths and obtain the factorizations.

But instead of working through a horrible example like $-134 + 26\sqrt{-5}$, try a number with a much smaller norm, like, say, $24$. It's norm is $576$. The divisors of $576$ we need to build our tree are $4, 6, 9, 16, 24, 36, 64, 96, 144$. Following our tree down the $4 \times 144$ branch leads us to this factorization: $2^3 \times 3$. Another branch leads us to $2^2 \times (1 - \sqrt{-5})(1 + \sqrt{-5})$. You should be able to work out the rest of this example on your own; I encourage to try your hand at other small numbers.

• I'm not sure the $4 \times 144$ branch really does lead to $2^3 \times 3$, and I'm not sure 24 is the best example,though it really is better than $-134 + 26 \sqrt{-5}$. – Robert Soupe Oct 26 '14 at 1:23
• Yes, i came up with example myself. Yes, aware of difference prime and irreducibles. Reading stuff on ideals now. – nilo de roock Oct 28 '14 at 12:20
• I think that once you understand ideals, you will see that Ricardo's answer is the best of this bunch. But Robert's is pretty good, too. – user155234 Oct 30 '14 at 23:02