Page 281 - Discrete Mathematics and Its Applications

260 4 / Number Theory and Cryptography

TABLE 1 The Sieve of Eratosthenes.
Integers divisible by 2 other than 2 Integers divisible by 3 other than 3
receive an underline. receive an underline.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100 91 92 93 94 95 96 97 98 99 100
Integers divisible by 5 other than 5 Integers divisible by 7 other than 7 receive
receive an underline. an underline; integers in color are prime.
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80 71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90 81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100 91 92 93 94 95 96 97 98 99 100

prime not listed. We will prove this fact using a proof given by Euclid in his famous mathematics
text, The Elements. This simple, yet elegant, proof is considered by many mathematicians to be
among the most beautiful proofs in mathematics. It is the first proof presented in the book Proofs
fromTHE BOOK[AiZi10], whereTHE BOOK refers to the imagined collection of perfect proofs
that the famous mathematician Paul Erd˝os claimed is maintained by God. By the way, there
are a vast number of different proofs than there are an infinitude of primes, and new ones are
published surprisingly frequently.

THEOREM 3 There are infinitely many primes.

Proof: We will prove this theorem using a proof by contradiction. We assume that there are only
finitely many primes, p 1 ,p 2 ,...,p n . Let

Q = p 1 p 2 ··· p n + 1.

By the fundamental theorem of arithmetic, Q is prime or else it can be written as the product of
two or more primes. However, none of the primes p j divides Q, for if p j | Q, then p j divides