Number theory 2

Primes
A positive integer p > 1 is called a prime number or a prime if its only divisors are ±1 and ±p, that is, if
p only has trivial divisors. If n > 1 is not prime, then n is said to be composite. We note (Problem 11.13) that if
n > 1 is composite then n = ab where 1 < a,b < n.
270 PROPERTIES OF THE INTEGERS [CHAP. 11
EXAMPLE 11.4
(a) The integers 2 and 7 are primes, whereas 6 = 2 · 3 and 15 = 3 · 5 are composite.
(b) The primes less than 50 follow:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
(c) Although 21, 24, and 1729 are not primes, each can be written as a product of primes:
21 = 3 · 7; 24 = 2 · 2 · 2 · 3 = 23 · 3; 1729 = 7 · 13 · 19
The Fundamental Theorem of Arithmetic states that every integern > 1 can be written as a product of primes
in essentially one way; it is a deep and somewhat difficult theorem to prove. However, using induction, it is easy
at this point to prove that such a product exists. Namely:
Theorem 11.11: Every integer n > 1 can be written as a product of primes.
Note that a product may consist of a single factor so that a prime p is itself a product of primes. We prove
Theorem 11.11 here, since its proof is relatively simple.
Proof: The proof is by induction. Let n = 2. Since 2 is prime, n is a product of primes. Suppose n > 2, and
the theorem holds for positive integers less than n. If n is prime, then n is a product of primes. If n is composite,
then n = ab where a, b < n. By induction, a and b are products of primes; hence n = ab is also a product of
primes.
Euclid, who proved the Fundamental Theorem of Arithmetic, also asked whether or not there was a largest
prime. He answered the question thus:
Theorem 11.12: There is no largest prime, that is, there exists an infinite number of primes.
Proof: Suppose there is a finite number of primes, say p1, p2, . . . , pm. Consider the integer
n = p1p2 · · · pm
+ 1
Since n is a product of primes (Theorem 11.11), it is divisible by one of the primes, say pk. Note that pk also
divides the product p1p2 . . . pm. Therefore pk divides
n ? p1p2 . . . pm
= 1
This is impossible, and so n is divisible by some other prime. This contradicts the assumption that p1, p2, . . . , pm
are the only primes. Thus the number of primes is infinite, and the theorem is proved.
11.6 GREATEST COMMON DIVISOR, EUCLIDEAN ALGORITHM
Suppose a and b are integers, not both 0. An integer d is called a common divisor of a and b if d divides
both a and b, that is, if d | a and d | b. Note that 1 is a positive common divisor of a and b, and that any common
divisor of a and b cannot be greater than |a| or |b|. Thus there exists a largest common divisor of a and b; it is
denoted by
gcd(a, b)
and it is called the greatest common divisor of a and b.
EXAMPLE 11.5
(a) The common divisors of 12 and 18 are ±1, ±2, ±3, ±6. Thus gcd(12, 18) = 6. Similarly:
gcd(12,?18) = 16, gcd(12,?16) = 4, gcd(29, 15) = 1, gcd(14, 49) = 7
(b) For any integer a, we have gcd(1, a) = 1.
CHAP. 11] PROPERTIES OF THE INTEGERS 271
(c) For any prime p, we have gcd(p, a) = p or gcd(p, a) = 1 according as p does or does not divide a.
(d) Suppose a is positive. Then a | b if and only if gcd(a, b) = a.
The following theorem (proved in Problem 11.26) gives an alternative characterization of the greatest
common divisor.
Theorem 11.13: Let d be the smallest positive integer of the form ax + by. Then
d = gcd(a, b).
Corollary 11.14: Suppose d = gcd(a, b). Then there exist integers x and y such that d = ax + by.
Another way to characterize the greatest common divisor, without using the inequality relation, follows
Theorem 11.15: A positive integer d = gcd(a, b) if and only if d has the following two properties:
(1) d divides both a and b.
(2) If c divides both a and b, then c | d.
Simple properties of the greatest common divisor are:
(a) gcd(a, b) = gcd(b, a). (c) If d = gcd(a, b), then gcd(a/d, b/d) = 1.
(b) If x > 0, then gcd(ax, bx) = x · gcd(a, b). (d) For any integer x, gcd(a, b) = gcd(a, b + ax).
Euclidean Algorithm
Let a and b be integers, and let d = gcd(a, b). One can always find d by listing all the divisors of a and
then all the divisors of b and then choosing the largest common divisor. The complexity of such an algorithm
is f (n) = 0(
?
n) where n = |a| + |b|. Also, we have given no method to find the integers x and y such that
d = ax + by.
This subsection gives a very efficient algorithm, called the Euclidean algorithm, with complexity
f (n) = O(log n), for finding d = gcd(a, b) by applying the division algorithm to a and b and then repeatedly
applying it to each new quotient and remainder until obtaining a nonzero remainder. The last nonzero
remainder is d = gcd(a, b).
Then we give an “unraveling” algorithm which reverses the steps in the Euclidean algorithm to find the
integers x and y such that d = xa + yb.
We illustrate the algorithms with an example.
EXAMPLE 11.6 Let a = 540 and b = 168. We apply the Euclidean algorithm to a and b. These steps, which
repeatedly apply the division algorithm to each quotient and remainder until obtaining a zero remainder, are
pictured in Fig. 11-3(a) using long division and also in Fig. 11-3(b) where the arrows indicate the quotient and
remainder in the next step. The last nonzero remainder is 12. Thus
12 = gcd(540, 168)
This follows from the fact that
gcd(540, 168) = gcd(168, 36) = gcd(36, 24) = gcd(24, 12) = 12
Next we find x and y such that 12 = 540x+168y by “unraveling” the above steps in the Euclidean algorithm.
Specifically, the first three quotients in Fig. 11-3 yield the following equations:
(1) 36 = 540 ? 3(168), (2) 24 = 168 ? 4(36), (3) 12 = 36 ? 1(24)
Equation (3) tells us that d = gcd(a, b) = 12 is a linear combination of 36 and 24. Now we use the preceding
equations in reverse order to eliminate the other remainders. That is, first we use equation (2) to replace 24 in
equation (3) so we can write 12 as a linear combination of 168 and 36 as follows:
(4) 12 = 36 ? 1[168 ? 4(36)] = 36 ? 1(168) + 4(36) = 5(36) ? 1(168)
272 PROPERTIES OF THE INTEGERS [CHAP. 11
Fig. 11-3
Next we use equation (1) to replace 36 in (4) so we can write 12 as a linear combination of 168 and 540 as follows:
12 = 5[540 ? 3(168)] ? 1(168) = 5(54) ? 15(168) ? 1(168) = 5(540) ? 16(168)
This is our desired linear combination. In other words, x = 5 and y = ?16.
Least Common Multiple
Suppose a and b are nonzero integers. Note that |ab| is a positive common multiple of a and b. Thus there
exists a smallest positive common multiple of a and b; it is denoted by
lcm(a, b)
and it is called the least common