What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

INTRODUCTION

The integers have gradually lost their association with superstition and mysticism, but their interest for mathematicians has never waned. Euclid (circa 300 B.C.), whose fame rests on the portion of his Elements that forms the foundation of geometry studied in high school, seems to have made original contributions to number theory, while his geometry was largely a compilation of previous results. Diophantus of Alexandria (circa 275 A.D.), an early algebraist, left his mark on the theory of numbers. Pierre de Fermat (1601-1665), a jurist of Toulouse, and one of the greatest mathematicians of his time, initiated the modern work in this field. Euler (1707–1783), the most prolific of mathematicians, included much number-theoretical work in his researches. Names prominent in the annals of mathematics—Legendre, Dirichlet, Riemann —can be added to the list. Gauss (1777–1855), the foremost mathematician of modern times, who devoted himself to many different branches of mathematics, is said to have expressed his opinion of number theory in the remark, “Mathematics is the queen of the sciences and the theory of numbers is the queen of mathematics.”

§1. THE PRIME NUMBERS

1. Fundamental Facts

Most statements in number theory, as in mathematics as a whole, are concerned not with a single object—the number 5 or the number 32—but with a whole class of objects that have some common property, such as the class of all even integers,

2, 4, 6, 8,···,

or the class of all integers divisible by 3,

3, 6, 9, 12,···,

or the class of all squares of integers,

1, 4, 9, 16,···,

and so on.

Of fundamental importance in number theory is the class of all primes. Most integers can be resolved into smaller factors: 10 = 2.5, 111 = 3.37, 144 = 3·3·2·2·2·2, etc. Numbers that cannot be so resolved are known as prime numbers or primes. More precisely, a prime is an integer p,greater than one, which has no factors other than itself and one. (An integer a is said to be a factor or divisor of an integer b if there is some integer c such that b = ac.) The numbers 2, 3, 5, 7, 11, 13, 17, · · · are primes, while 12, for example, is not, since 12 = 3·4. The importance of the class of primes is due to the fact that every integer can be expressed as a product of primes: if a number is not itself a prime, it may be successively factored until all the factors are primes; thus 360 = 3.120 = 3.30.4 = 3.3.10.2.2 = 3·3·5·2.2·2 = 2³.3².5. An integer (other than 0 or 1) which is not a prime is said to be composite.

One of the first questions that arises concerning the class of primes is whether there is only a finite number of different primes or whether the class of primes contains infinitely many members, like the class of all integers, of which it forms a part. The answer is: There are infinitely many primes.

The proof of the infinitude of the class of primes as given by Euclid remains a model of mathematical reasoning. It proceeds by the “indirect method”. We start with the tentative assumption that the theorem is false. This means that there would be only a finite number of primes, perhaps very many—a billion or so—or, expressed in a general and non-committal way, n. Using the subscript notation we may denote these primes by p₁, p₂, · · ·, p_n. Any other number will be composite, and must be divisible by at least one of the primes p₁, p₂, · · ·, p_n. We now produce a contradiction by constructing a number A which differs from every one of the primes p₁, p₂, · · ·, p_n because it is larger than any of them, and which nevertheless is not divisible by any of them. This number is

A = p₁p₂ · · · p_n + 1,

i.e. 1 plus the product of what we supposed to be all the primes. A is larger than any of the p’s and hence must be composite. But A divided by p₁ or by p₂, etc., always leaves the remainder 1; therefore A has none of the p’s as a divisor. Since our initial assumption that there is only a finite number of primes leads to this contradiction, the assumption is seen to be absurd, and hence its contrary must be true. This proves the theorem.

Although this proof is indirect, it can easily be modified to give a method for constructing, at least in theory, an infinite sequence of primes. Starting with any prime number, such as p₁ = 2, suppose we have found n primes p₁, p₂, · · ·, p_n; we then observe that the number p₁p₂... p_n + 1 either is itself a prime or contains as a factor a prime which differs from those already found. Since this factor can always be found by direct trial, we are sure in any case to find at least one new prime p_n+1; proceeding in this way we see that the sequence of constructible primes can never end.

