# A Non-Unique Factorization of Integers!

I'm going to introduce my students to the fundamental theorem of arithmetic (uniqueness of integer factorization to prime factors), and I don't want them to take the uniqueness for granted! To make my students understand that the uniqueness is not trivial by any means, I'm looking for a non-unique factorization of integers. What factorizations do you suggest?

I have a suggestion myself, but it's definitely not the best one: Suppose that Goldbach's conjecture is true. So every integer can be written as the sum of at most 3 primes, but this factorization is not unique!

• I gather that you are using italics to indicate that you don't mean to use the word factorization literally, but rather that you are seeking something that is "like" factorization, but not unique. If that is what you mean, I would suggest using a word like "decomposition". "Factorization" means something specific, and I don't think you are doing your students any favors by using that word for decompositions that are not factors. – mweiss Dec 25 '14 at 20:14
• @mweiss You're right. Thanks. – Behzad Dec 25 '14 at 20:20
• Related idea: Start with a composite number and use a factor tree to find its prime factors. As you move down the tree, you get lots of different factorizations. But only the very top of the tree (i.e. the original number) and the very bottom (the end of the roots i.e. the prime factors) will necessarily be the same - this being precisely the content of the FTA! Do this for each number (let them choose the starting numbers, if they want) in a bunch of different ways; this gives lots of factorizations, and helps students see the uniqueness feature empirically. – Benjamin Dickman Dec 26 '14 at 3:42

A really nice example is factorization of the Hilbert numbers - that is the numbers $$1,\,5,\,9,\,13,\,17,\,\ldots,4n+1,\,\ldots.$$ Now, we can talk about factoring in this domain too - for instance, $45=5\times 9$ is a factorization of $45$. Moreover, $5$ and $9$ are both "Hilbert Primes" - they are not the product of two other Hilbert numbers - meaning that this factorization cannot be further reduced.

This looks very similar to factoring an integer. Except - surprise! - it's not unique: $$1617=21\times 77=33\times 49$$

(I encountered this example in the book In Code by Sarah Flannery)

• Simpler: $\ 441 = 9\cdot 49 = 21^2,\,$ i.e. $\ 3^2\, 7^2 = (3\cdot 7)^2\$ is the classical example. – Bill Dubuque Dec 26 '14 at 1:45
• Other numbers have the same effect. {3n+1}: 10*22 = 4*55 = 220 is smaller than the above examples. {5n+1}are much easier to work with (end in 1 or 6) and has 6*91 = 21*26 = 546. {2n+1}numbers have unique factorisations, as do {ZZ - 3n}. – Richard Dec 31 '14 at 6:30
• Simpler $\ 4\!\cdot\! 25 = 10^2,\,$ i.e. $\,2^2 5^2 = (2\!\cdot\! 5)^2,\,$ and $\ 6\!\cdot\! 56 = 21\!\cdot\! 16,\,$ i.e. $\,(2\!\cdot\! 3)(7\!\cdot\! 8) = (7\!\cdot\! 3)(2\!\cdot\! 8).\$ Such number systems arise naturally as normsets of quadratic number rings. Because the norm map is multiplicative, it preserves many properties related to factorization. For example, in many favorable contexts (e.g. Galois) a number ring enjoys unique factorization iff its monoid of norms does. See here for further discussion, including literature references. – Bill Dubuque Jun 29 '15 at 20:13

Integer factorization itself isn't unique: for example, $6 \cdot 2 = 4 \cdot 3$. The remarkable theorem is that there is only one factorization (up to reordering and sign) in which all the factors are prime.

Or, you could give an example where unique factorization into irreducibles genuinely fails. If we look at numbers of the form $m + n \sqrt{10}$, where $m$ and $n$ are integers, then we don't have unique factorization. For example, $2 \cdot 3 = 6 = (4 + \sqrt{10}) \cdot (4 - \sqrt{10})$.

