Factorization

We like to ``break down'', or factorize, a number into its prime factors. For example, primes like 2 and 11 cannot be broken down further; composites like 6 can be broken down as 2*3, 15 as 3*5, 12 as 2*2*3, 25 as 5*5, etc. In the broad sense, we could factorize 12 as 2*6 or 4*3, decomposing it into two non-trivial multiplicands; however, often we like to continue until all multiplicands are primes, as in 12 = 2*2*3. We refer to the latter as a prime factorization if the context has not made the intention clear.

We could go on with other examples forever, but eventually we must ask some fundamental questions. Can all numbers be prime-factorized? In how many different ways can a number be prime-factorized?

First let us agree that the cases of 0 and units are special. In a broad sense, 0 can be factorized, as 0*1, 0*2, 0*3, 0*5, etc. But none of these are prime factorizations, because 0 is not a prime but is involved. Similarly, units like 1 do not have prime factorizations.

You may argue that this is caused by our artificial definition of primes, in which we exclude units. But let us suppose for a moment that 1 were considered a prime. Then 1 could be prime-factorized in many ways: 1, 1*1, 1*1*1, 1*1*1*1, ad infinitum. What's more, any number could be prime-factorized in equally silly ways: 10 = 2*5 = 1*2*5 = 1*1*2*5, etc. If you allow integers, it would be even more silly: 10 = 2*5 = (-1)*(-1)*2*5 = (-1)*(-1)*1*2*5 = (-1)*(-1)*(-1)*(-1)*2*5, to no end. Precisely because units have reciprocals, we could throw in any occurrence of units to make ``new'' prime factorizations, provided we also threw in the appropriate reciprocals to balance things out. This is not only silly but also obscuring. We feel that 2*5 should be the ``only'' prime factorization of 10, and things like 1*2*5 and (-1)*(-1)*2*5 should be merely insignificant, superfluous variations. By excluding units from primes, we free ourselves from endless strings of reciprocals, and highlight the more significant and interesting aspect of factorization. Units are called units because they are as boring as unity: 1.

Having settled the issues of 0 and units, it can be proved that numbers can indeed be factorized into primes, and the prime factorization of a number is fairly unique. For the natural numbers, this result is often called the Fundamental Theorem of Arithmetic.

Theorem: In the natural numbers, each non-zero, non-unit number can be factorized into a product of primes; furthermore, the factorization is unique up to ordering.

The phrase ``unique up to ordering'' must be made precise: if n has two prime factorizations p1*...*pk and q1*...*qm, then k=m (i.e. they have the same number of items), and the p's are just a permutation of the q's, i.e., each pi is equal to a certain corresponding qj.

Proof. Use strong induction to prove the existence. The uniqueness is proved by appealing to the characterizing theorem of primes.

For example, prime numbers can be factorized trivially: 3 as 3, 2 as 2. Composite numbers are more interesting, e.g., 6 = 2*3 = 3*2, 12 = 2*2*3 = 3*2*2 = 2*3*2. You may change the order of the prime factors, but not the prime factors themselves.

An analogous theorem holds for the integers.

Theorem: In the integers, each non-zero, non-unit number can be factorized into a product of primes. Furthermore, the factorization is unique up to ordering and associates. (And in the integers, associates differ by signs only.)

Again the uniqueness phrase must be made precise: if n has two prime factorizations p1*...*pk and q1*...*qm, then k=m (i.e. they have the same number of items), and each pi is an associate of a certain corresponding qj.

Proof. Extend the result for the natural numbers to the integers by allowing negative integers. Or, appeal to results in abstract algebra - the set of integers is a Euclidean domain, and therefore a principle ideal domain, and therefore a unique factorization domain.

For example, 6 = 2*3 = 3*2 = (-2)*(-3) = (-3)*(-2), and -6 = (-2)*3 = 2*(-3) = (-3)*2 = 3*(-2). Although -3 and 3 are distinct numbers, they are associates; so are 2 and -2. We do not wish to consider 2*3 to be significantly different from (-2)*(-3); we consider them minor variations of the same essence. By stating ``unique up to associates'', we again free ourselves from minor details and stress the main point.