The fundamental theorem of arithmetic states that {
n: n is an element of N > 1} (the set of natural numbers, or positive integers, except the number 1) can be represented uniquely apart from rearrangement as the product of one or more
prime numbers (a positive integer that'
s divisible only by 1 and itself). This theorem is also called the
unique factorization theorem and is a corollary to Euclid'
s first theorem, or Euclid'
s principle, which states that if p is a prime number and p/ab is given (a does not equal 0; b does not equal 0), then p is divisible by a or p is divisible by b.
Proof: First prove that every integer n > 1 can be written as a product of primes by using inductive reasoning. Let n = 2. Since 2 is
prime, n is a product of primes. Suppose n > 2, and the above proposition is true for N < n. If n is
prime, then n is a product of primes. If n is composite, then n = ab, where a < n and b < n. Therefore, a and b are products of primes. Hence, n = ab is also a product of primes. Since that has been established, we can now prove that such a product is
unique (except for order). Suppose n = p sub1 * p sub2 * ... * p subk = q sub1 * q sub2 * ... * q subr, where the p'
s and q'
s are primes. If so, then p sub1 is divisible by (q sub1 * ... * q subr) by Euclid'
s first theorem. What is the
relationship between p sub1 and one of the q'
s? If the r in q subr equals 1, then p sub1 = q sub1 since the only divisors of q are + or - 1 and + or - q and p > 1, making p = q. What about the other factors in the divisor? If p does not divide q, then the greatest common denominator of p and q is 1 since the only divisors of p are + or - 1 and + or - p. Thus there are integers m and n so that 1 = am + bn. Multiplying by q subr yieds q subr = amq subr + bnq subr. Since we are saying that p is divisible by q, let'
s say the q sub1 * q subr = cp. Then q subr = amq subr + bnq subr = amq subr + bcm = m(aq subr + bc). Therefore, p is divisible by q sub1 of q sub2 * ... * q subr. If p sub1 is divisible by q sub1, then p sub1 = q sub 1. If this does not work the first time, then repeat the argument until you find an equality. Therefore, one of the p'
s must equal one of the q'
s. In any
case, rearrange the q'
s so that p sub1 = q sub1, then p sub1 * p sub2 * ... * p subk= p sub1 * q sub2 * ... * q subr and p sub2 * ... * p subk = q sub2 * ... * q subr, and so on. By the same argument, we can rearrange the remaining q'
s so that p sub2 = q sub2. Thus n can be expressed uniquely as a product of primes regardless of order, making the fundamental theorem of arithmetic true.
