Unique Factorization: Concept and Counterexamples

1. The Crucial Distinction: Irreducible vs. Prime

In everyday language, and even in many introductory texts, the word "prime" is used for any number that cannot be broken down further. However, to truly understand unique factorization, we must be more precise. There are two distinct concepts:

• An integer $n>1$ is irreducible if it cannot be written as a product of two smaller integers $a,b>1$. This is our intuitive notion of a "prime" as an indivisible building block.
• An integer $p>1$ is prime if it satisfies the condition of Euclid's Lemma: whenever $p$ divides a product $ab$, it must divide at least one of the factors, $a$ or $b$.

In the familiar world of integers ($\mathbb{Z}$), our work in the previous module showed that these two concepts are equivalent. Because we have the Euclidean Algorithm and Bézout's Identity, we can prove Euclid's Lemma for any irreducible number. This equivalence is the very reason the Fundamental Theorem of Arithmetic holds.

The breakdown of unique factorization in other number systems occurs precisely when these two concepts diverge—that is, when a number system contains elements that are irreducible but not prime.

To analyze these systems, we need a few tools. The following article introduces the concepts of Units, Associates, and Norms, which are essential for rigorously checking whether a factorization is truly unique and whether its factors are truly irreducible.

2. A Gallery of Systems Without Unique Factorization

Let's now step into the looking-glass and explore some mathematical worlds where the Fundamental Theorem of Arithmetic does not hold. By examining these counterexamples, we can pinpoint exactly what goes wrong.

Example 1: The World of Even Numbers

Let's consider a very simple system: the set $E=\{2,4,6,8,\dots \}$ of positive even numbers. This set is closed under multiplication. What are the "primes" in this world? They are the numbers that cannot be factored into two other even numbers.

As the article shows, the "primes" in $E$ are numbers of the form $2k$ where $k$ is an odd integer (e.g., 2, 6, 10, 14, 18...). Let's look at the number 60. We can factor it in two ways within $E$:
$60=6\times 10$
$60=2\times 30$
Here, 2, 6, 10, and 30 are all "irreducible" in the world of even numbers. We have two distinct factorizations of 60 into irreducibles.

Why did this happen? Let's check Euclid's Lemma. The irreducible number 6 divides the product $2\times 30$. However, 6 divides neither 2 nor 30 within the system E (since $2/6$ and $30/6=5$ are not even numbers). So, 6 is an example of an element that is irreducible but not prime. The failure of Euclid's Lemma for the number 6 leads directly to the failure of unique factorization.

Example 2: The Ring $\mathbb{Z}[\sqrt{-5}]$

This is a classic and historically important example. Consider the set of numbers of the form $a+b\sqrt{-5}$, where $a$ and $b$ are integers. In the previous lesson's video, you saw a brief mention of this system. Let's examine it more closely.

As stated, we have two factorizations for the number 6:
$6=2\cdot 3=(1+\sqrt{-5})(1-\sqrt{-5})$
To be sure this is a genuine failure, we must confirm two things:

1. The factors on the right are not simply "associates" of the factors on the left (i.e., they are not just $2\times u$ or $3\times v$ where $u,v$ are units).
2. All four factors—$2,3,1+\sqrt{-5},1-\sqrt{-5}$—are themselves irreducible in this ring.

This is precisely the kind of analysis you read about in the article "Unique and Non-unique Factorization". The norm of an element $a+b\sqrt{-5}$ is $N(a+b\sqrt{-5})=a^2+5b^2$.

• $N(2)=4$
• $N(3)=9$
• $N(1+\sqrt{-5})=1^2+5(1^2)=6$
• $N(1-\sqrt{-5})=1^2+5(-1{)}^2=6$

Since the norms are different, 2 and 3 are not associates of $1\pm \sqrt{-5}$. To show 2 is irreducible, we would need to find factors whose norms multiply to 4. If $2=xy$, then $N(2)=N(x)N(y)=4$. The only way this could be a non-trivial factorization is if $N(x)=2$. But the equation $a^2+5b^2=2$ has no integer solutions for $a$ and $b$. Thus, no element has a norm of 2, and 2 must be irreducible. A similar argument holds for the other factors.

Again, the failure can be traced to an irreducible element that is not prime. The irreducible element 2 divides the product $(1+\sqrt{-5})(1-\sqrt{-5})$, but it does not divide either factor in this ring.

3. The Consequences: Why Uniqueness Matters

Having seen how factorization can fail, we now ask: what are the practical and theoretical consequences?

Practical Chaos: The Ambiguity of Simplification

The PolyaMath video you started in the last lesson provides a brilliant and intuitive illustration of the problems that arise when factorization is not unique.

This simple example reveals the chaos that non-uniqueness introduces. Basic operations we take for granted, like reducing a fraction to its single "simplest form," become impossible. The very concept of "canceling common factors" becomes ambiguous if the factors themselves are not uniquely defined.

Conceptual Power: A Pillar of Modern Number Theory

The FTA is not just about avoiding ambiguity; it is a foundational tool for building new mathematical ideas. One of the most beautiful examples is Euler's product formula for the Riemann zeta function, which connects a sum over all natural numbers to a product over all prime numbers.

Euler's argument rests entirely on the fact that every integer $n$ can be formed in exactly one way by multiplying together powers of primes. If an integer could be formed from two different sets of prime powers, the one-to-one correspondence between the terms of the sum and the terms of the expanded product would break down, and the formula would not hold. This demonstrates that the FTA is not merely a curious property but a load-bearing pillar supporting some of the deepest results in mathematics.

Conclusion

In this lesson, we have explored the conceptual space around the Fundamental Theorem of Arithmetic. By venturing into number systems where it fails, we have gained a much deeper appreciation for its significance.

Key Takeaways:

• The property of being prime (satisfying Euclid's Lemma) is stronger than being irreducible (unfactorable). In $\mathbb{Z}$, they are equivalent, which is why unique factorization holds.
• In systems where unique factorization fails, it is because there exist elements that are irreducible but not prime.
• The consequences of this failure are profound. At a practical level, it introduces ambiguity into fundamental operations like simplifying fractions. At a theoretical level, it removes a critical tool used to build advanced results, such as Euler's product formula.
• The FTA is "fundamental" because it establishes a rigid, predictable, and reliable structure for the integers, which we can then use to reason about them with certainty.

Now that we have a deep appreciation for the structure that unique prime factorization provides, we can begin to use it as a powerful problem-solving tool. In our next lesson, we will do just that, applying the FTA to derive formulas for the number of divisors and the sum of the divisors of an integer—a classic topic in Olympiad number theory.