76 CHAPTER 2 Discrete Mathematics
Therefore the original list of primes did not containallof the primes.
This contradiction proves the result.
Knowing that there are infinitely many primes, one may ask a slighly
more subtle question, namely whether the infinite series
∑
primesp( 1
p)
=1
2
+
1
3
+
1
5
+···+
1
31
+···
converges or diverges. One can show that this series actually diverges,
which shows that the prime numbers are relatively densely packed
within the set of positive integers.
There are many unsolved conjectures related to prime numbers; we’ll
just state two such here. The first is related to twin primeswhich
are prime pairs of the formp, p+ 2, where both are primes. The first
few twin primes are 3,5, 5,7, 11,13, and so on. The so-called “Twin
Prime” conjecture which states that there are an infinite number of
twin primes. The next is theGoldbach conjecturewhich states that
any even integer greater than 2 is the sum of two primes. Neither of
these conjectures has been proved.
Using the above method of “criminals”^10 one eventually arrives at
the importantFundamental Theorem of Arithmetic:
Theorem. (Fundamental Theorem of Arithmetic)Any positive integer
n > 1 has a unique factorization into primes. In other words
(i) there exist primesp 1 < p 2 <···< pr and exponentse 1 ,e 2 ,...,er
such that
n=pe 11 pe 22 ···perr.(ii) The factorization above is unique in that ifn = qf 11 qf 22 ·qfss then
s=r, p 1 =q 1 ,p 2 =q 2 ,...,pr =qr ande 1 =f 1 ,e 2 =f 2 ,...,er =
fr.Now letaandbbe positive integers greater than 1. Write(^10) My surrogate formathematical induction