Feature Column from the AMS

Primes

2. Basic ideas

The sequence of primes begins 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. Although Euclid's proof that the primes are infinite is quite well known, his argument is so neat that I will repeat it here in modern language. Suppose there were only a finite number of primes. Form the number M obtained by multiplying the numbers in this finite collection and adding 1. M is either prime or has a prime factor, yet M or a prime factor of M cannot be in our original list (because none of the primes in the original list divides M without remainder). This contradiction means that the collection of primes cannot be finite.

When a result is very important, it is not surprising that there are various approaches to proving the same thing. This is true with the infinitude of the primes for which a variety of proofs are known.

Many interesting questions about primes arise. We mentioned before that 60 is 5 x 12 or 6 x 10. These factorizations, breaking down the number into smaller numbers, are different, but in each case one or more of the factors is not a prime. Thus, 12 is 2 x 2 x 3 and 6 is 2 x 3 and 10 is 2 x 5. The first factorization leads to the product 2 x 2 x 3 x 5, as does the second. This suggests that even though one may break down a number into primes in different ways, when one gets down to primes and lists these in increasing order, perhaps the result one gets is always the same. This is the content of the Fundamental Theorem of Arithmetic which states:

Every positive integer other than 1 can be written in a unique way as a product of primes.

Again, the reference to a unique factoring into primes refers to the fact that we are not interested in the order in which the primes are listed, only in which primes appear and how often each prime occurs.

Just as artists must learn to use the tools of their "trade," such as brushes, charcoal, or watercolors, mathematicians have tools they put to use regularly. These tools include proof techniques such as mathematical induction or parity arguments, as well the knowledge of "workhorse" theorems. "Workhorse" theorems are results which always seem to be useful in proving new results no matter how often they have been put to use in the past. A good example of a workhorse theorem in the area of number theory is known as Fermat's Little Theorem. This result enables one to show that certain numbers must be composite, that is, they are not prime.

To explain Fermat's Little Theorem first let me briefly review the idea of the congruence of two numbers. This notion, which goes back at least to Carl Friedrich Gauss (1777-1855), calls two numbers equivalent or congruent modulo m (where m is a positive integer which is at least 2) if the numbers leave the same remainder when divided by m. Thus, 24 and 57 are congruent modulo 11 because when divided by 11 they both leave the remainder of 2. (Note that 24 = 2(11) + 2 while 57 = 5(11) + 2). When two numbers are congruent modulo m, their difference is divisible by m with a zero remainder. Thus, since 57 and 24 are congruent modulo 11, we notice that 57 - 24 = 33 is exactly divisible by 11. Because of its many similarities to the properties of the equal sign (=), the symbol " " was used by Gauss for congruence, and we can write 57 24 mod 11. (Mod is short for "modulo.")

We can now state the result that Pierre Fermat (1601-1665) showed: If p is a prime and a is not a multiple of p, then a^p-¹ 1 mod p. (From this it immediately follows that when p is a prime, a^p a mod p for any integer a.)

Here is an example to illustrate Fermat's wonderful result. Suppose p is 11, and a is 2. (Since 2 is not a multiple of 11, the theorem applies.) We need to verify that 2^11-1 which is 2¹⁰, leaves the remainder of 1 when divided by 11. Now 2¹⁰ = 1024, and 1024 = 11(93) + 1, so we indeed have 1 as a remainder when we divide 2¹⁰ by 11. Notice that to do a calculation which involves Fermat's Little Theorem it is helpful to be able to compute the remainder for numbers raised to large powers easily.

Unfortunately, the converse of Fermat's Little Theorem is not true. For example, you can check for yourself that for m = 341 (which is composite because 341 = 31(11)), 2^m-1 1 mod 341. Because of this we say that 341 is a pseudoprime for the base 2. More generally, we say that a number m is a pseudoprime for base b (b a positive integer) if m is composite and b^m-¹ 1 mod m. It turns out that for each choice of a base b, there are pseudoprimes for b. However, things are much worse. When a^m-¹ 1 mod m for every choice of positive a (where a and m are such that the only number which divides both is 1), it does not follow that m must be prime. Such composite numbers m are called Carmichael Numbers, after Robert Daniel Carmichael (1879-1967). An example of a Carmichael Number is 561. Not only do there exist Carmichael Numbers, but like the primes themselves, there are infinitely many of the "varmints."