(As a side note, the latter situation is important in the history of number theory. Dedekind's theory of "ideal numbers", which led to much of modern algebraic number theory, was motivated by trying to recover some sort of unique factorization in such rings. Such failures of unique factorization are closely related to why Kummer was unable to prove Fermat's Last Theorem in full generality, and it's plausible that the error in Fermat's own claim of a proof was due to incorrectly assuming that cyclotomic fields always have unique factorization.)

Here's another illustrative example: There isn't a good notion of "prime factorization" in the rational numbers or real numbers (or more generally, in any field): everything but zero is invertible, so we get "factorizations" like $5 = \frac{5}{1728} \cdot 1728$. This shows that some failure of invertibility of multiplication is required for an interesting notion of factorization, which explains why we don't pay attention to scalar factors when factoring polynomials with real coefficients. Similarly, we can factor $6$ as $(-2) \cdot (-3)$, but we don't consider this to be a breakdown of unique prime factorization because $-1$ has a multiplicative inverse in the integers.

• 1728, hmm, that's an interesting number. Wait, I mistook you for some other number... – James S. Cook Dec 25 '14 at 22:44
• @JamesS.Cook: Were you thinking of the taxicab number 1729? I tend to pick 1728 when I need an arbitrary integer because of its appearance in the $j$-invariant. I don't know whether their proximity is a coincidence. – Daniel Hast Dec 25 '14 at 23:13
• Yeah, I wonder about that, I noticed 1728 a few places after reading the taxicab story. – James S. Cook Dec 26 '14 at 5:52

You can restrict to subsets of the integers to get nice examples of structures that do not have unique factorization.

For example, take the set of all natural numbers, or integers it does not really matter, that are congruent to $1$ modulo $4$. This is a semigroup with identity under multiplication, and every element is the product of irreducible elements. However, factorizations into irreducible elements are not unique in an essential way. For example, you have: $$21 \cdot 21 = 9 \cdot 49$$ and $9,21,49$ are irreducible in that structure as their divisors are $3$ modulo $4$.

This structure is sometimes called Hilbert semigroup as he used (it is said) this as instructional example. (Added: this is also mentioned in another answer that appeared while I was writing this.)

Another possibility would be to consider only the even integers (and $1$). Again you have a factorization into irreducible elements, but it is not unique; $$42 \cdot 2 = 6 \cdot 14$$

Still another one would be to consider all integers greater than $2$ (and $0$) in this case with addition as operation. The only two irreducible elements are $2$ and $3$ and one has non-unique factorizations:

$$2+2+2 = 3 + 3$$

The above is an example of a numerical semigroup. If you do not like this is additive, you can instead consider polynomials that do not have a linear term.

I am not sure if this is relevant in your context, but if you want you could continue to use some of these examples in more advanced contexts. For instance, the Hilbert semigroup is contained in the (odd) natural numbers and that structure has unique factorization. This situation is analogous, in fact not just analogous but in a suitable sense littelraly the same, as one encounter when studying factorizations into ideals to restore unique factorization in algebraic number theory.

• Simpler: $\ 2\cdot 18 = 6^2\$ in the second example. – Bill Dubuque Dec 26 '14 at 1:54
• I meant to recall the Answer to the Ultimate Question of Life, the Universe, and Everything. – quid Dec 26 '14 at 1:58
• Re: prior remark: when teaching number theory it is wise to avoid (like the plague) anything remotely resembling "numerology". – Bill Dubuque Jun 29 '15 at 15:57

You can "factor" every positive integer into a sum of distinct Fibonacci numbers. This is not unique. However, it is unique if you add the condition that no two summands are adjacent Fibonacci numbers.

• Could you please reference the proof for that? – yoniLavi Dec 26 '14 at 21:31
• @yoniLavi, cut-and-pasted from MathSciNet: Zeckendorf, "Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas", Bull. Soc. Roy. Sci. Liège 41 (1972), 179–182 (ams.org/mathscinet-getitem?mr=308032). – LSpice Dec 27 '14 at 17:11

I know this might be perhaps be too advanced, but perhaps you can look at other integer-like structures, (non unique factorization domains) like e.g. the classical counterexample $\mathbb Z[\sqrt{-5}]$ where $6= 2 \cdot 3= (1+\sqrt{-5})(1-\sqrt{-5})$ (which are all primes). Perhaps someone can come up with another example, but I fear this is the simplest one.

