question archive Let a, b 2 1 be integers with prime factorizations a = P1 P2 02
Let a, b 2 1 be integers with prime factorizations a = P1 P2 02
Subject:MathPrice: Bought3
Let a, b 2 1 be integers with prime factorizations a = P1 P2 02 . . . Pn . b = P1 P2 bn 1b2 . . . Pn for primes p1 < p2 < . . . < Pn and exponents a1, . . ., an, b1, . . ., bn 2 0. (a) Use the Fundamental Theorem of Arithmetic to explain why GCD(a, b) = pmin(@1,bi) min(az,b2) . . . pmin(an,bn) on LCM(a, b) = P1 pmax(a1,bi) max(a2,b2) . .. pmax(an,bn) Here min(x, y) denotes the minimum of two integers x, y and max(r, y) denotes their maximum (obviously!). (b) Suppose a = 25 .37 .5 . 112 . 101 and b = 23.52 . 11 . 132. Write down the numbers GCD(a, b) and LCM(a, b), leaving your answers as products of prime powers. This illustrates how easy it is to find GCDs and LCMs if you know the prime factorizations (but prime factorizations are hard to find for big numbers!) (c) Using (a), show that a . b = GCD(a, b) . LCM(a, b). This means you can easily find LCM(a, b) if you know GCD(a, b), and the latter can be computed quickly using the Euclidean Al- gorithm
