Mathematics
Unique and Non-unique Factorization
--
Let’s begin with an illustration. Of (non)unique factorization. Consider the following factorizations of 24:
24 = 8 x 3
24 = 12 x 2
24 = 6 x 4
Three sets of factorizations with different sets of factors in each case. So, the factorization of 24 is not unique? It can be done in more than one way? Hmm. But some of those factors can be broken down further, like 6= 2 x 3. Let’s just break down all the factors into the most elementary factors possible - into prime factors, and see how it goes:
24 = 2 x 2 x 2 x 3
24 = 2 x 2 x 3 x 2
24 = 2 x 3 x 2 x 2
Now, we see that the factorizations are made up of the same set of numbers, though the arrangement differs, but it doesn’t matter since we are working in a commutative ring, Z. We can just take any one of them;
24 = 2 x 2 x 2 x 3, this is the only way 24 can be expressed as a product of prime factors.The factorization can now be said to be unique.
Does unique prime factorization hold for all integers? It seems an obvious fact, but let’s try to prove it, we need two facts about prime numbers to do this.
Fact 1. A prime number has just itself and 1 as factors. This is just the definition of a prime number, nothing extraordinary.
Fact 2. If a prime number, say p, divides another number, say N, then p also divides a factor of N. This is a simple but very crucial property of prime numbers. We are not going to prove it now but you can check with some examples, for instance, 7 divides 35, and 7 divides 7, a factor of 35.
Now, to the proof of unique prime factorization.
First, assume unique prime factorization does not hold, let there be an integer N, that has two different sets of factorizations:
N = P₁ x P₂ x P₃ x … x Pᵢ
N = Q₁ x Q₂ x Q₃ x … x Qⱼ
The Pᵢ’s and Qⱼ’s are prime factors.
Since P₁ is a factor of N, it divides N. And since N = Q₁ x Q₂ x Q₃ x … x Qⱼ,
P₁ divides one of Q₁, Q₂, Q₃, … ,Qⱼ (by Fact 2 above). Without loss of generality, we can assume P₁ divides Q₁, but Q₁ = Q₁ x 1 (being a prime number - Fact 1), that implies Q₁ = P₁. By the same argument, we can show that Q₂ = P₂, Q₃ = P₃, … , Qⱼ = Pᵢ(with i=j). So, the two sets of factorizations are really the same, therefore unique prime factorization holds for any integer N. Quod Erat Demonstrandum.
Paradise Lost
We’ve just established the uniqueness of prime factorization in the ring of rational integers, Z. Let’s see what happens in other rings, particularly rings of integers in quadratic field extensions, but before then let’s introduce some useful notions.
Units and Associates
A unit is an element of a ring that has a multiplicative inverse in the ring. In the familiar ring of integers, Z, the units are 1 and -1.
An associate of an element is the element multiplied by a unit. E.g. the associate of 5 is -1 x 5 = -5.
Two sets of factorizations are considered the same if the factors in one set are associates of the factors in the other set.
15 can be prime-factorized in two seemingly different ways; 5 x 3, and -5 x -3.
The two sets of prime factors are different, does that mean there is a breakdown of unique factorization here? Not really. The two factorizations are counted as equivalent - because they are made up of associates.
Norm
There is no sense of magnitude and order among the numbers in field extensions such as exist among the rationals; how do you arrange the numbers 3 - 2√-5, 1 + 4√-5, 7 - 6√-5, for example, in order of size. Norm is a function that provides some sense of magnitude to such numbers. The norm of a quadratic integer a + b√c is defined as:
N(a + b√c) = (a + b√c)(a - b√c) = a² - cb².
Norm is a multiplicative function; the norm of a product of two or more numbers equals the product of the individual norms.
N(A x B) = N(A) x N(B). This property of norms helps identify units in number rings. If u is a unit of a ring, then by definition, there exists an element, v, in the ring such that uv = 1. Taking norms on both sides, we have;
N(uv) = N(1) = 1² - 0²c = 1. And by the multiplicative property of norms;
N(uv) = N(u) x N(v) = 1. This implies both N(u) and N(v) are 1 or -1.
Therefore to test if an element of a ring is a unit, check if it’s norm is 1 or -1.
Now, to the Paradise Lost part.
We state some instances where unique factorization seems to fail.
(i) In the ring of integers of the quadratic field extension Q(√10), 6 can be factored in two apparently different ways:
2 x 3 = (4 + √10)(4 - √10)
(ii) In the ring of integers of the quadratic field extension Q(√-5), 21 can be factored in two apparently different ways:
3 x 7 = (1 + 2√-5)(1 - 2√-5)
Before drawing conclusion that the factorizations are not unique, we need to show first that the factors involved are not associates, and that they cannot be factored further in the ring.
From the definition, if A and B are associates, then A = u x B, where u is a unit. Taking norms;
N(A) = N(u x B) = N(u) x N(B) = 1 x N(B) = N(B).
N(A) = N(B) implies if two numbers are associates, their norms must be equal, so, to check if the factors are associates, check if their norms are the same.
In case (i); N(2) = 4, N(3) = 9, N(4 + √10) = 6, N(4 - √10) = 6. The norms on both sides do not match up, therefore the factors are not associates. You can check for case (ii).
Next, we need to show that the factors, cannot be factored further, i.e., irreducible.
In case (i), let’s check if the factor 2 is irreducible or not. Assuming 2 can be factored further as 2 = pq in the ring, then taking norms, we have;
N(2) = N(pq) = N(p) x N(q).
4 = N(p) x N(q).
There are four possibilities;
(i) N(p) = 2, N(q) = 2
(ii) N(p) = -2, N(q) = -2
(iii) N(p) = + or -1, N(q) = + or -4
(iv) N(p) = + or -4, N(q) = + or -1
In (iii) and (iv), p and q are units respectively(norm equals 1), that implies, between the two cases, 2 is irreducible, which is what we wanted to prove
(2 = p x 1, or 2 = q x 1 means 2 is irreducible - Fact 1).
We still have cases (i) and (ii) left. In (i) the norm is 2. Let there be an element of Q(√10), a + b√10, such that N(a + b√10) = 2, this implies a² - 10b² = 2, similary, from (ii) we have a² - 10b² = -2. These two diophantine equations can be reduced modulo 5 to a² ≡ 2 (mod 5) and a² ≡ 3 (mod 5), both of which have no solution since a square can only have a residue of 0 or 1 or 4 modulo 5, never 2 or 3.
So, only cases (iii) and (iv) where 2 is irreducible is possible. You can apply the same method to check that all the other factors are irreducible too. In conclusion, unique factorization has failed in the stated rings.
Note that we are careful to use the term irreducible here, and not prime, an element of a ring can be irreducible without being prime. An irreducible element satisfies Fact 1 only, not Fact 2. Paradise Regained
So, we’ve lost the paradise of unique factorization, the fundamental theorem of arithmetic! Well,…
It did not last: an angel singing ‘Ho!
Let Kummer be!’ restored the status quo.
Just kidding. But the German mathematician Ernst Kummer did try to restore unique factorization by introducing what he called ideal numbers. Pretty similar to what we did at the beginning, Kummer observed that irreducible elements sometimes behave as if they could be factored further and he invented ideal numbers to act as these imaginary factors. For example, in the first instance of nonunique factorization above, Kummer’s idea was to come up with symbols β₁, β₂, β₃, β₄ such that:
2 = β₁ x β₂
3 = β₃ x β₄
4 + √10 = β₁ x β₃
4 - √10 = β₂ x β₄
Then the nonunique factorization:
2 x 3 = (4 + √10)(4 - √10)
becomes unique with the ideal factors β₁, β₂, β₃, β₄:
(β₁ x β₂) x (β₃ x β₄) = (β₁ x β₃) x (β₂ x β₄)
Same set of factors on both sides, just that the arrangement differs, which doesn’t matter.
Exercise : Try to work out the ideal numbers factorization of instance (ii) of nonunique factorization above.
Just like their name implies, ideal numbers only existed as a concept with Kummer, it was another mathematician Richard Dedekind who gave a more concrete realization of the concept in terms of subsets of rings of integers. That will be a topic for another day.
