vA = w,

where we are given as input a non-singular square integer matrix A and an

integer vector w. The solution vector v will, in general, have rational en-

tries. We stress that we want to compute the exact solution v, and not some

¬‚oating point approximation to it. Now, we could solve for v directly us-

ing Gaussian elimination; however, the intermediate quantities computed by

that algorithm would be rational numbers whose numerators and denomina-

tors might get quite large, leading to a rather lengthy computation (however,

4.6 Notes 73

it is possible to show that the overall running time is still polynomial in the

input length).

Another approach is to compute a solution vector modulo n, where n is

a power of a prime that does not divide the determinant of A. Provided n

is large enough, one can then recover the solution vector v using rational

reconstruction. With this approach, all of the computations can be carried

out using arithmetic on integers not too much larger than n, leading to a

more e¬cient algorithm. More of the details of this procedure are developed

later, in Exercise 15.13.

4.6 Notes

The Euclidean algorithm as we have presented it here is not the fastest

known algorithm for computing greatest common divisors. The asymptot-

ically fastest known algorithm for computing the greatest common divisor

of two numbers of bit length at most runs in time O( len( )) on a RAM,

and the smallest Boolean circuits are of size O( len( )2 len(len( ))). This

algorithm is due to Sch¨nhage [81]. The same complexity results also hold

o

for the extended Euclidean algorithm, as well as Chinese remaindering and

rational reconstruction.

Experience suggests that such fast algorithms for greatest common divi-

sors are not of much practical value, unless the integers involved are very

large ” at least several tens of thousands of bits in length. The extra “log”

factor and the rather large multiplicative constants seem to slow things down

too much.

The binary gcd algorithm (Exercise 4.1) is due to Stein [95]. The ex-

tended binary gcd algorithm (Exercise 4.2) was ¬rst described by Knuth

[54], who attributes it to M. Penk. Our formulation of both of these al-

gorithms closely follows that of Menezes, van Oorschot, and Vanstone [62].

Experience suggests that the binary gcd algorithm is faster in practice than

Euclid™s algorithm.

Our exposition of Theorem 4.6 is loosely based on Bach [11]. A somewhat

“tighter” result is proved, with signi¬cantly more e¬ort, by Wang, Guy, and

Davenport [97]. However, for most practical purposes, the result proved

here is just as good. The application of Euclid™s algorithm to computing a

rational number from the ¬rst digits of its decimal expansion was observed

by Blum, Blum, and Shub [17], where they considered the possibility of

using such sequences of digits as a pseudo-random number generator ” the

conclusion, of course, is that this is not such a good idea.

5

The distribution of primes

This chapter concerns itself with the question: how many primes are there?

In Chapter 1, we proved that there are in¬nitely many primes; however, we

are interested in a more quantitative answer to this question; that is, we

want to know how “dense” the prime numbers are.

This chapter has a bit more of an “analytical” ¬‚avor than other chapters

in this text. However, we shall not make use of any mathematics beyond

that of elementary calculus.

5.1 Chebyshev™s theorem on the density of primes

The natural way of measuring the density of primes is to count the number

of primes up to a bound x, where x is a real number. For a real number

x ≥ 0, the function π(x) is de¬ned to be the number of primes up to x.

Thus, π(1) = 0, π(2) = 1, π(7.5) = 4, and so on. The function π is an

example of a “step function,” that is, a function that changes values only at

a discrete set of points. It might seem more natural to de¬ne π only on the

integers, but it is the tradition to de¬ne it over the real numbers (and there

are some technical bene¬ts in doing so).

Let us ¬rst take a look at some values of π(x). Table 5.1 shows values of

π(x) for x = 103i and i = 1, . . . , 6. The third column of this table shows

the value of x/π(x) (to ¬ve decimal places). One can see that the di¬er-

ences between successive rows of this third column are roughly the same ”

about 6.9 ” which suggests that the function x/π(x) grows logarithmically

in x. Indeed, as log(103 ) ≈ 6.9, it would not be unreasonable to guess that

x/π(x) ≈ log x, or equivalently, π(x) ≈ x/ log x.

The following theorem is a ¬rst ” and important ” step towards making

the above guesswork more rigorous:

74

5.1 Chebyshev™s theorem on the density of primes 75

Table 5.1. Some values of π(x)

x π(x) x/π(x)

103 168 5.95238

106 78498 12.73918

109 50847534 19.66664

1012 37607912018 26.59015

1015 29844570422669 33.50693

1018 24739954287740860 40.42045

Theorem 5.1 (Chebyshev™s theorem). We have

π(x) = ˜(x/ log x).

It is not too di¬cult to prove this theorem, which we now proceed to do

in several steps. Recalling that νp (n) denotes the power to which a prime p

divides an integer n, we begin with the following observation:

Theorem 5.2. Let n be a positive integer. For any prime p, we have

n/pk .

νp (n!) =

k≥1

Proof. This follows immediately from the observation that the numbers

1, 2, . . . , n include exactly n/p multiplies of p, n/p2 multiplies of p2 ,

and so on (see Exercise 1.5). 2

The following theorem gives a lower bound on π(x).

1

Theorem 5.3. π(n) ≥ 2 (log 2)n/ log n for all integers n ≥ 2.

Proof. For positive integer m, consider the binomial coe¬cient

2m (2m)!

N := = .

(m!)2

m

Note that

m+1 m+2 m+m

···

N= ,

1 2 m

from which it is clear that N ≥ 2m and that N is divisible only by primes p

not exceeding 2m. Applying Theorem 5.2 to the identity N = (2m)!/(m!)2 ,

we have

( 2m/pk ’ 2 m/pk ).

νp (N ) =

k≥1

76 The distribution of primes

Each term in this sum is either 0 or 1 (see Exercise 1.4), and for k >

log(2m)/ log p, each term is zero. Thus, νp (N ) ¤ log(2m)/ log p.

So we have

log(2m)

π(2m) log(2m) = log p

log p

p¤2m

≥ νp (N ) log p = log N ≥ m log 2,

p¤2m

where the summations are over the primes p up to 2m. Therefore,

π(2m) ≥ 1 (log 2)(2m)/ log(2m).