6th CanMO 1974 Problem 6 What is the largest integer n which cannot be represented as 8a + 15b with a and b non-negative integers? Solution
: 97 (=8.15 - 15 - 8). 98 = 6·15 + 8, 99 = 5·15 + 3·8, 100 = 4·15 + 5·8, 101 = 3·15 + 7·8, 102 = 2·15 + 9·8, 103 = 1·15 + 11·8, 104 = 13·8, 105 = 7·15. That gives 8 consecutive numbers. We can now get any larger number by adding a multiple of 8 to one of 98-105. To see that 97 cannot be expressed as 8a + 15b, note that b must be odd, but 97-15, 97-45, 97-75 are not multiples of 8. For the general case of relatively prime positive m, n > 1, the largest number which cannot be written as ma + nb is mn - m - n. 6th CanMO 1974 © John Scholes jscholes@kalva.demon.co.uk 10 June 2002