5. Exploring Unique Factorization

Following is a brief history of the Unique Factorization Theorem (UFT), aka Fundamental Theorem of Arithmetic: Any integer {> 1} has a unique representation (up to ordering) as a product of primes. There are two concepts underlying UFT, existence (every composite number can be decomposed into purely prime factors) and uniqueness (each number’s prime decomposition is unique). The UFT is usually expressed in terms of uniqueness, but it relies on prior proof of existence. Below, we explore UFT through the eyes of Euclid and Gauss.

The UFT is central to understanding the prime numbers as the ‘essential’ natural numbers. But lest we think of the UFT as universal, there are number systems for which UFT does not apply. A number system in which UFT holds is called a Unique Factorization Domain (UFD)*. Hardy calls the UFT `the foundation of systematic arithmetic’. Divisibility and the related concepts GCD and LCM are well-defined in a UFD. Many results in arithmetic, such as the Chinese Remainder Theorem and the Euler Product Theorem, depend on UFT.

Plato’s Academy pursued the first systematic investigation of the prime numbers, recorded in Euclid’s Elements. Yet it was 2000 years later that Gauss formalized a modern mathematical proof of the uniqueness part of UFT. It has been speculated that until Gauss, mathematicians accepted UFT more or less as an axiom. But Gauss showed that other number systems were not UFDs. Since UFT could no longer be universally assumed, rigor demanded a formal proof of UFT from the axioms of arithmetic. Gauss was able to do so, referring obliquely to Euclid’s existence demonstration, then providing a simple argument for uniqueness. It seems so simple that many before Gauss must have understood this, but Gauss may be the first one who saw the necessity to write it down.

Euclid’s Elements are just that, primitive statements expressing atoms of mathematical meaning (the same Greek word elements describes the letters of the alphabet, analogous language primitives). How the reader assembles various meanings into a rational argument in support of some greater generality was not specified by Elements.

Elements is divided into books. Books VII-IX are devoted to the study of Pythagorean number theory and primes in particular. Here, magnitudes are commensurables, multiples of a unit magnitude. Thus, these propositions study whole numbers, whereas the perhaps more modern Book V deals with Eudoxean proportion, suitable for studying incommensurables.

Elements contains several practical arguments regarding prime factorization, esp. Propositions VII:30, VII:31, and IX:14. Those in turn reference earlier propositions, particularly VII:20, VII:19, and VII:13. And ultimately, VII-2, the Euclidean Algorithm underlies all. When reading Elements books VII-IX, realize that in Euclid’s day, magnitudes refer to the natural numbers beginning with 1, which were understood geometrically as lengths of measurable line segments. Measurement is analogous to division; if {a} measures {b}, then {b=na}, and so {a|b}. A lesser quantity is parts of a larger quantity if it does not measure the larger (divides with remainder). But the lesser is a part of the larger if it measures the larger (divides).

Conway believes that the Euclideans understood the concept of unique factorization, for such intuition is a small step beyond what is explicitly expressed in Elements. But a proof of the entirety of UFT was beyond the scope of Elements, if perhaps not beyond the ability of the Pythagoreans. Here are the three Propositions referenced above, which seem to argue in support of this belief. The proofs are Euclid’s proofs, here expressed in modern notation. This is a tricky change of mind set, deprecated by some mathematicians. Not being a mathematician, I choose to use it as a convenience for exploring the basic intent.

1. Euclid’s First Theorem (aka Euclid’s Lemma) (Proposition VII:30): If two numbers by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers.

Proofs of UFT assert this Euclid Lemma, as does proposition (3) below.

[Note: I had problems with Euclid’s proof and had to do some research to get help. Below I simply state my interpretation of Euclid’s proof, and refer to the footnote** for a paper that explains the entire proof and further provides an update for an incomplete Euclid proof of a subordinate proposition.]

Let integer product {ab} be divisible by prime {d}. Then {d|ab} implies {d|a} or {d|b}. By hypothesis, {a:d=e:b} for some {e}. Also by VII:19, {\dfrac{a}{d} = \dfrac{e}{b}}.

Assume {d \nmid a}, so {(a,d)=1}. We must then show {d|b}. We use VII:20, which shows that if {a} and {d} are the least values for which {a:d=e:b}, then {a|e} and {d|b}. First, observe that VII:13 (Alternando Rule) shows {a:e = d:b} , and then by Def. VII:20, there are integers {x}, {y}, {m}, and {n} such that {a=mx}, {d=my}, {e=nx}, {b=ny}. Hence by definition, there is a common factor {n} in both {e} and {b}. [Note:The part I didn’t find for myself was this use of VII:13 together with the algebraic statement of Def. VII:20; once I saw it, the proof made sense.]

Note from the definition above that {a|e \Longleftrightarrow m=1}. To prove VII:20, assume {a \nmid e}. Then {a=m\dfrac{e}{n}}, {m>1} (i.e. {a} contains {m} copies of {\dfrac{e}{n}}). Similarly {d=m\dfrac{b}{n}}, because {a} is the same parts of {e} as {d} is of {b}. Since {m>1}, {\dfrac{e}{n}<a} and {\dfrac{b}{n}<d}. Since {\dfrac{e}{n}:e=\dfrac{b}{n}:b}, then {\dfrac{e}{n}:\dfrac{b}{n}=e:b}, contradicting the hypothesis that {a} and {d} are the least integers in the same proportion. Thus {a|e} and {d|b}.
{\hfill \mbox{\raggedright \rule{.07in}{.1in}}}

2. Euclid’s Proposition VII:31 (existence of prime factors): Any composite number is measured by some prime.

Let {a} be a composite number measured by {b}. Write {a=mb}. If {b} is prime, we are done. Else, {a=mnc}. If {c} is prime we are done, else one continues until a prime factor is discovered. If no such prime is discovered, then an infinite number of decreasing integer divisors of {a} must exist, an impossibility.
{\hfill \mbox{\raggedright \rule{.07in}{.1in}}}

Note this Proposition is as close as Euclid comes to the existence part the of prime factorization of any composite number. It discovers the germ of meaning from which the entire story can be developed. One intuits that simply repeating the above argument for all discovered factors of {a} {(m, n,...)} will surely construct a purely prime factorization of {a}. The primes will not necessarily be distinct.

3. Euclid Proposition IX:14 (uniqueness of prime factorization – limited context): If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it.

Let {b, c, d} be primes and let {a = bcd} where {a} is the least integer measured by {b}, {c}, and {d}. Then there can be no other prime {e}, distinct from {b, c, d}, that is a factor of {a}. For let {a = fe}. By Euclid’s Lemma above, since {b}, {c}, and {d} are factors of {a}, they must also be factors of either {f} or {e}. But by definition, they do not divide {e}. Hence they must be factors of {f}. But {f<a}, contradicting that {a} was the least such integer.
{\hfill \mbox{\raggedright \rule{.07in}{.1in}}}

Here Euclid assembles a limited uniqueness theorem. He proves the lcm of some number of primes can have no other divisors except those primes. This is essentially a corollary to VII:30. The proof is correct even when the selected primes are not distinct. What isn’t proved is that the counts of occurrences of non-distinct primes in a factorization are also unique. This is the only piece of the UFT proof that Gauss would add.

Next we look at Gauss’ proof of UFT over the integers, as presented in Disquisitiones Arithmeticae in 1801. Gauss credits Euclid for the original proof of the essential Euclid Lemma, but states a need to reassert the proof in modern terms both to combat `feeble arguments’ (laziness) expressed by others up to then, and also so that `by this very simple case we can more easily understand the nature of the method which will be used later for solving much more difficult problems.’ [Note: Gauss himself reported no error in Euclid’s proof.] Gauss proves the contrapositive of the Lemma, in two parts.

(13) THEOREM. The product of two positive numbers each of which is smaller than some given prime number cannot be divided by the prime number.

Let prime {p} and {0<a<p}. Then there is no {b}, {0<b  1}, because {p \nmid a}. Thus there is some m such that {mb < p < (m+1)b}. Let {\bar{b}=p-mb} and observe {0<\bar{b}<b}. One must show {a\bar{b} \equiv 0 \pmod p}, which is evident because by assumption, {mab \equiv 0 \pmod p} and {ap \equiv 0 \pmod p}; subtracting gives {a(p-mb) \equiv 0 \pmod p}. But {\bar{b} < b} is smaller than the least of the {b_i}, a contradiction.
{\hfill \mbox{\raggedright \rule{.07in}{.1in}}}

(14) THEOREM. If neither {a} nor {b} can be divided by a prime {p}, then {ab} cannot be divided by {p}.

Assume {ab \equiv 0 \pmod p} and derive a contradiction. Let {a \equiv \alpha \pmod p} and {b \equiv \beta \pmod p} and assume these are the least positive residues ({\alpha < p} and {\beta<p}). Neither residue is {0} by hypothesis. But {ab \equiv \alpha\beta \pmod p}, implying {\alpha\beta \equiv 0 \pmod p}, a contradiction with (13).
{\hfill \mbox{\raggedright \rule{.07in}{.1in}}}

Essential preliminaries aside, Gauss arrives at the heart of the matter. The existence part of the UFT is assumed from `elementary considerations’, which we may take to mean Euclid’s approach. He states that UFT uniqueness `is often wrongly taken for granted’. To prove uniqueness, he assumes two prime decompositions of a composite number can be resolved differently and derives a contradiction.

(16) THEOREM. A composite number can be resolved into prime factors in only one way.

To begin, Gauss states that clearly, both representations must consist of only the same primes with different powers, for by assumption no other prime is allowed to divide the number except the primes in its original decomposition. Why is no other prime allowed to divide our number? Euclid’s Lemma, Theorem 14 above, proscribes it. Hence if {k=\prod{p_i}} and {\bar{p}} is different from all {p_i}, then {\bar{p} \nmid p_i} for any {i} and hence {\bar{p}\nmid k}.

To create his contradiction, Gauss assumes at least one prime {p} appears in one decomposition {m} times and one {n} times, {m>n}. Then by dividing each decomposition {n} times by {p}, it is eliminated from one decomposition, but remains in the other {m-n} times. But this contradicts the prior assertion that all decompositions of a composite number must contain the same set of primes.
{\hfill \mbox{\raggedright \rule{.07in}{.1in}}}

* What distinguishes a UFD from a number system in which UFT does not hold? The answers are found in the study of commutative algebra; a property called integral closure is a requirement for a UFD. One naturally questions what is missing from arithmetic within non-UFD number systems. Looking at examples of non-UFD systems, the even integers are not closed under division and have no multiplicative unit. The Hilbert device, numbers of the form 4n+1, are not closed under addition (interesting that additive closure might be necessary even though the UFT is a multiplicative property). The referenced paper** points out two other such non-UFD number systems, the monoid consisting of all integers {n \equiv 1 \pmod 3}, and the semi-ring of reals of the form {a+b\sqrt{5}}, {a} and {b} non-negative integers not both {0}. For both systems, the transitive property of equality derived from Pythagorean proportion is shown not to hold. One senses the implications of the UFT run deep.

** I discovered that Euclid scholars have been dissecting Euclid’s Lemma for decades. The paper `Did Euclid Need the Euclidean Algorithm to Prove Unique Factorization?’ (David Pengelley and Fred Richman, AMA Monthly No. 113, March 2006, pp. 196-205) suggests Euclid does not quite prove it completely, then provides analysis of what is technically wrong and a proposal to fix it. Modern proofs of this Lemma utilize the Euclidean algorithm and its additive operation. But Euclid’s proof appears to have been purely multiplicative. The part that Euclid is said to have flubbed is the proof of VII:19 (involving Pythagorean proportion as defined in Def. VII:20): {a:b=c:d \Longleftrightarrow ad=bc}. The equality was assumed to be transitive, but was not proved. To be complete, Proposition VII:19 requires use of the Porism from Proposition 2 (Euclidean Algorithm). Davenport (Higher Arithmetic, pp. 20-21) suggests that any correct proof of UFT must utilize additive properties. Perhaps he anticipated the findings in the paper above. On a not directly related note, Weil observed that in Euclid `the ratios of magnitudes are treated as a multiplicative group operating on the additive group of the magnitudes themselves’ (unbeknownst to Euclid of course).


Comments Welcome

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s