• I think this is the simplest natural example, as opposed to contrived examples, that no one would necessarily care about except exactly to contrive something more elementary. My problem with contrived counter-examples is that they may be persuasive in the wrong direction, e.g., people may conclude that failure of unique factorization is itself contrived and artificial, and that in all natural examples unique factorization does hold... So I vote for the $\sqrt{-5}$ example. – paul garrett Jun 28 '18 at 19:42

In addition to the $\sqrt{-5}$ example, there is also the $R=\mathbb Z[\sqrt{-3}]$ example, which fails to be unique factorization for the "secret" reason that it is not integrally closed: we should really adjoin $\omega={-1+\sqrt{-3}\over 2}$, and then we have a Euclidean ring. A virtue of this example is that the details of non-unique factorization in $R$ can be studied "externally" by using the integral closure. (And that integral closure has finitely-many units, etc., so it is hardly more complicated than $\mathbb Z$).

On the other hand, the $\sqrt{-5}$ example has the virtue that there is no "easy fix" to the non-uniqueness (apart from switching over to factorization into ideals).

If you use $*$ as multiplication modulo 6 you get very strange behavior. The only non-negative "prime" is 5. All other numbers are composite. Even zero is $2 * 3$. But with only one prime, unique decomposition into primes has no real meaning. Also $3 * 3 = 3$ and $3 * 5$ is also $3$. That isn't a prime decomposition, of course. Some numbers in this situation have no prime decomposition at all.

You can either interpret this as multiplication over [0..5], or as over the integers with $=$ meaning "equivalent to". i.e. $15 = 5$

This isn't exactly what you asked for, but can motivate the fundamental theorem in a parallel way.

• Beware that factorization is much more complex in rings with zero-divisors, where basic notions such as associate and irreducible bifurcate into many inequivalent notions (e.g.see here). This leads to multiple notions of unique factorization. In your example $5\equiv -1$ is a unit (invertible) so it is neither prime nor irreducible. It is probably best not to broach such complexity until students have further background. – Bill Dubuque Jun 27 '18 at 20:10
• @Number, yes, and so I put "prime" in quotes. Not-composite would be better, of course. I'm not sure I agree with you about introducing the integers mod 6, though. You don't need to give a complete treatise on them, or even introduce the terms Group or Ring. But the complete multiplication table is trivial to show so the example of something "similar" to the integers that doesn't have a fundamental theorem is pretty easy to demonstrate. This can show the importance of it in the Integers. – Buffy Jun 27 '18 at 20:15
• The matter is more complex than it may appear at first glance. You haven't defined what you mean by "prime" so it does not make sense to claim that it "doesn't have a fundamental theorem". Even algebraists don't agree on how such notions should be generalized to rings with zero divisors. See the citations in the link I gave to learn more. – Bill Dubuque Jun 27 '18 at 22:48
• @Number, I'm not disputing that. The question tag is secondary-education. I was trying to frame something that would be easily understandable at that level without going deeply into the details. I thought I put sufficient caveats into my answer. I didn't intend, nor would I, at this level try to teach algebraic number theory to HS students when teaching them about unique factorization. It is enough, IMO, to show that there are systems in which it doesn't work. I interpreted the question of the OP to be seeking that, just as much as the explicit question. Read my final sentence in the answer. – Buffy Jun 27 '18 at 23:10
• What you wrote in the answer is mathematically meaningless without any definition of "prime" (or irreducible), "fundamental theorem", etc in the more general case of rings with zero-divisors (as in your example $\Bbb Z/6 =$ integers $\!\bmod 6).$ As I mentioned, there are various inequivalent ways to generalize these notions to such rings hence there is no unique denotation for such notions in this more general context. I know these matters well and I cannot make any sense of what you wrote in the answer. It is never wise to attempt to teach things that you do not know well. – Bill Dubuque Jun 28 '18 at 0:31