Exercise: Carry out this construction starting with p₁ = 2, p₂ = 3 and find 5 more primes.

When a number has been expressed as a product of primes, we may arrange these prime factors in any order. A little experience shows that, except for this arbitrariness in the order, the decomposition of a number N into primes is unique: Every integer N greater than 1 can be factored into a product of primes in only one way. This statement seems at first sight to be so obvious that the layman is very much inclined to take it for granted. But it is by no means a triviality, and the proof, though perfectly elementary, requires some subtle reasoning. The classical proof given by Euclid of this “fundamental theorem of arithmetic” is based on a method or “algorithm” for finding the greatest common divisor of two numbers. This will be discussed on page 44. Here we shall give instead a proof of more recent vintage, somewhat shorter and perhaps more sophisticated than Euclid’s. It is a typical example of an indirect proof. We shall assume the existence of an integer capable of two essentially different prime decompositions, and from this assumption derive a contradiction. This contradiction will show that the hypothesis that there exists an integer with two essentially different prime decompositions is untenable, and hence that the prime decomposition of every integer is unique.

*If there exists a positive integer capable of decomposition into two essentially different products of primes, there will be a smallest such integer (see p. 18),

where the p’s and q’s are primes. By rearranging the order of the p’s and q’s if necessary, we may suppose that

p₁ ≤ p₂ ≤ · · · ≤ p_r, q₁ ≤ q₂ ≤ · · · ≤ q₈.

Now p₁ cannot be equal to q₁, for if it were we could cancel the first factor from each side of equation (1) and obtain two essentially different prime decompositions of an integer smaller than m, contradicting the choice of m as the smallest integer for which this is possible. Hence either p₁ <q₁ or q₁ < p₁. Suppose p₁ < q₁. (If q₁ < p₁ we simply interchange the letters p and q in what follows.) We form the integer

(2) m′ = m – (p₁q₂q₃ · · ·q₈).

By substituting for m the two expressions of equation (1) we may write the integer m’ in either of the two forms

Since p₁ < q₁, it follows from (4) that m’ is a positive integer, while from (2) it follows that m’ is smaller than m. Hence the prime decomposition of m’ must be unique, aside from the order of the factors. But from (3) it appears that the prime p₁ is a factor of m’, hence from (4) p₁ must appear as a factor of either (q₁ — p₁) or (q₂q₃ · · · q₈). (This follows from the assumed uniqueness of the prime decomposition of m′; see the reasoning in the next paragraph.) The latter is impossible, since all the q’s are larger than p₁. Hence p₁ must be a factor of q₁ – p₁, so that for some integer h,

q₁ – p₁ = p₁·h or q₁ = p₁(h + 1).

But this shows that p₁ is a factor of q₁, contrary to the fact that q₁ is a prime. This contradiction shows our initial assumption to be untenable and hence completes the proof of the fundamental theorem of arithmetic.

An important corollary of the fundamental theorem is the following: If a prime p is a factor of the product ab, then p must be a factor of either a or b. For if p were a factor of neither a nor b, then the product of the prime decompositions of a and b would yield a prime decomposition of the integer ab not containing p. On the other hand, since p is assumed to be a factor of ab, there exists an integer t such that

ab = pt.

Hence the product of p by a prime decomposition of t would yield a prime decomposition of the. integer ab containing p, contrary to the fact that the prime decomposition of ab is unique.

Examples: If one has verified the fact that 13 is a factor of 2652, and the fact that 2652 = 6.442, one may conclude that 13 is a factor of 442. On the other hand, 6 is a factor of 240, and 240 = 15.16, but 6 is not a factor of either 15 or 16. This shows that the assumption that p is prime is an essential one.

Exercise: In order to find all the divisors of any number a we need only decompose a into a product

where the p’s are distinct primes, each raised to a certain power. All the divisors of a are the numbers

where the β’s are any integers satisfying the inequalities

0 ≤ β₁ ≤ α₁, 0 ≤ β₂ ≤ α₂, · · ·, 0 ≤ β_r ≤ α_r.

