The Fundamental Theorem of Arithmetic.

Fraction Unit

Math 300

Dr. Wilson

 

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 = p1p2 . . . pr = q1q2 . . . qs

 

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, p1 has to divide one of the q's. Since each of the q's is prime, the only way that p1 could divide any of the q's is to be equal to one of them. We can thus cancel p1 both sides of the equation. We repeat this argument with the factorizations which are left, and conclude that p2 is equal to one of the q's. We cancel p2 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.