PUMaC 2013 · 数论（A 组） · 第 6 题

PUMaC 2013 — Number Theory (Division A) — Problem 6

[ 6 ] What is the largest positive integer that cannot be expressed as a sum of non-negative integer multiples of 13 , 17 and 23?

解析

[ 6 ] What is the largest positive integer that cannot be expressed as a sum of non-negative integer multiples of 13 , 17 and 23? Solution There are numerous approaches to this problem, and no approach that attempts to find the last obtained remainder modulo any of the three numbers in sums of them will fail. The below is our approach: By trial, the following gives the smallest positive integer in the form 17 a + 23 b for integers a, b ≥ 0 in different residue classes modulo 13 (starting from the class 0): 91 , 40 , 80 , 68 , 17 , 57 , 97 , 46 , 34 , 74 , 23 , 63 , 51 . (Indeed, one should note that 5(17) ≡ 2(23) (mod 13) and 3(23) ≡ 17 (mod 13) to reduce the number of cases for consideration.) The largest n which is not of the form 13 x + 17 y + 23 z is therefore 97 − 13 = 84.