Prove this statement. As a consequence, show that the number of different divisors of a (including the divisors a and 1) is given by the product

(α₁ + 1)(α₂ + 1) · · · (α_r + 1).

For example,

144 = 2⁴·3²

has 5.3 divisors. They are 1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144.

2. The Distribution of the Primes

A list of all the primes up to any given integer N may be constructed by writing down in order all the integers less than N, striking out all those which are multiples of 2, then all those remaining which are multiples of 3, and so on until all composite numbers have been eliminated. This process, known as the “sieve of Eratosthenes,” will catch in its meshes the primes up to N. Complete tables of primes up to about 10,000,000 have gradually been computed by refinements of this method, and they provide us with a tremendous mass of empirical data concerning the distribution and properties of the primes. On the basis of these tables we can make many highly plausible conjectures (as though number theory were an experimental science) which are often extremely difficult to prove.

a. Formulas Producing Primes

Attempts have been made to find simple arithmetical formulas that yield only primes, even though they may not give all of them. Fermat made the famous conjecture (but not the definite assertion) that all numbers of the form

F(n) = 2² + 1

are primes. Indeed, for n = 1, 2, 3, 4 we obtain

F(1) = 2² + 1 = 5,

F(2) = 2²² + 1 = 2⁴ + 1 = 17,

F(3) = 2²³ + 1 = 2⁸ + 1 = 257,

F(4) = 2²⁴ + 1 = 2¹⁶ + 1 = 65,537,

all primes. But in 1732 Euler discovered the factorization 2²⁵ + 1 = 641 · 6,700,417; hence F(5) is not a prime. Later, more of these “Fermat numbers” were found to be composite, deeper number-theoretical methods being required in each case because of the insurmountable difficulty of direct trial. To date it has not even been proved that any of the numbers F(n) is a prime for n > 4.

Another remarkable and simple expression which produces many primes is

f(n) = n² – n + 41.

For n = 1, 2, 3, · · ·, 40, f(n) is a prime; but for n = 41, we have f(n) = 41², which is no longer a prime.

The expression

n² – 79n + 1601

yields primes for all n up to 79, but fails when n = 80. On the whole, it has been a futile task to seek expressions of a simple type which produce only primes. Even less promising is the attempt to find an algebraic formula which shall yield all the primes.

b. Primes in Arithmetical Progressions

While it was simple to prove that there are infinitely many primes in the sequence of all integers, 1, 2, 3, 4, · · ·, the step to sequences such as 1, 4, 7, 10, 13, · · · or 3, 7, 11, 15, 19, · · · or, more generally, to any arithmetical progression, a, a + d, a + 2d,... a + nd, · · ·, where a and d have no common factor, was much more difficult. All observations pointed to the fact that in each such progression there are infinitely many primes, just as in the simplest one, 1, 2, 3, · · ·. It required an enormous effort to prove this general theorem. Lejeune Dirichlet (1805–1859), one of the leading mathematicians of the nineteenth century, obtained full success by applying the most advanced tools of mathematical analysis then known. His original papers on the subject rank even now among the outstanding achievements in mathematics, and after a hundred years the proof has not yet been simplified enough to be within the reach of students who are not well trained in the technique of the calculus and of function theory.

Although we cannot attempt to prove Dirichlet’s general theorem, it is easy to generalize Euclid’s proof of the infinitude of primes to cover some special arithmetical progressions such as 4n + 3 and 6n + 5. To treat the first of these, we observe that any prime greater than 2 is odd (since otherwise it would be divisible by 2) and hence is of the form 4n + 1 or 4n + 3, for some integer n. Furthermore, the product of two numbers of the form 4n + 1 is again of that form, since

(4a + 1)(4b + 1) = 16ab + 4a + 4b + 1 = 4(4ab + a + b) + 1.

Now suppose there were but a finite number of primes, p₁, p₁, ··· p_n, of the form 4n + 3, and consider the number

N = 4(p₁p₂ · · · p_n) – 1 = 4(p₁ · · · p_n – 1) + 3.

