IMO 1983 SL 18

Origin: FRG

Problem

Let a, b, c be positive integers satisfying (a, b) = (b, c) = (c, a) = 1. Show that 2abc −ab −bc −ca is the largest integer not repre- sentable as xbc + yca + zab with nonnegative integers x, y, z.

Solution

Let (x0, y0, z0) be one solution of bcx + cay + abz = n (not necessarily nonnegative). By subtracting bcx0 + cay0 + abz0 = n we get bc(x −x0) + ca(y −y0) + ab(z −z0) = 0.

Since (a, b) = (a, c) = 1, we must have a|x−x0 or x−x0 = as. Substituting this in the last equation gives bcs + c(y −y0) + b(z −z0) = 0. Since (b, c) = 1, we have b|y −y0 or y −y0 = bt. If we substitute this in the last equation we get bcs+bct+b(z−z0) = 0, or cs+ct+z −z0 = 0, or z −z0 = −c(s + t). In x = x0 + as and y = y0 + bt, we can choose s and t such that 0 \leqx \leqa−1 and 0 \leqy \leqb−1. If n > 2abc−bc−ca−ab, then abz = n −bcx −acy > 2abc −ab −bc −ca −bc(a −1) −ca(b −1) = −ab or z > −1, i.e., z \geq0. Hence, it is representable as bcx + cay + abz with x, y, z \geq0. Now we prove that 2abc−bc−ca−ab is not representable as bcx+cay+abz with x, y, z \geq0. Suppose that bcx + cay + abz = 2abc −ab −bc −ca with x, y, z \geq0. Then bc(x + 1) + ca(y + 1) + ab(z + 1) = 2abc with x+1, y+1, z+1 \geq1. Since (a, b) = (a, c) = 1, we have a|x+1 and thus a \leqx + 1. Similarly b \leqy + 1 and c \leqz + 1. Thus bca + cab + abc \leq2abc, a contradiction.