What the discovery of Fermat's Little Theorem set in motion is typical of many parts of mathematics. An interesting result is proven and it encourages a detailed investigation of ideas in the intellectual vicinity of that result. For example, Euler (1707-1783) studied an important relative of the Little Theorem. To state Euler's result we need a very useful concept, that of two positive integers being relatively prime. We say that j and k are relatively prime if the only integer that divides both j and k is 1. Thus, any two primes are relatively prime and, for example, 14 and 15 are relatively prime, while 10 and 14 are not, since 2 divides both 10 and 14. Euler's result states that for any positive integers n and a with the property that the largest integer which divides them both is 1, then a^phi(n) 1 mod n. Here, phi(n) (n at least 1) denotes the number of positive integers no more than n which are relatively prime to n. Hence, for a prime p, phi(p) = p-1, while for, say, the composite number 20, phi(20) = 8. (The numbers relatively prime to 20 are 1, 3, 7, 9, 11, 13, 17, and 19.)

If one looks at a moderately long list of primes, many questions about primes come to mind. For example, after noting that there are infinitely many primes, it is natural to ask if there are infinitely many primes of special types. There are many interesting things here to explore once one has this new idea. For example, 3, 7, 11, 19, 23, 31, are all primes as are 5, 13, 17, 29, 37. The first set of primes has the form 4k +3 while the second has the form 4k + 1. Numbers which have the form as + b where s can take on the values 1, 2, 3, etc., are called arithmetic progressions. Here we will be interested only in the special class of arithmetic progressions where the numbers a and b are relatively prime, which I will call a relatively prime arithmetic progression. Are there infinitely many primes in the arithmetic progressions 4k +1 and 4k + 3? It turns out that with some work one can show the answer is "yes." However, what is truly amazing is that the following more general observation is true: There are infinitely many primes in any relatively prime arithmetic progression! This remarkable theorem (1837) is due to the mathematician Lejeune Dirichlet (1805-1859). For those interested in connections between music and mathematics, Dirichlet was married to composer Felix Mendelssohn's sister Rebecca. Unquestionably, Dirichlet's Theorem is one of the major landmarks in the history of number theory.

Other special sequences that have been searched for primes, include, for example, the Mersenne primes, named for the cleric Marin Mersenne, pictured below.

Mersenne primes are primes of the form 2ⁿ - 1. It remains unknown whether or not there are infinitely many Mersenne primes, though very large examples are known. It is also unknown if there are infinitely many primes which are one more than a perfect square (e.g. have the form n² + 1). Another tantalizing problem is whether or not for every integer n there is always a prime in the interval from n² to (n+1)². (For example, when n is 10 this question asks if between 100 and 121 there is a prime, and in fact, there are several.) There are many other simple-to-state open problems about primes.

Another pattern that quickly becomes apparent when one carefully looks at the sequence of primes is the occurrence of "twins." Twin primes are primes which differ by 2. Thus, 3 and 5; 11 and 13; 17 and 19; 29 and 31; 41 and 43 are examples of twin primes. The Norwegian mathematician Viggo Brun (1885-1978), shown below, raised the specific question as to whether or not there are infinitely many twin primes.

(This photograph was made available with the kind permission of Harald Hanche-Olsen)

His work makes more specific the earlier family of problems raised by Alphonse de Polignac, who raised the question in 1849 if, for any even integer s, there are infinitely many pairs of primes that differ by s? The remarkable answer to Brun's question about twin primes is that no one knows. For the primes, if one sums the series whose terms are 1/p where p is a prime, the sum turns out not to be a finite number. Perhaps surprisingly, if one sums the series whose terms are 1/s and 1/(s+2) where s and s+2 are both primes, Brun showed the result is a finite number. To use slightly more technical terminology, the first series diverges and the second converges to the constant 1.9021605... , regardless of whether it has a finite number of terms (which as I noted, is still not known). The sum of the series of twin prime pairs is now known as Brun's constant. Finding its exact value has served as a challenge for mathematicians interested in computation. Thomas Nicely, during his effort in 1995 to find a more precise value for Brun's constant, discovered a flaw in the design of one of Intel's Pentium series of chips! Who would have thought that trying to solve an arcane mathematics problem would save many individuals from improperly relying on calculations done by a microprocessor? Nicely is still involved with trying to find more exact values of Brun's constant.