Unique factorization

In mathematics, the unique factorization theorem, also known as the fundamental theorem of arithmetic states that every positive whole number can be expressed as a product of prime numbers in essentially only one way. For instance, 12=2x2x3, and 2 and 3 are prime numbers. In addition, if you manage to factor 12 into primes again, the only possibility is that there are three factors, two of them being 2 and one being 3 as above.

Unique factorization allows us to consider the prime numbers as "atoms" from which all other whole numbers can be assembled through multiplication. Unique factorization is the foundation for most of the structure of whole numbers as described by elementary number theory. For instance, the assumption that many electronic financial transactions are secure is based on the belief that the product of two very large prime numbers is difficult to factor. If several other prime factorizations were possible, perhaps some having small prime factors, finding a factorization might be much easier and such security methods would be ineffective.

Applications

Unique factorization imparts useful structure to the whole numbers. For instance, it guarantees that any two positive whole numbers have a greatest common divisor (gcd) and a least common multiple(lcm). In fact, knowing the prime factorization of two numbers makes it much easier to find their gcd and lcm than not knowing. Also, unique factorization is implicit in the statement of many results, such as the Chinese remainder theorem.

History

A result about unique factorization appeared in book IX of Euclid's Elements. However, and it did not apply to all whole numbers.

The unique factorization property of the integers was implicitly understood by many intervening mathematicians, but most mathematics historians ascribe the first precise statement and proof this property to Carl Friedrich Gauss about 2000 years after Euclid. A precise statement and proof may be found on the "advanced" subpage.

Several factors contribute to the huge amount of time between the results of Euclid and Gauss. First, many mathematicians probably considered this to be an axiom of the integers that did not require proof -- it was intuitively obvious to them. Second, a precise proof of the property from more fundamental principles is surprisingly difficult, so the mathematical abilities of many mathematicians before Gauss would not have been enough to produce a proof. Third, in his advanced work, Gauss encountered systems of "numbers" like the integers for which unique factorization did not hold. The failure of unique factorization to hold in other contexts showed that unique factorization cannot be taken for granted, and is a property that should be proved from more fundamental principles.

This failure of unique factorization in other contexts is a rather advanced topic, but a discussion of it is provided at the page on unique factorization domains.