The Integers - Introduction to Cryptography with Java Applets - page 83

where each , and that these factors are in

nondecreasing order. Remove any common primes from the two factorizations, and re-index
if necessary to obtain

p i and q j is prime, i = 1, 2, . . . , m , j = 1, 2, . . . , k

p 1 p 2 ... p v = q 1 q 2 ... q w , where v ≤ m , w ≤ k .

All of the factors on the left-hand side are different from the factors on the right. Now,
consider p 1 , which divides q 1 q 2 ... q w (since p 1 | p 1 p 2 ... p v , which is equal to q 1 q 2 ... q w ).
Proposition 14 says then that p 1 must divide q i for some i between 1 and w (inclusive), but
this is clearly impossible, since each q i is prime, and each different from p 1 . Thus, the prime
factorization of n is unique.

The Fundamental Theorem of Arithmetic reveals that integers greater than 1 factor
uniquely into primes. We often order these factors from the smallest to the largest, and group
those that are equal together. We call this the prime power factorization of an integer.

E XAMPLES .

• 24 = 2 3 · 3

• 588 = 2 2 · 3 · 7 2

• 450 = 2 · 3 2 · 5 2

Before we move on to the next chapter, we should discuss the least common multiple of
two integers. We will derive a convenient formula to compute it, based on the greatest com-
mon divisor. Proving the validity of this formula is easy with the Fundamental Theorem of
Arithmetic.

Definition
The least common multiple of two integers

x and y , not both zero, is the smallest pos-

itive integer that is divisible by both x and y . We denote the least common multiple, or

lcm, of x and y as lcm( x , y ).

if we reason in the following
way: Take the prime power factorization of the two integers, and note which factors they
have in common. Note that the product

It isn't difficult to compute the lcm of two integers x and y

P of these common factors must be the gcd of x and

y . To see this, note that P | x and P | y , and furthermore:

• If we multiply P by another factor of x (or y ), that product will then fail to divide y (or x ),
and
• if we remove a factor from P , we then have a common divisor of x and y which is smaller
than P .

Thus, ). (See Figure 3.7.)

Now, remove one set of the common factors; say, from

P = ( x , y

x . (See Figure 3.8.)