|
Re: Mathematics
Circulate this on Facebook:
The prime factorization of any integer is unique.
Proof: Suppose that there exists at least one integer with more than one prime factorization. Then there must be a least (smallest) such integer, k. We can write k as a product of prime factors like this:
[1] k = p_0 * p_1 * p_2 * ... * p_n = q_0 * q_1 * q_2 * ... * q_n
The two lists (p_0...p_n and q_0...q_n) cannot have any primes in common -- otherwise we could factor out the non-unique prime(s) from both sides of the equation and have a smaller number with two prime factorizations, which would contradict our initial premise. It follows then that either p_0 < q_0 or q_0 < p_0. Say p_0 is the smaller of the two, and consider the following number, k':
[2] k' = k - (p_0 * q_1 * q_2 * ... * q_n)
[3] k' = (p_0 * p_1 * p_2 * ... * p_n) - (p_0 * q_1 * q_2 * ... * q_n) = p_0 * ( (p_1 * p_2 * ... * p_n) - (q_1 * q_2 * ... * q_n))
[4] k' = (q_0 * q_1 * q_2 * ... * q_n) - (p_0 * q_1 * q_2 * ... * q_n) = (q_0 - p_0) * (q_1 * q_2 * ... * q_n)
Clearly k' is smaller than k. k' is also positive, since the product (p_0 * q_1 * q_2 * ... * q_n) is smaller than k. [3] Tells us that p_0 must be a factor of k', and from [4] it follows that p_0 must be a factor of either (q_0 - p_0) or (q_1 * q_2 * ... * q_n). But p_0 cannot be a factor of the latter term, as that term produces a number smaller than k and any number smaller than k must be uniquely factorizable. So p_0 must be a factor of (q_0 - p_0), which means we can write:
q_0 - p_0 = p_0 * h
...with h being some integer. And...
q_0 = p_0 + p_0 * h = p_0 * (h + 1)
But if q_0 is a multiple of p_0, then q_0 is not prime, which means that (q_0 * q_1 * q_2 * ... * q_n) cannot be a prime factorization. So our first premise -- that at least one integer has more than one prime factorization -- must be mistaken.
|
