25
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 10
    $\begingroup$ 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. $\endgroup$
    – mweiss
    Dec 25, 2014 at 20:14
  • $\begingroup$ @mweiss You're right. Thanks. $\endgroup$
    – Behzad
    Dec 25, 2014 at 20:20
  • 5
    $\begingroup$ 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. $\endgroup$
    – Benjamin Dickman
    Dec 26, 2014 at 3:42

7 Answers 7

Reset to default
35
$\begingroup$

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)

Improve this answer
$\endgroup$
3
  • 10
    $\begingroup$ Simpler: $\ 441 = 9\cdot 49 = 21^2,\,$ i.e. $\ 3^2\, 7^2 = (3\cdot 7)^2\ $ is the classical example. $\endgroup$
    – Bill Dubuque
    Dec 26, 2014 at 1:45
  • 5
    $\begingroup$ 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}. $\endgroup$
    – Richard
    Dec 31, 2014 at 6:30
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Jun 29, 2015 at 20:13
22
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 1728, hmm, that's an interesting number. Wait, I mistook you for some other number... $\endgroup$
    – James S. Cook
    Dec 25, 2014 at 22:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – Daniel Hast
    Dec 25, 2014 at 23:13
  • $\begingroup$ Yeah, I wonder about that, I noticed 1728 a few places after reading the taxicab story. $\endgroup$
    – James S. Cook
    Dec 26, 2014 at 5:52
18
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you please reference the proof for that? $\endgroup$
    – yoniLavi
    Dec 26, 2014 at 21:31
  • 4
    $\begingroup$ @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). $\endgroup$
    – LSpice
    Dec 27, 2014 at 17:11
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – paul garrett
    Jun 28, 2018 at 19:42
1
$\begingroup$

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).

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Jun 27, 2018 at 20:10
  • $\begingroup$ @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. $\endgroup$
    – Buffy
    Jun 27, 2018 at 20:15
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Jun 27, 2018 at 22:48
  • $\begingroup$ @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. $\endgroup$
    – Buffy
    Jun 27, 2018 at 23:10
  • $\begingroup$ 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. $\endgroup$
    – Bill Dubuque
    Jun 28, 2018 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.