# Factoring into primes using the norm function

Let $l(z)=z \bar z$ be a norm function.

How can one perform prime factorization in the rings $\mathbb{Z}[i]$, $\mathbb{Z}[\frac{-1 \sqrt{-3}}2]$ or any other ring using the norm function?

For example, how can one find prime factorization of $8+i \in \mathbb{Z}[i]$ or $13 \in \mathbb{Z}[\frac{-1 \sqrt{-3}}2]$?

Any help would be appreciated.

-
Why do you think this should be possible at all? Are there any hints you have been given? –  Joe Tait Feb 23 '14 at 16:02

If $R$ is a ring, $a,b\in R$ such that $a\mid b$, then we have $b=ak$ for some $k\in R$, and if $\mathsf{N}:R\to\mathbb{Z}_{\geq 0}$ is a norm function, then we have $$\mathsf{N}(b)=\mathsf{N}(ak)=\mathsf{N}(a)\mathsf{N}(k)\;\;\implies \;\;\mathsf{N}(a)\mid \mathsf{N}(b).$$ As an example, if we take $R=\mathbb{Z}[i]$ and $\mathsf{N}(a+bi)=a^2+b^2$, then $$\mathsf{N}(8+i)=8^2+1^2=65=5\cdot 13.$$ So if $$8+i=u\;\pi_1^{d_1}\cdots\pi_n^{d_n}$$ is the factorization into irreducibles of $8+i$ in the ring $\mathbb{Z}[i]$ ($u$ being a unit), we have that $$\mathsf{N}(8+i)=65=\mathsf{N}(\pi_1)^{d_1}\cdots\mathsf{N}(\pi_n)^{d_n}.$$ Now, I leave it to you to check that we cannot have $\mathsf{N}(\pi)=65$ for any irreducible $\pi\in\mathbb{Z}[i]$ (do you know the classification of irreducibles in $\mathbb{Z}[i]$?) But from this, we see that $$8+i=u\;\pi_1\pi_2$$ where $\mathsf{N}(\pi_1)=5$ and $\mathsf{N}(\pi_2)=13$, and $u\in\{\pm1,\pm i\}$. Now just solve for the real and imaginary parts of $\pi_1$ and $\pi_2$... except for the fact that there are two potential $\pi_1$'s and two potential $\pi_2$'s (up to multiplication by a unit), each potential being the conjugate of the other: $$\pi_1\in\{2\pm i\},\quad \pi_2\in\{3\pm 2i\}.$$ Here I think you must guess and check (at least, I don't remember any way of deducing which conjugate we need).
Some ways of checking are nicer than others. Instead of doing straight division by $2+i$, say, you could look at the original number mod $2+i$. Keeping in mind that ${\mathbf Z}[i]/(2+i) \cong {\mathbf Z}/(5)$, with $i \equiv -2 \equiv 3$, we have $8+i \equiv 8+3 = 11 \equiv 1 \not\equiv 0$, so $2+i$ is not a factor: $2-i$ has to be. –  KCd Feb 23 '14 at 16:15
How did you know to give $\pi_2$ the values $3+- 2i$? I personally thought right away on $\sqrt{12} +- i$ –  user130955 Feb 23 '14 at 16:28
@user130955: Like I said, solve for the real and imaginary parts. If $\mathsf{N}(a+bi)=13$, what can $a$ and $b$ be? This will give you 8 possibilities for the element $a+bi$, but you don't care about units, so there are only 2 fundamentally different options (e.g., $3$ is an irreducible in $\mathbb{Z}[i]$, but if I solve for $\mathsf{N}(a+bi)=9$ I could have $\pm3, \pm 3i$; I would just choose $3$ since if it were any of the others, the unit can be placed in the $u$ in the factorization.) –  Zev Chonoles Feb 23 '14 at 16:32