Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

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 ofArithmetic 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 integern>1 can be written as a product of primes.

Note that a product may consist of a single factor so that a primepis itself a product of primes. We prove
Theorem 11.11 here, since its proof is relatively simple.

Proof:The proof is by induction. Letn=2. Since 2 is prime,nis a product of primes. Supposen>2, and
the theorem holds for positive integers less thann.Ifnis prime, thennis a product of primes. Ifnis composite,
thenn=abwherea,b<n. By induction,aandbare products of primes; hencen=abis 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, sayp 1 ,p 2 ,...,pm. Consider the integer

n=p 1 p 2 ···pm+ 1

Sincenis a product of primes (Theorem 11.11), it is divisible by one of the primes, saypk. Note thatpkalso
divides the productp 1 p 2 ...pm. Thereforepkdivides

n−p 1 p 2 ...pm= 1

This is impossible, and sonis divisible by some other prime. This contradicts the assumption thatp 1 ,p 2 ,...,pm
are the only primes. Thus the number of primes is infinite, and the theorem is proved.

11.6Greatest Common Divisor, Euclidean Algorithm

Supposeaandbare integers, not both 0. An integerdis called acommon divisorofaandbifddivides
bothaandb, that is, ifd|aandd|b. Note that 1 is a positive common divisor ofaandb, and that any common
divisor ofaandbcannot be greater than|a|or|b|. Thus there exists a largest common divisor ofaandb;itis
denoted by
gcd(a, b)

and it is called thegreatest common divisorofaandb.

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)Forany integera, we have gcd( 1 ,a)=1.