Prime Numbers

Prime Numbers

^[1] In this section, unless otherwise noted, we deal only with the nonnegative integers. The use of negative integers would introduce no essential differences.

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.

^[2] Recall from Chapter 4 that integer a is said to be a divisor of integer b if there is no remainder on division. Equivalently, we say that a divides b.

Equation 8-1

where p1 < p₂ < ... < p_t are prime numbers and where each is a positive integer. This is known as the fundamental theorem of arithmetic; a proof can be found in any text on number theory.

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 a_p 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 k_p = a_p + b_p for all p P.

---

[Page 238]

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, p^j with j n. Thus, we can say the following:

Given , If a|b, then a_p b_p then for all p.

a	= 12;b = 36; 12|36
12	= 22 x 3; 36 = 22 x 32
a2	= 2 = b2
a3	= 1 2 = b3
Thus, the inequality ap bp is satisfied for all prime numbers.

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 k_p = min(a_p, b_p) 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.