## The Fundamental Theorem of Arithmetic.

** **

**Definition**: A whole number greater than 1 is a prime number
if the only whole numbers that go into it are 0 and 1.

We need to specifically exclude 1 from the list of prime numbers
in order to make the following result work.

** **

**Theorem**: (The Fundamental Theorem of Arithmetic)

(Existence) Every whole number greater than 1 is either prime or
can be written as a product of primes.

(Uniqueness) Any two factorizations of a number into a product of
primes will involve the same numbers of the same primes.

** **

**Proof**: (Existence) Let n be a whole number greater than 1.
If n is prime, then it is prime. If it is not, then it can be written
as a product of two smaller numbers. If both of those numbers are
prime, the n is a product of primes. If not then write which ever one
is not prime as a product of two smaller numbers. Since there are
only a finite number of positive integers which are smaller than n,
this process must eventually stop. The only way it can stop is if the
factors are prime.

(Uniqueness) Let

n = p_{1}p_{2} . . . p_{r} =
q_{1}q_{2} . . . q_{s}

be two prime factorizations of a positive integer, n. If r is not
equal to s, then we will, after possibly relabeling, assume that r is
smaller. Since each of the p's and each of the q's are prime, if they
are not equal, they are relatively prime. By one of the
corollaries to the
Euclidean Algorithm,
p_{1} has to divide one of the q's. Since each of the q's is
prime, the only way that p_{1} could divide any of the q's is
to be equal to one of them. We can thus
cancel p_{1} both sides of the
equation. We repeat this argument with the factorizations which are
left, and conclude that p_{2} is equal to one of the q's. We
cancel p_{2} from both sides of the equation, and repeat the
argument until all of the p's are gone. At this point we see that we
could not have more q's than p's, because if we did, the product of
the remaining q's would equal 1, and it is impossible to get integers
which are larger than 1 to multiply up to 1.