8.1. Prime Numbers[1]
A central concern of number theory is the study of prime numbers. Indeed, whole books have been written on the subject (e.g., [CRAN01], [RIBE96]). In this section we provide an overview relevant to the concerns of this book. An integer p > 1 is a prime number if and only if its only divisors[2] are ± 1 and ±p. Prime numbers play a critical role in number theory and in the techniques discussed in this chapter. Table 8.1 shows the primes less than 2000. Note the way the primes are distributed. In particular, note the number of primes in each range of 100 numbers.
Table 8.1. Primes under 2000 |
91 | = 7 x 13 |
3600 | = 24 x 32 x 52 |
11011 | = 7 x 112 x 13 |
It is useful for what follows to express this another way. If P is the set of all prime numbers, then any positive integer a can be written uniquely in the following form:
The right-hand side is the product over all possible prime numbers p; for any particular value of a, most of the exponents ap will be 0.
The value of any given positive integer can be specified by simply listing all the nonzero exponents in the foregoing formulation.
The integer 12 is represented by {a2 = 2, a3 = 1}. |
The integer 18 is represented by {a2 = 1, a3 = 2}. |
The integer 91 is represented by {a7 = 2, a13 = 1}. |
Multiplication of two numbers is equivalent to adding the corresponding exponents. Given a . Define k = ab We know that the integer k can be expressed as the product of powers of primes: . It follows that kp = ap + bp for all p
k = 12 x 18 = (22 x 3) x (2 x 32) = 216 |
k2 = 2 + 1 = 3; k3 = 1 + 2 = 3 |
216 = 23 x 33 = 8 x 27 |
What does it mean, in terms of the prime factors of a and b, to say that a divides b? Any integer of the form can be divided only by an integer that is of a lesser or equal power of the same prime number, pj with j Given , If a|b, then ap p.
a | = 12;b = 36; 12|36 | ||||||
12 | = 22 x 3; 36 = 22 x 32 | ||||||
a2 | = 2 = b2 | ||||||
a3 | = 1 2 = Thus, the inequality ap It is easy to determine the greatest common divisor[3] of two positive integers if we express each integer as the product of primes. [3] Recall from Chapter 4 that the greatest common divisor of integers a and b, expressed gcd(a, b), is an integer c that divides both a and b without remainder and that any divisor of a and b is a divisor of c. 300 = 22 x 31 x 52 18 = 21 x 32 gcd(18,300) = 21 x 31 x 50 = 6 The following relationship always holds: If k = gcd(a,b) then kp = min(ap, bp) for all p Determining the prime factors of a large number is no easy task, so the preceding relationship does not directly lead to a practical method of calculating the greatest common divisor. |