SECTION 2.1 Elementary Number Theory 75
2.1.4 Primes and the fundamental theorem of arithmetic
We have already defined aprimeas a positive integerpgreater than
1 whose only positive divisors are 1 andpitself. The following result
may seem a bit obvious to the naive reader. What I want, though, is
for the reader to understand the nature of the proof.^9
Lemma.Any positive integern > 1 has at least one prime factor.
Proof. Denoting byNthe set of positive integers, we define the set
C = {n∈N|n >1 andnhas no prime factors}.
Think ofC as the set of “criminals;” naturally we would like to show
thatC = ∅, i.e., that there are no criminals. IfC 6 =∅, thenC has a
smallest element in it; call itc 0 (the “least criminal”). Sincec 0 cannot
itself be prime, it must have a non-trivial factorization: c 0 = c′ 0 c′′ 0 ,
where 1< c′ 0 , c′′ 0 < c 0. But then,c′ 0 , c′′ 0 6∈Cand hence aren’t criminals.
In particular,c′ 0 has a prime factor, which is then a factor of c 0. So
c 0 wasn’t a criminal in the first place, proving thatC=∅, and we’re
done!
Using the above simple result we can prove the possibly surprising
result that there are, in fact, infinitely many primes. This was known
to Euclid; the proof we give is due to Euclid:
Theorem. There are infinitely many primes.
Proof. (Euclid) Assume, by way of contradiction that there are only
finitely primes; we may list them:
p 1 , p 2 , ...,pn.Now form the positive integern = 1 +p 1 p 2 ···,pn.Note that none of
the primesp 1 ,p 2 ,...,pn can divide n. However, because of the above
lemma we know thatn must have a prime divisor p 6 = p 1 ,p 2 ,...,pn.
(^9) I will formalize this method of proof in the next section.