The Art and Craft of Problem Solving

224 CHAPTER 7 NUMBER THEORY

in other words, 60 has two completely different E-prime factorizations, and

consequently, if x,y E E satisfy 2x = lOy, even though 2 and 10 are both E­

primes, we cannot conclude that (^10) Ix, 2Iy. After all, x could equal 30, and y
could equal 6. In this case, x is not a multiple of 10 in E, since 30 is an E­
prime. Likewise y is not a multiple of 2.
This example is rather contrived, but it should convince you that the FfA has real
content. Certain number systems have unique factorization, and others do not. The
set Z possesses important properties that make the FfA true. We will discover these
properties and construct a proof of the FfA in the course of this section, developing
useful problem-solving tools along the way.

GCD, LCM, and the Division Algorithm

Given t wo natural numbers a, b, their greatest common factor, written (a,b) or some­

times as GCD(a,b), is defined to be the largest integer that divides both a and b.

For example, (66, 150 ) = 6 and (100,250) = 25 and (4096,999) = 1. If the GCD of

two numbers is 1, we say that the two numbers are relatively prime. For example,

(p, q) = 1 if P and q are different primes. We will frequently use the notation a..l b

in place of (a, b) = 1. Likewise, we define the least common multiple, or LCM, of

a and b to be the least positive integer that is a multiple of both a and b. We use the

notation [a,b] or LCM(a, b).^2

7.1. 3 Here are some important facts about GCD and LCM that you should think about

and verify. [You may assume the truth of the FfA, if you wish, for (a), (b), and (c).]

(a) a..l b is equivalent to saying that a and b share no common primes in their PPFs.

(b) If a = pr^1 p�^2 ... p�' and b = p{l p{^2 ... p f' (where some of the exponents may be

zero), then

(a, b) = p�

in(el,tI l p�in(e 2 ,h)

... p�

in(e" f,)

,

[ a, b] = max(el,tI l max(e 2 ,h) max(e" f,)

P I P 2 ... PI.

For example, the GCD of 360 = 23. 32 .5 and 1597050 = 2. 33. 52. 7. 132 is

21. 32. 51. 7 °. 13 ° = 90.

(c) (a,b)[a,b] = ab for any positive integers a,b.

(d) If gla and glb, then glax + by, where x and y can be any integers. We call a

quantity like ax + by a linear combination of a and b.

(e) Consecutive integers are always relatively prime.

(f) If there exist integers x, y such that ax + by = 1, then a ..1 b.

7.1.4 Recall the division algorithm, which you encountered in Problem 3.2. 17 on

page 83.

(^2) We can also define OCD and LCM for more than two integers. For example, ( (^70) , 100 ,2 25 ) = 5 and
[ 1 ,2,^3 ,^4 ,5,6,^7 ,8,^9 J = 2520.