# How can I find decompositions in $\mathbb{Z}[\sqrt{d}]$?

## Decompositions in $\mathbb{Z}$

In $\mathbb{Z}$ you can find a decomposition of any element $n \in \mathbb{Z}$ by factorization such that

$$n = \prod_{p \in \mathbb{P}} p^{v_p(n)}$$

So for a concrete example:

$$48 = 2 \cdot 24 = 2^2 \cdot 12 = 2^3 \cdot 6 = 2^4 \cdot 3$$

## Decompsitions in $\mathbb{Z}[\sqrt{d}]$

Now let $R := (\mathbb{Z}[\sqrt{d}], +, \cdot)$ be a ring with $d \in \mathbb{Z}$ and $$\mathbb{Z}[\sqrt{d}] := \{a + b \cdot \sqrt{d} | a, b \in \mathbb{Z}\}$$

You can composite more elements in this ring, e.g. for $d = -1$

$$-i \cdot (1+i)^2 = -i (1 + 2i - 1) = -i(2i) = 2$$

So obviously at least one prime in $\mathbb{Z}$ has a decomposition in $\mathbb{Z}[i]$.

## Questions

Is there any algorithm with which I can find such a decomposition of any prime $p$ and for any $d$? Are there decompositions of numbers $a+b\sqrt{d}$ with $a \neq 0 \neq b$ (and of course $d \neq 0$)? Can you please describe it generally and with $17$?

If $b = 0$ I can factorize $a$ as I know it in $\mathbb{Z}$, but as soon as I only have prime numbers left, I might still be able to further factorize the number.

Is the decomposition in $\mathbb{Z}[\sqrt{d}]$ unique? According to fundamental theorem of arithmetic it is unique in $\mathbb{Z}$, but I don't know if it is still true for $\mathbb{Z}[\sqrt{d}]$.

Uniqueness of the factorization in $\mathbb Z[\sqrt{d}]$

The best we can expect is that a factorization into irreducibles is unique up to permuting the factors and multiplying factors with units. Rings in which every element has an unique (in this sense) factorization are called unique factorization domain (UFD). For example, the ring of the Gaussian integers ($d=-1$) is an UFD. But not all rings $\mathbb{Z}[\sqrt{d}]$ are UFDs, a counterexample is the ring $\mathbb{Z}[\sqrt{-3}]$, in which $4 = 2\cdot 2 = (1 + \sqrt{-3})(1 - \sqrt{-3})$ has two factorizations.

Computation of the factorization in $\mathbb Z[\sqrt{d}]$

An important tool for such rings is the norm function $$N : R \to \mathbb{N}, \quad a + b\sqrt{d}\mapsto \lvert{(a + b\sqrt{d})(a - b\sqrt{d})\rvert}.$$ Its crucial property is that it is multiplicative ($N(xy) = N(x)N(y)$). We get the following consequences:

• $x\in R^\times \iff N(x) = 1$
• $N(x)$ prime in $\mathbb{Z} \implies x$ irreducible in $R$
• Each proper factorization of $x\in R$ implies a proper factorization of $N(x)$ in $\mathbb{Z}$.

As a result, we get the following method to factor $x$ in $R$: First compute $N(x)$. For each factor $a$ of $N(x)$ (in $\mathbb Z$), enumerate all elements of $R$ with norm $a$ (up to multiplication with units, there are only finitely many), and test if $x$ is divisible by $a$. Then continue with the two factors you found.

This is the basic idea of factorization in $R$. The method can be refined by special knowledge about the ring $R$ (depending on $d$).

Example: Factorization of $x = 17$ in the ring of Gaussian numbers $\mathbb{Z}[i]$

Here $N(x) = \lvert x\rvert^2$ and $N(17) = 17^2$. Assume $17 = rs$ with $r,s\in R\setminus R^\times$. Application of $N$ yields $N(17) = N(rs)$, so $17^2 = N(r)N(s)$ and hence $N(r) = N(s) = 17$.

To find the elements of norm $17$, we look at the norm equation $N(a + bi) = a^2 + b^2 = 17$. The 8 solutions are $(a,b)\in\{(\pm 1, \pm 4), (\pm 4, \pm 1)\}$. So up to multiplication with units (the units in $R$ are $\pm 1$ and $\pm i$), the elements of norm $17$ are $1 + 4i$ and $1 - 4i$. This leads to the factorization $$17 = (1 + 4i)(1 - 4i).$$

• @azimut: Is the following correct: $a$ is irreducible $\Leftrightarrow N(a)$ is prime – Martin Thoma Sep 4 '13 at 12:32
• Just a comment: you have implicitly used the fact $N(a)=\pm 1$ if and only if $a$ is a unit. If you dont use this fact, you could happen to "delete" some factor of $a$. – Fredrik Meyer Sep 4 '13 at 13:23
• @FredrikMeyer: Thanks. I've moved the $N(x) = 1 \iff x\in R^\times$ argument from the application part to the general part. – azimut Sep 4 '13 at 18:02
• @moose: No, it isn't. By the multiplicativity of $N$ you get $N(a)$ prime $\implies a$ irreducible. But for example in the Gaussian numbers, there are no elements of norm $3$. Hence, the element $3$ is irreducible, but its norm $9$ is not a prime number in $\mathbb Z$. – azimut Sep 4 '13 at 18:15
• @rschwieb: done. And thanks for the feedback! – azimut Sep 4 '13 at 18:20