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.
