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

CHAP. 11] PROPERTIES OF THE INTEGERS 273

11.7Fundamental Theorem of Arithmetic

This section discusses the Fundamental Theorem of Arithmetic. First we define relatively prime integers.

Relatively Prime Integers

Two integersaandbare said to berelatively primeorcoprimeif gcd(a, b)=1. Accordingly, ifaandbare
relatively prime, then there exist integersxandysuch that

ax+by= 1

Conversely, ifax+by=1, thenaandbare relatively prime.

EXAMPLE 11.8

(a) Observe that: gcd( 12 , 35 )=1, gcd( 49 , 18 )=1, gcd( 21 , 64 )=1, gcd(− 28 , 45 )= 1

(b) Ifpandqare distinct primes, then gcd(p, q)=1.

(c) For any integera, we have gcd(a, a+ 1 )=1, since any common factor ofaanda+1 must divide their
difference(a+ 1 )−a=1.
The relation of being relatively prime is particularly important because of the following results. The first
theoremisproved in Problem 11.27, and we will prove the second theorem here.

Theorem 11.17: Suppose gcd(a, b)=1, andaandbboth dividec. Thenabdividesc.

Theorem 11.18: Supposea|bc, and gcd(a, b)=1. Thena|c

Proof:Since gcd(a, b)=1, there existxandysuch thatax+by=1. Multiplying bycyields:

acx+bcy=c
We havea|acx. Also,a|bcysince, by hypothesis,a|bc. Henceadivides the sumacx+bcy=c.

Corollary 11.19:Supposeaprimepdivides the productab. Thenp|aorp|b.
This corollary (proved in Problem 11.28) dates back to Euclid; it is the basis of his proof of the Fundamental
Theorem of Arithmetic.

Fundamental Theorem of Arithmetic

Theorem 11.11 asserts that every positive integer is a product of primes. Can different products of primes

yield the same number? Clearly, we can rearrange the order of the prime factors, e.g.,

30 = 2 · 3 · 5 = 5 · 2 · 3 = 3 · 2 · 5

TheFundamentalTheorem of Arithmetic (proved in Problem 11.30) says that this is the only way that two
“different” products can give the same number. Namely:

Theorem 11.20 (FundamentalTheorem ofArithmetic): Every integern>1 can be expressed uniquely (except
for order) as a product of primes.
The primes in the factorization ofnneed not be distinct. Frequently, it is useful to collect together all equal
primes. Thenncan be expressed uniquely in the form

n=pm 11 pm 22 ...pmrr

where themiare positive andp 1 <p 2 <...<pr. This is called thecanonical factorizationofn.

EXAMPLE 11.9 Givena= 24 · 33 · 7 ·13 andb= 23 · 32 · 52 · 11 ·17. Findd=gcd(a, b)andm=lcm(a, b).

(a) First we findd=gcd(a, b). Those primesp, which appear in bothaandb, 2, 3, and 11, will also appear in

d, and the exponent ofp,indwill be the smaller of its exponents inaandb. Thus

d=gcd(a, b)= 23 · 32 · 11 = 792