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

Question

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?

Answer 1

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.

Answer 2

A different approach us to identify a unique factorization in an augmented set that includes both $\mathbb Z[\sqrt{-5}]$ and the algebraic integers having the form $a\sqrt2+b\sqrt{-10}$, with $a,b$ rational. The latter numbers are algebraic integers when $a$ and $b$ are both integers or both integers plus one-half, such as $(\sqrt2+\sqrt{-10})/2$ whose minimal polynomial is $x^4+4x^2+9$.

Given $-134+26\sqrt{-5}$, first factor put the ramified primes $2$ and $5$. Only $2$ is a factor in this case:

$-134+26\sqrt{-5}=2(-67+13\sqrt{-5})$

The numbers $67$ and $13$ are both odd, so we identify an additional factor of $\sqrt2$ from the augmenting lattice. We also reduce our original factor of $2$, so there will be a total of three $\sqrt2$ factors:

$-134+26\sqrt{-5}=(\sqrt2)^3[(-67\sqrt2+13\sqrt{-10})/2]$

where $(-67\sqrt2+13\sqrt{-10})/2$ is an algebraic integer.

We now multiply this algebraic integer by its complex conjugate, which gives $(4489+5×169)/2=2667$. This factors in natural numbers as $3×7×127$.

We then factor each of the numbers $3,7,127$ in the augmented lattice I defined. A prime number having residue $3$ or $7\bmod 20$ will have factors of the form $a\sqrt2+b\sqrt{-10}$ where $a$ and $b$ are each an integer plus one-half, while residues $1$ and $9$ will produce factors in $\mathbb Z[\sqrt{-5}]$ instead. Other primes besides $2$ and $5$, which we already eliminated, will be irreducible.

Clearly in this case all the natural primes $3,7,127\in\{3,7\}\bmod 20$, so we render

$3=\left(\dfrac{m\sqrt2+n\sqrt{-10}}2\right)\left(\dfrac{m\sqrt2-n\sqrt{-10}}2\right)$

from which we are then required to solve $m^2+5n^2=6$ for a pair of positive odd integers $m,n$. Thus $m=n=1$ and

$3=\left(\dfrac{\sqrt2+\sqrt{-10}}2\right)\left(\dfrac{\sqrt2-\sqrt{-10}}2\right).$

Similarly, though less trivially,

$7=\left(\dfrac{3\sqrt2+\sqrt{-10}}2\right)\left(\dfrac{3\sqrt2-\sqrt{-10}}2\right)$

$127=\left(\dfrac{3\sqrt2+7\sqrt{-10}}2\right)\left(\dfrac{3\sqrt2-7\sqrt{-10}}2\right)$

We now pick one of the factors of $3$, one of the factors of $7$ and one of the factors of $127$ such that their product is our target $(-67\sqrt2+13\sqrt{-10})/2$. We try out different sign combinations:

$\left(\dfrac{\sqrt2+\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2+\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2+7\sqrt{-10}}2\right)=(-73\sqrt2-\sqrt{-10})/2■$

$\left(\dfrac{\sqrt2+\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2+\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2-7\sqrt{-10}}2\right)=(67\sqrt2+13\sqrt{-10})/2■\text{but imaginary part is correct, so take conjugates and multiply by -1}$

$(-1)\left(\dfrac{\sqrt2-\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2-\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2+7\sqrt{-10}}2\right)=(-67\sqrt2+13\sqrt{-10})/2☆$

Thus we have obtained the unique double-lattice factorization:

$-134+26\sqrt{-5}=(-1)(\sqrt2)^3\left(\dfrac{\sqrt2-\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2-\sqrt{-10}}2\right)\cdot\left(\dfrac{3\sqrt2+7\sqrt{-10}}2\right)$

Now we have to translate the factors back into $\mathbb Z[\sqrt{-5}]$. To do this note that pairs of numbers having the secondary form $a\sqrt2+b\sqrt{-10}$ will have products within $\mathbb Z[\sqrt{-5}]$. For instance

$(\sqrt2)\left(\dfrac{\sqrt2-\sqrt{-10}}2\right)=1-\sqrt{-5}$

So we simply pair up the secondary-lattice factors. Since there are six of them we have fifteen possible pairings, but not all are distinct because of the repeated factor of $\sqrt2$. To count the pairings distinctly, we may consider two cases.

The first case: two $\sqrt2$ factors are paired with each other, leaving the last one to be joined with one of the other secondary-lattice factors. The remaining two complex factors, which are not paired with $\sqrt2$, are multiplied by each other to produce the third non-unit factor in $\mathbb Z[\sqrt{-5}]$. This gives three nonunique factorizations in $\mathbb{Z}[\sqrt{-5}]$:

$-134+26\sqrt{-5}=(-1)(2)(1-\sqrt{-5})(22+9\sqrt{-5})$

$-134+26\sqrt{-5}=(-1)(2)(3-\sqrt{-5})(19+2\sqrt{-5})$

$-134+26\sqrt{-5}=(2)(3+7\sqrt{-5})(1+2\sqrt{-5}).$

In the second case, no $\sqrt2$ factors are paired with each other; instead one of them is paired with each of the three complex factors from the unique double-lattice factorization. This gives one more nonunique factorization in $\mathbb Z[\sqrt{-5}]$:

$-134+26\sqrt{-5}=(-1)(1-\sqrt{-5})(3-\sqrt{-5})(3+7\sqrt{-5}).$

Answer 3

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.

Answer 4

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.