Question

See four problems attached. These will ask you to think about GCDs and prime factorizations, and also look at the related topic of Least Common Multiples (LCMs).

The prime factorization of numbers can be used to find the GCD. If we write the prime factorization of a and b as a = p a1 1 p a2 2 · p an n b = p b1 1 p b2 2 · p bn n (using all the primes pi needed to write either factorization), then gcd(a, b) is gcd(a, b) = p min(a1,b1) 1 p min(a2,b2) 2 . . . pmin(an,bn) n . (In other words, choose the smaller power required for either a or b.) For example, the prime factorization of 289 and 85 are given as follows: 289 = 172 85 = 51 171 Note that 85 needs a 5, but 289 doesn’t. However, we can rewrite the factorization as 289 = 172 = 50 172 85 = 5 · 17 = 51 171 so that both factorizations use the same primes. (Note the 5 to the zero power!) Then gcd(85, 289) = 50171 = 17, by choosing the smaller power in each case.

Part a: Use the above technique to find the GCD of the following two numbers, written in their prime factorization: (Note that as above, not every prime already appears as part of each factorization.) 2 3 5 2 111 472 2 1 3 3 5 1 7 5 131 You can write your final answer in factored form. Sometimes instead of the GCD, we want the Least Common Multiple, or LCM, of two numbers. lcm(a, b) is the smallest number which is a multiple of both a and b. (You have used LCMs to find the least common denominators for fractions.) For example, lcm(6, 8) = 24, because 24 is the first number that is a multiple of both 6 and 8: Multiples of 6: 6, 12, 18, 24 , 30, 36, . . . Multiples of 8: 8, 16, 24 , 32, 40, . . . The technique for finding GCDs from the prime factorization can be modified to find the LCM: If a and b are written in prime factorizations with the same primes a = p a1 1 p a2 2 · p an n b = p b1 1 p b2 2 · p bn n 1 2 then lcm(a, b) = p max(a1,b1) 1 p max(a2,b2) 2 . . . pmax(an,bn) n . In other words, do as before, but choose the larger exponent on each prime. For example, 6 = 2 · 3 and 8 = 23 . Writing these using the same primes gives 6 = 21 3 1 8 = 23 3 0 and lcm(6, 8) = 23 3 1 = 24.

Part b: Use the above technique to find the LCM of the numbers given below in their prime factorization (same numbers as before): 2 3 5 2 111 472 2 1 3 3 5 1 7 5 131

Part c: Given the ways above to find the LCM and the GCD, explain why the following relationship holds for any two positive integers a and b: a · b = gcd(a, b) · lcm(a, b). (You don’t have to write a formal proof, but explain why it should hold.)

Part d: The result of Part c above provides a way to find the LCM if we can find the GCD. (Note that we already know an efficient way to compute GCDs!) Suppose that you know that for two numbers a and b, gcd(a, b) = 34, and that a · b = 85, 680. Compute lcm(a, b).

Answer 1

I am giving the solution for part (C) and (D) . Hope it will be helpful .

in part (a) and (b) the number given in prime factorization is not clear to me. It may be for the spacing between them.