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.
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 = p1 × p2 × ... × pn and b = q1 × q2 × ... × qm, where all pi and qi are prime, the factorization of n = a × b = p1 × p2 × ... × pn × q1 × q2 × ... × qm, 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.
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 = p1 × p2 × ... × pn = q1 × q2 × ... × qm
Notice that pi is not equal to qj 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 p1. 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 p1.
Now we shall write q1 as d × p1 + r, with 0 < r < p1. So:
n = p1 × p2 × ... × pn
n = (d×p1+r) × q2 × ... × qm = d × p1 × q2 × ... × qm + r × q2 × ... × qm
Now we define the number k = n - d × p1 × q2 × ... × qn = r × q2 × ... × qn. As d ≥ 1, k must be smaller than n. And because r > 0, k is positive.
k = p1(p2 × ... × pm - d × q2 × ... × qn).
So this means there is a factorization of k which contains the prime p1. But we can also define k as
k = r × q2 × ... × qn
This factorization does not contain p1, 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.