148
Proofs, Induction, and Number Theory
We have now completed the proof of the fundamental theorem of arithmetic.
Note, however, that this is an existence result. It says that for any integer n ≥ 2
that is not prime, there exists a unique factorization as a product of primes. But
this does not tell us
a. how to decide whether n is prime.
b. if n is not prime, how to find the prime factors of n.
Neither of these problems has an efficient algorithmic solution. The approach in
Example 31 of dividing a number n by successively larger primes accomplishes
both tasks—if there are prime factors of n, they will be discovered and if there
are none, then n is prime. However, this approach becomes very labor intensive
when n is large.
More on Prime Numbers
Anything with a title as imposing as the fundamental theorem of arithmetic must
be fairly important. We can use this theorem to discover several more results
about prime numbers.
Given a positive integer n, suppose we test for prime factors by dividing n by
successively larger primes. Clearly we can stop with the largest prime less than or
equal to n, but in fact we can stop with the largest prime less than or equal to !n.
If n can be factored in a nontrivial way as n = st, then s and t cannot both be greater
than !n because then their product would be greater than n. Therefore one of s
and t, let’s say s, must be less than or equal to. !n. By the fundamental theorem of
arithmetic, s is either prime or can be written as a product of primes. In either case,
there is a prime factor less than or equal to !n, which proves the following theorem.
tHeoReM oN SIzE oF PrIME FaCTorS
If n is a composite number, then it has a prime factor less than or equal to !n.
eXAMPLe 32
Given n = 1021, let’s find the prime factors of n or determine that n is prime. The
value of !1021 is just less than 32. So the primes we need to test are 2, 3, 5, 7, 11,
13, 17, 19, 23, 29, 31. None divides 1021, so 1021 is prime.
How many prime numbers are there? An infinite number.
tHeoReM oN INFINITy oF PrIMES (EuClID)
There is an infinite number of prime numbers.
Proof: Assume that there is a finite number of primes, listed as p 1 , p 2 , … , p k .
Consider the number s = p 1 p 2 c p k + 1. The integer s is greater than any of the
primes p 1 , … , p k , which we assumed is the total list of primes, therefore s is not
prime. Thus s is composite and, by the fundamental theorem of arithmetic, s can
be factored as a product of (some of) the prime numbers. Suppose that p j is one of
the prime factors of s, that is, s = p j (m) for some integer m. Then
1 = s − p 1 p 2 c p k = p j (m) − p 1 c p k = p j (m − p 1 c p j−1 p j+1 c p k )
Therefore p j 0 1, which is a contradiction. End of Proof
Proofs, Induction, and Number Theory
We have now completed the proof of the fundamental theorem of arithmetic.
Note, however, that this is an existence result. It says that for any integer n ≥ 2
that is not prime, there exists a unique factorization as a product of primes. But
this does not tell us
a. how to decide whether n is prime.
b. if n is not prime, how to find the prime factors of n.
Neither of these problems has an efficient algorithmic solution. The approach in
Example 31 of dividing a number n by successively larger primes accomplishes
both tasks—if there are prime factors of n, they will be discovered and if there
are none, then n is prime. However, this approach becomes very labor intensive
when n is large.
More on Prime Numbers
Anything with a title as imposing as the fundamental theorem of arithmetic must
be fairly important. We can use this theorem to discover several more results
about prime numbers.
Given a positive integer n, suppose we test for prime factors by dividing n by
successively larger primes. Clearly we can stop with the largest prime less than or
equal to n, but in fact we can stop with the largest prime less than or equal to !n.
If n can be factored in a nontrivial way as n = st, then s and t cannot both be greater
than !n because then their product would be greater than n. Therefore one of s
and t, let’s say s, must be less than or equal to. !n. By the fundamental theorem of
arithmetic, s is either prime or can be written as a product of primes. In either case,
there is a prime factor less than or equal to !n, which proves the following theorem.
tHeoReM oN SIzE oF PrIME FaCTorS
If n is a composite number, then it has a prime factor less than or equal to !n.
eXAMPLe 32
Given n = 1021, let’s find the prime factors of n or determine that n is prime. The
value of !1021 is just less than 32. So the primes we need to test are 2, 3, 5, 7, 11,
13, 17, 19, 23, 29, 31. None divides 1021, so 1021 is prime.
How many prime numbers are there? An infinite number.
tHeoReM oN INFINITy oF PrIMES (EuClID)
There is an infinite number of prime numbers.
Proof: Assume that there is a finite number of primes, listed as p 1 , p 2 , … , p k .
Consider the number s = p 1 p 2 c p k + 1. The integer s is greater than any of the
primes p 1 , … , p k , which we assumed is the total list of primes, therefore s is not
prime. Thus s is composite and, by the fundamental theorem of arithmetic, s can
be factored as a product of (some of) the prime numbers. Suppose that p j is one of
the prime factors of s, that is, s = p j (m) for some integer m. Then
1 = s − p 1 p 2 c p k = p j (m) − p 1 c p k = p j (m − p 1 c p j−1 p j+1 c p k )
Therefore p j 0 1, which is a contradiction. End of Proof