Either N is itself a prime, or it may be decomposed into a product of primes, none of which can be p₁, · · ·, p_n, since these divide N with a remainder –1. Furthermore, all the prime factors of N cannot be of the form 4n + 1, for N is not of that form and, as we have seen, the product of numbers of the form 4n + 1 is again of that form. Hence at least one prime factor must be of the form 4n + 3, which is impossible, since we saw that none of the p’s, which we supposed to be all the primes of the form 4n + 3, can be a factor of N. Therefore the assumption that the number of primes of the form 4n + 3 is finite has led to a contradiction, and hence the number of such primes must be infinite.

Exercise: Prove the corresponding theorem for the progression 6n + 5.

c. The Prime Number Theorem

In the search for a law governing the distribution of the primes, the decisive step was taken when mathematicians gave up futile attempts to find a simple mathematical formula yielding all the primes or giving the exact number of primes contained among the first n integers, and sought instead for information concerning the average distribution of the primes among the integers.

For any integer n let us denote by A_n the number of primes among the integers 1, 2, 3, · · ·, n. If we underline the primes in the sequence consisting of the first few integers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ··· we can compute the first few values of A_n:

A₁ = 0, A₂ = 1, A₃ = A₄ = 2, A₅ = A₆ = 3, A₇ = A₈ = A₉ = A₁₀ = 4, A₁₁ = A₁₂ = 5, A₁₃ = A₁₄ = A₁₅ = A₁₆ = 6, A₁₇ = A₁₈ = 7, A₁₉ = 8, etc.

If we now take any sequence of values for n which increases without limit, say

n = 10, 10², 10³, 10⁴, · · ·,

then the corresponding values of A_n,

A₁₀, A₁₀², A₁₀³, A₁₀⁴, · · ·,

will also increase without limit (although more slowly). For we know that there are infinitely many primes, so the values of A_n will sooner or later exceed any finite number. The “density” of the primes among the first n integers is given by the ratio A_n/n, and from a table of primes the values of A_n/n may be computed empirically for fairly large values of n.

The last entry in this table may be regarded as giving the probability that an integer picked at random from among the first 10⁹ integers will be a prime, since there are 10⁹ possible choices, of which A₁₀⁹ are primes.

The distribution of the individual primes among the integers is extremely irregular. But this irregularity “in the small” disappears if we fix our attention on the average distribution of the primes as given by the ratio A_n/n. The simple law that governs the behavior of this ratio is one of the most remarkable discoveries in the whole of mathematics. In order to state the prime number theorem we must define the “natural logarithm” of an integer n. To do this we take two perpendicular axes in a plane, and consider the locus of all points in the plane the product of whose distances xand y from these axes is equal to one. In terms of the coördinates x and y this locus, an equilateral hyperbola, is defined by the equation xy = 1. We now define log n to be the area in Figure 5 bounded by the hyperbola, the x-axis, and the two vertical lines x = 1 and x = n. (A more detailed discussion of the logarithm will be found in Chapter VIII.) From an empirical study of prime number tables Gauss observed that the ratio A_n/n is approximately equal to 1/log n, and that this approximation appears to improve as n increases. The goodness of the approximation is given by the ratio , whose values for n = 1000, 1,000,000, 1,000,000,000 are shown in the following table.

Fig. 5. The area of the shaded region under the hyperbola defines log n.

On the basis of such empirical evidence Gauss made the conjecture that the ratio A_n/n is “asymptotically equal” to 1/log n. By this is meant that if we take a sequence of larger and larger values of n, say n equal to

10, 10², 10³, 10⁴, · · ·

as before, then the ratio of A_n/n to 1/log n,

calculated for these successive values of n, will become more and more nearly equal to 1, and that the difference of this ratio from 1 can be made as small as we please by confining ourselves to sufficiently large values of n. This assertion is symbolically expressed by the sign ~:

That ~ cannot be replaced by the ordinary sign = of equality is clear from the fact that while A_n is always an integer, n/log n is not.

