# About unique factorization of natural numbers into irreducibles

Confine attention to the positive integers in what follows. Suppose for any $$n>1$$ we define $$L(n)$$ to be the least divisor of $$n$$ other than $$1.$$ As usual we say $$m$$ is irreducible provided in any factorization $$m=ab$$ one of $$a,b$$ must be $$1.$$ Then an easy argument shows $$L(n)$$ is irreducible.

My question is why is there any need for more than continually applying the process of factoring out $$L(n)$$ and then going on, if the goal is only to show unique factorization into integers. It seems that at each stage of the outlined process there is only one way to continue, and the divisors come out in a non-decreasing order as usually stated in unique factorization theorems.

I'm probably missing something obvious, and would appreciate any light on this, since the usual method of first getting to Euclid's lemma etc. is what I learned and now am wondering if there is any sense in which it can be avoided.

• There are rings similar to $\mathbb Z$ , for which the factorization is not unique. Therefore the uniqueness is not so obvious as it seems. – Peter Jun 24 at 7:41

Your argument (iterating on factoring out the least nontrivial factor) only shows that for a given integer $$n > 1$$, there is at least one way to express $$n$$ as a product of irreducibles.

Without further reasoning, your argument doesn't show that every possible way of expressing $$n$$ as a product of irreducibles is the same, up to a permutation of the factors.

More concretely, your argument doesn't show that every possible way of expressing $$n$$ as a product of irreducibles has $$L(n)$$ as one of the irreducible factors.

As an example to illustrate the issue, let $$R$$ be the ring without $$1$$ given by $$R=\{4k{\,\mid\,}k\in\mathbb{Z}\}$$ and let $$n=64$$.

Then $$4$$ is irreducible in $$R$$, and if you apply the least factor method, you get the factorization $$64=4^3$$.

But $$8$$ is also irreducible in $$R$$, so the factorization $$64=8^2$$ is another way to express $$64$$ as a product of irreducibles.

• I can see from one point of view that my argument doesn't use the existence of a unit. I wonder whether there is another case like your example but where there is a unit in the ring and the ring has a natural ordering compatible with multiplication/addition. If you know that I'd appreciate info about it. Thanks. – coffeemath Jun 24 at 12:08
• @coffeemath: There are lots of examples of commutative rings with $1$ for which unique factorization fails, but the ones that come to mind don't come equipped with a natural well-ordering that respects addition and multiplication. Still, even if you had such an ordering, the least factor method, without further conditions on the ring (e,g,, a Euclidean-type algorithm or a Bezout-type theorem) doesn't seem strong enough to force unique factorization. – quasi Jun 24 at 12:31

Often students wrongly believe that integer factorization is unique because there is a deterministic algorithm for factorization: simply continue to pull out the least prime factor (found by trial division). To help them debunk this belief it suffices to show them another ring where a similar method fails. An elementary example is factoring (monic) quadratics with coefficients being integers $$\!\bmod m.\,$$ Here - as above - there is a simple deterministic factorization algorithm: simply test in order $$r\equiv 0,1,\cdots,m-1$$ till we find a root $$\,r\,$$ hence a factor $$\,x-r\,$$ (by the Factor Test).

But here factorizations need not be unique, e.g. $$\, (x-1)(x+1) \equiv (x-3)(x+3)\,\pmod{\! 8}$$

Applying the above algorithm we test if $$\,r\equiv 0,1,\cdots \,$$ is a root of $$\,x^2-1\,$$ and we find the root $$\,r\equiv 1,\,$$ yielding the factor $$\,x-1\,$$ with cofactor $$\,(x^2-1)/(x-1) = x+1.\,$$ If we (wrongly) believed such factorizations were unique we would not continue testing for other roots and we would stop there, missing the factorization $$(x-3)(x+3)$$.

This shows clearly and simply that the existence of a deterministic algorithm for solution does not imply that the solution is unique.

• A nice example [+1] Thanks for this. – coffeemath Jun 24 at 15:08

Finding $$L(n)$$ is one way to factor the number $$n$$. There might be other ways.

However, in the natural numbers there is essentially no other way, but this is a feature of the natural numbers and this must be proved! You'll see that induction has a fundamental role in the argument, but also Euclid's theorem: “if $$p$$ is prime and $$p\mid(ab)$$, then $$p\mid a$$ or $$p\mid b$$”.

The base case is easy: $$n=2$$ is a prime number, so its factorization is obviously unique. Suppose that unique factorization holds for every number $$m$$ with $$2\le m. If $$n$$ is prime, there's nothing to prove. Otherwise take a factorization of $$n$$ as a product of primes in nondecreasing order as provided by choosing each time the minimal divisor greater than $$1$$: $$n=p_1p_2\dots p_k,\qquad p_1\le p_2\le\dots p_r$$ Thus $$p_1=L(n)$$ by construction. Take another similar factorization $$n=q_1q_2\dots q_s,\qquad q_1\le q_2\le\dots q_s$$ We have $$q_1\ge L(n)=p_1$$, because $$L(n)$$ is minimum among the divisors of $$n$$ greater than $$1$$. On the other hand, $$p_1$$ is prime and so it divides one of the $$q_i$$, but then $$p_1=q_i$$ for some $$i$$. Thus $$q_1\le q_i=p_1$$ and therefore $$q_1=p_1$$.

Hence we can consider $$m=n/p_1=p_2p_3\dots p_k$$ and factorization is unique by the induction hypothesis. Therefore also the factorization of $$n$$ is unique (complete the details).

If we want a more general framework, namely integral domains, we have to waive full uniqueness in favor of “uniqueness up to multiplication by invertible elements”. Over the integers, we can take $$n\in\mathbb{Z}$$ with $$|n|>1$$ and consider a noninvertible divisor $$p$$ such that $$|p|$$ is minimal. The arguments above carry over easily.

But they don't in different cases: take $$R=\mathbb{Z}[\sqrt{-5}]$$. We can define, for $$z=a+b\sqrt{-5}$$, the norm to be $$N(z)=a^2+5b^2$$ and choose, among the noninvertible divisors one of minimal norm. It's easy to prove that such a divisor cannot be expressed as a product of two noninvertible elements (or its norm wouldn't be minimal). But Euclid's theorem doesn't hold in this case. Indeed we can write $$6=(1+\sqrt{-5})(1-\sqrt{-5})=(2+0\sqrt{-5})(3+0\sqrt{-5})$$ The norm of $$2=2+0\sqrt{-5}$$ is minimal, but $$2$$ divides neither $$1+\sqrt{-5}$$ nor its conjugate $$1-\sqrt{-5}$$. And the argument above fails here.

• My argument for the natural numbers uses that they are ordered. $\mathbb{Z}[\sqrt -5]$ does not have an obvious ordering which is compatible with multiplication and addition. – coffeemath Jun 24 at 12:05
• @coffeemath Also $\mathbb{Z}[\sqrt{5}]$ is ordered, but it is not a UFD. – egreg Jun 24 at 12:57