Let a , b and c be positive integers, no two of which have a common divisor greater than 1. Show that 2abc - ab - bc - ca is the largest integer which cannot be expressed in the form xbc + yca + zab, where x, y, z are non-negative integers.
Solution
We start with the lemma that bc - b - c is the largest number which cannot be written as mb + nc with m and n non-negative. [Proof: 0, c, 2c, ... , (b-1)c is a complete set of residues mod b. If r > (b-1)c - b, then r = nc (mod b) for some 0 ≤ n ≤ b-1. But r > nc - b, so r = nc + mb for some m ≥ 0. That proves that every number larger than bc - b - c can be written as mb + nc with m and n non-negative. Now consider bc - b - c. It is (b-1)c (mod b), and not congruent to any nc with 0 ≤ n < b-1. So if bc - b - c = mb + nc, then n ≥ b-1. Hence mb + nc ≥ nc ≥ (b-1)c > bc - b - c. Contradiction.]
0, bc, 2bc, ... , (a-1)bc is a complete set of residues mod a. So given N > 2abc - ab - bc - ca we may take xbc = N (mod a) with 0 <= x < a. But N - xbc > 2abc - ab - bc - ca - (a-1)bc = abc - ab - ca = a(bc - b - c). So N - xbc = ka, with k > bc - b - c. Hence we can find non-negative y, z so that k = zb + yc. Hence N = xbc + yca + zab.
Finally, we show that for N = 2abc - ab - bc - ca we cannot find non-negative x, y, z so that N = xbc + yca + zab. N = -bc (mod a), so we must have x = -1 (mod a) and hence x ≥ a-1. Similarly, y ≥ b-1, and z ≥ c-1. Hence xbc + yca + zab ≥ 3abc - ab - bc - ca > N. Contradiction.
Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
14 Oct 1998