That the average behavior of the prime number distribution can be described by the logarithmic function is a very remarkable discovery, for it is surprising that two mathematical concepts which seem so unrelated should be in fact so intimately connected.

Although the statement of Gauss’s conjecture is simple to understand, a rigorous mathematical proof was far beyond the powers of mathematical science in Gauss’s time. To prove this theorem, concerned only with the most elementary concepts, it is necessary to employ the most powerful methods of modern mathematics. It took almost a hundred years before analysis was developed to the point where Hadamard (1896) in Paris and de la Vallée Poussin (1896) in Louvain could give a complete proof of the prime number theorem. Simplifications and important modifications were given by v. Mangoldt and Landau. Long before Hadamard, decisive pioneering work had been done by Riemann (1826–1866) in a famous paper where the strategic lines for the attack were drawn. Recently, the American mathematician Norbert Wiener was able to modify the proof so as to avoid the use of complex numbers at an important step of the reasoning. But the proof of the prime number theorem is still no easy matter even for an advanced student. We shall return to this subject on page 482 et seq.

d. Two Unsolved Problems Concerning Prime Numbers

While the problem of the average distribution of primes has been satisfactorily solved, there are many other conjectures which are supported by all the empirical evidence but which have not yet been proved to be true.

One of these is the famous Goldbach conjecture. Goldbach (1690–1764) has no significance in the history of mathematics except for this problem, which he proposed in 1742 in a letter to Euler. He observed that for every case he tried, any even number (except 2, which is itself a prime) could be represented as the sum of two primes. For example:

4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5, 12 = 5 + 7, 14 = 7 + 7, 16 = 13 + 3, 18 = 11 + 7, 20 = 13 + 7, · · ·, 48 = 29 + 19, · · ·, 100 = 97 + 3, etc.

Goldbach asked if Euler could prove this to be true for all even numbers, or if he could find an example disproving it. Euler never provided an answer, nor has one been given since. The empirical evidence in favor of the statement that every even number can be so represented is thoroughly convincing, as anyone can verify by trying a number of examples. The source of the difficulty is that primes are defined in terms of multiplication, while the problem involves addition. Generally speaking, it is difficult to establish connections between the multiplicative and the additive properties of integers.

Until recently, a proof of Goldbach’s conjecture seemed completely inaccessible. Today a solution no longer seems out of reach. An important success, very unexpected and startling to all experts, was achieved in 1931 by a then unknown young Russian mathematician, Schnirelmann (1905–1938), who proved that every positive integer can be represented as the sum of not more than 300,000 primes. Though this result seems ludicrous in comparison with the original goal of proving Goldbach’s conjecture, nevertheless it was a first step in that direction. The proof is a direct, constructive one, although it does not provide any practical method for finding the prime decomposition of an arbitrary integer. More recently, the Russian mathematician Vinogradoff, using methods due to Hardy, Littlewood and their great Indian collaborator Ramanujan, has succeeded in reducing the number from 300,000 to 4. This is much nearer to a solution of Goldbach’s problem. But there is a striking difference between Schnirelmann’s result and Vinogradoff’s; more significant, perhaps, than the difference between 300,000 and 4. Vinogradoff’s theorem was proved only for all “sufficiently large” integers; more precisely, Vinogradoff proved that there exists an integer N such that any integer n > N can be represented as the sum of at most 4 primes. Vinogradoff’s proof does not permit us to appraise N; in contrast to Schnirelmann’s theorem it is essentially indirect and non-constructive. What Vinogradoff really proved is that the assumption that infinitely many integers cannot be decomposed into at most 4 prime summands leads to an absurdity. Here we have a good example of the profound difference between the two types of proof, direct and indirect. (See the general discussion on p. 86.)

The following even more striking problem than Goldbach’s has come nowhere near a solution. It has been observed that primes frequently occur in pairs of the form p and p + 2. Such are 3 and 5, 11 and 13, 29 and 31, etc. The statement that there are infinitely many such pairs is believed to be correct, but as yet not the slightest definite step has been taken towards a proof.