What is the abc conjecture | Open and solved problems | Consequences | The algorithm

Integer factorization is the process of breaking down a number n into primes which, when multiplied, form the original number n. For example, the factorization of 12 = 2 × 2 × 3. These are all primes and their product is 12. Every integer can be factorized into primes, and that is why primes are called the "building blocks" of all positive integers. Every integer has one unique factorization.

Existence of a factorization

To prove that any number has an integer factorization, we are going to assume there are some numbers which cannot be decomposed into a set of primes. If there are any numbers which cannot be factorized, there must be a smallest one. Lets call this number n. Now there are 2 possibilities: Either the number is a product of two numbers between one and n (exclusive), or it is not. Suppose it is a product of 2 numbers, so n = a × b. We know a and b have an integer factorization, as n is the smallest natural number without one. If the factorization of a = p₁ × p₂ × ... × p_n and b = q₁ × q₂ × ... × q_m, where all p_i and q_i are prime, the factorization of n = a × b = p₁ × p₂ × ... × p_n × q₁ × q₂ × ... × q_m, so n does turn out to have a factorization. On the other hand, if n cannot be written as a product of 2 numbers between 1 and n, it is prime by definition and it's integer factorization is simply n. So there cannot be an integer which is not a product of primes.

Uniqueness of a factorization

We are going to do the same trick to prove any number n has only one integer factorization. To prove this we are going to assume there are some numbers which have 2 factorizations. And there is a least one, and we call this number n. Suppose:

n = p₁ × p₂ × ... × p_n = q₁ × q₂ × ... × q_m

Notice that p_i is not equal to q_j for any i and j. If both numbers share a common prime factor, we simply divide n by this prime factor, and we find a smaller number with two factorizations, though n was the smallest one.

We can assume the smallest prime in both factorizations is p₁. If the smallest prime is one of the q's simply switch the p's and q's and if it's another p, switch this one with p₁.

Now we shall write q₁ as d × p₁ + r, with 0 < r < p₁. So:

n = p₁ × p₂ × ... × p_n
n = (d×p₁+r) × q₂ × ... × q_m = d × p₁ × q₂ × ... × q_m + r × q₂ × ... × q_m

Now we define the number k = n - d × p₁ × q₂ × ... × q_n = r × q₂ × ... × q_n. As d ≥ 1, k must be smaller than n. And because r > 0, k is positive.

k = p₁(p₂ × ... × p_m - d × q₂ × ... × q_n).

So this means there is a factorization of k which contains the prime p₁. But we can also define k as

k = r × q₂ × ... × q_n

This factorization does not contain p₁, and therefore, it's different from the first one. So we have found a natural number less than n with two factorizations, and we said n was the smallest one. So since there cannot be a smallest integer with two factorizations, there cannot be any number with two factorizations, and all numbers have a unique factorization.