P3.1.5

P3.1.5 Let z and y be any two positive numbers. Using the definitions in Problems 3.1.3.and 3.1.4, show that ged (a) by using the characterizations of gcd and lcm in terms of the prime factorization, and (b) directly by proving that for any natural z, z is a common factor of z and y if and only if z divides ry and xy/z is a common multiple of x and y. P3.1.3 The greatest common divisor of two naturals r and y is the largest number that divides both r and y. For example, gcd(8, 12) 4 because 4 divides both 8 and 12 and no larger natural divides both (a) What is the greatest common divisor of 60 and 339? How do you know? (b) What are the possible greatest common divisors of p and z, if p is a prime number? How can you tell which is the correct one, given any x? 3-7 (c) What is the greatest common divisor of 23-32-54 and 22-34-53? Can you describe method to find the greatest common divisor of any two numbers, given their factorization into primes? (You might not be able to prove that your method is correct, of course, without results from later in this chapter). P3.1.4 The least common multiple of two naturals and y is the smallest natural that both a and y divide. For example, lcm(8, 12) 24 because 8 and 12 each divide 24, and there is no smaller natural that both 8 and 12 divide. (a) Find the least common multiple of 60 and 339. (b) Find the least common multiple of 23 32.54 and 22.34.53 (c) Describe a general method to find the least common multiple of two naturals, given their factorization into primes (and assuming that the factorization exists and is unique)