Cryptography Reference
In-Depth Information
Figure 3.7
Factorization of y
Common
Factors
Common
Factors
Factorization of x
Figure 3.8
Factorization of y
Common
Factors
Common
Factors
Factorization of x
Figure 3.9
lcm of x and y
Common
Factors
Consider now the integer formed by the product of the factors of
with the remaining
y
factors of
. (See Figure 3.9.)
Clearly, this integer is divisible by both
x
. Furthermore, if we attempt to remove
any more factors from this integer, it will no longer be divisible by either
and
x
y
or
(possibly
x
y
neither). This is clearly the least common multiple of
and
. This yields a convenient for-
x
y
mula for the least common multiple; that is,
lcm(
x
,
y
) =
xy
/(
x
,
y
).
This argument doesn't really count as a proof, and you should confirm this. (Hint: Use
the prime power factorization of
x
and
y
.)
Search WWH ::
Custom Search