Page 280 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 259
EXAMPLE 4
THE INFINITUDE OF PRIMES It has long been known that there are infinitely many primes.
√
factor not exceeding n is found, then n is prime. Otherwise, if a prime factor p is found,
continue by factoring n/p. Note that n/p has no prime factors less than p. Again, if n/p has
no prime factor greater than or equal to p and not exceeding its square root, then it is prime.
Otherwise, if it has a prime factor q, continue by factoring n/(pq). This procedure is continued
until the factorization has been reduced to a prime. This procedure is illustrated in Example 4.
Find the prime factorization of 7007.
Solution: To find the prime factorization of 7007, first perform divisions of 7007 by succes-
sive primes, beginning with 2. None of the primes 2, 3, and 5 divides 7007. However, 7 di-
vides 7007, with 7007/7 = 1001. Next, divide 1001 by successive primes, beginning with 7.
It is immediately seen that 7 also divides 1001, because 1001/7 = 143. Continue by divid-
ing 143 by successive primes, beginning with 7. Although 7 does not divide 143, 11 does
divide 143, and 143/11 = 13. Because 13 is prime, the procedure is completed. It follows that
7007 = 7 · 1001 = 7 · 7 · 143 = 7 · 7 · 11 · 13. Consequently, the prime factorization of 7007
2
is 7 · 7 · 11 · 13 = 7 · 11 · 13. ▲
Prime numbers were studied in ancient times for philosophical reasons. Today, there are
highly practical reasons for their study. In particular, large primes play a crucial role in cryp-
tography, as we will see in Section 4.6.
The Sieve of Eratosthenes
Note that composite integers not exceeding 100 must have a prime factor not exceeding 10.
Because the only primes less than 10 are 2, 3, 5, and 7, the primes not exceeding 100 are these
four primes and those positive integers greater than 1 and not exceeding 100 that are divisible
by none of 2, 3, 5, or 7.
The sieve of Eratosthenes is used to find all primes not exceeding a specified positive
integer. For instance, the following procedure is used to find the primes not exceeding 100. We
begin with the list of all integers between 1 and 100. To begin the sieving process, the integers
that are divisible by 2, other than 2, are deleted. Because 3 is the first integer greater than 2 that
is left, all those integers divisible by 3, other than 3, are deleted. Because 5 is the next integer
left after 3, those integers divisible by 5, other than 5, are deleted. The next integer left is 7,
so those integers divisible by 7, other than 7, are deleted. Because all composite integers not
exceeding 100 are divisible by 2, 3, 5, or 7, all remaining integers except 1 are prime. In Table 1,
the panels display those integers deleted at each stage, where each integer divisible by 2, other
than 2, is underlined in the first panel, each integer divisible by 3, other than 3, is underlined
in the second panel, each integer divisible by 5, other than 5, is underlined in the third panel,
and each integer divisible by 7, other than 7, is underlined in the fourth panel. The integers not
underlined are the primes not exceeding 100. We conclude that the primes less than 100 are 2,
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.
This means that whenever p 1 ,p 2 ,...,p n are the n smallest primes, we know there is a larger
ERATOSTHENES (276 b.c.e.–194 b.c.e.) It is known that Eratosthenes was born in Cyrene, a Greek colony
west of Egypt, and spent time studying at Plato’s Academy in Athens. We also know that King Ptolemy II
invited Eratosthenes to Alexandria to tutor his son and that later Eratosthenes became chief librarian at the
famous library at Alexandria, a central repository of ancient wisdom. Eratosthenes was an extremely versatile
scholar, writing on mathematics, geography, astronomy, history, philosophy, and literary criticism. Besides his
work in mathematics, he is most noted for his chronology of ancient history and for his famous measurement
of the size of the earth.