29th CanMO 1997 Problem 1 How many pairs of positive integers have greatest common divisor 5! and least common multiple 50! ? Solution
: 2 14 . Let m, n satisfy the conditions. Clearly each must be divisible by 5!. Now 50!/5! is divisible by 15 distinct primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47. The precise power in each case does not matter. Suppose 11 a is the highest power of 11 dividing 50!/5!. Then mn must be divisible by 11 a . But we cannot have 11 dividing both m and n, otherwise we would increase their greatest common divisor. So either 11 a divides m, or it divides n. To avoid double-counting, we may assume that 47 divides m. Then for each of the other 14 primes we have two choices, giving 2 14 possible numbers. [We cannot introduce any additional factors beyond those in 50!/5! or we would increase the lcm.] 29th CanMO 1997 © John Scholes jscholes@kalva.demon.co.uk 15 June 2002