4.5.2 THE GREATEST COMMON DIVISOR 317 that is a multiple of (i.e., evenly divisible by) both u and w; and lcm(O,O) = 0. The classical method for teaching children how to add fractions u/u + v/v is to train them to find the O; (9) u. w = gcd(u, w) . lcm(u, v), if u, 2) 2 0; (10) gcd(lcm(u, II), lcm(u, w)) = lcm(u, gcd(v, w)); (11) lcm(gcd(u, v), gcd(u, w)) = gcd(u, lcm(v, w)). (12) The latter two formulas are distributive laws analogous to the familiar identity uz, + uw = u(w + w). Equation (10) reduces the calculation of gcd(u, v) to the calculation of lcm(u, w), and conversely. Euclid s algorithm. Although Eq. (6) is useful for theoretical purposes, it is generally no help for calculating a greatest common divisor in practice, because it requires that we first determine the factorization of u and v. There is no known method for finding the prime factors of an integer very rapidly (see Section 4.5.4). But fortunately there is an efficient way to calculate the greatest common divisor of two integers without factoring them, and, in fact, such a method was discovered over 2250 years ago; this is Euclid s algorithm, which we have already examined in Sections 1.1 and 1.2.1.
This entry was posted
on Friday, January 18th, 2008 at 8:08 am and is filed under J2EE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.