Mathematics for the liberal arts (2013)

Part II. TWO PILLARS OF MATHEMATICS

Chapter 5. NUMBER THEORY

5.5 Primes

Definitions and Examples

In studying the divisibility of integers, one soon encounters special integers that cannot be divided into smaller ones. You may be familiar with this notion.

Definition. Let n be an integer greater than 1. Then n is prime if its only positive divisors are 1 and n. If n is not prime, it is called composite.

EXAMPLE 5.12

The first three primes are 2, 3, and 5. The numbers 4 and 6 are composite, because they are divisible by 2.

Notes:

i. The number 1 is not considered prime or composite.

ii. There is only one even prime, 2. Any other even number is divisible by 2, so cannot be prime.

iii. Similarly, the only prime divisible by 3 is 3 itself, and the only prime divisible by 5 is 5 itself, etc.

Computing Primes

The notes (ii) and (iii) above are the basis for a very old (c. 240 BCE) method of computing all the primes up to any integer N, called the Sieve of Eratosthenes. We will demonstrate the sieve to determine all the primes up to 50.

Write all numbers 1, 2,…, 50.

We will proceed to systematically cross out all the composite numbers, being left at the end with only the primes. We can cross out all the even numbers except 2, since, as noted above, they are all composite. We will also cross out 1, since it is not a prime, and circle 2, because it is a prime.

Now 3 is the smallest number not circled or crossed out, so it must be a prime. Circle it, and cross out all the multiples of 3 that are not already crossed out.

Now 5 is the smallest number not circled or crossed out, so it must be a prime. Circle 5, and cross out all its multiples that are not already crossed out.

If you proceed with the circling and crossing out, you will find all the primes less than 50:

How Many Primes Are There?

Anyone who spends some time looking at primes soon notices that they get rarer as the numbers get larger. For example, there are fifteen primes between 1 and 50, but only ten between 51 and 100. Do they peter out entirely? This question was answered in Euclid’s great book, Elements. His argument is based on a simple fact about primes.

Every integer greater than 1 is divisible by a prime.

We won’t attempt a formal proof (which uses mathematical induction), but the idea is simple enough. Let n be an integer greater than 1. If n is prime, then it is divisible by a prime, namely, itself. If it is not a prime, then an integer other than 1 or n divides it, say m₁, with 1 < m₁ < n. Now repeat this argument with m₁. If it is prime, then we have a prime dividing n. If not, we can find m₂ dividing m₁ with 1 < m₂ < m₁. Keep on repeating this argument. Since each m_i is smaller than the last, this cannot go on forever. So eventually we arrive at some m_i being a prime, and since it divides n, we are done.

We can use this last result for Euclid’s theorem on primes.

Euclid’s Theorem. There are infinitely many primes.

Here is Euclid’s argument. Suppose that there are only finitely many primes, say p₁, p₂,… p_k. Let n be one greater than the product of all these primes: n = p₁p₂ … p_k + 1. Now notice that p₁ divides p₁p₂ … p_k, so p₁ cannot divide n. (Otherwise it would divide 1.) Similarly, p₂ does not divide n, and so on. None of p₁, p₂, …, p_k divides n. But we know that some prime divides n, so we have a contradiction to p₁,…, p_k being the only primes.

Thus there is no end to the primes, but they do seem to get rarer as they get bigger. It turns out that there is a pattern to this, although it took more than 2000 years after Euclid until it was found. The pattern, called the Prime Number Theorem, was conjectured in 1792 by Carl Friedrich Gauss (when he was 15 years old), and, in a slightly different form, in 1796 by Adrien-Marie Legendre. This theorem gives a function for computing the number of primes less than or equal to a number x. The function is not precise, but gives a closer and closer approximation as x gets larger. (For those of you who have seen natural logs, the theorem tells us that the ratio of the number of primes to x/ln x approaches 1 as x gets large.)

The Prime Number Theorem attracted a lot of attention, but wasn’t proved until 1896, independently by Jacques Hadamard and Charles Jean de la Vallée-Poussin.

EXERCISES

5.21 How many primes end in a 5?

5.22 Use the Sieve of Eratosthenes to find all the primes less than 100.

5.23 The only primes that are consecutive integers are 2 and 3. Why?

5.24 Twin primes are primes that are two apart, for example, 3 and 5. Find five other such pairs.

5.25 Twin primes are always consecutive odd integers. Why is that?

5.26 Suppose that we define prime triplets to be three consecutive odd integers which are all prime, for example, 3, 5, and 7. How many such triplets are there?

5.27 Define n! to be the product of the first n positive integers. For example, 2! = 1 · 2 = 2 and 3! = 1 · 2 · 3 = 6. Show that the 999 consecutive numbers

are all composite.

5.28 Use the idea of the last exercise to show that, whatever n is, it is always possible to find n consecutive composite numbers.