IMO 1975 SL 11

Origin: GBR

Problem

Let a1, a2, a3, . . . be any infinite increasing sequence of pos- itive integers. (For every integer i > 0, ai+1 > ai.) Prove that there are infinitely many m for which positive integers x, y, h, k can be found such that 0 < h < k < m and am = xah + yak.

Solution

Let (aki) be the subsequence of (ak) consisting of all ak’s that give re- mainder r upon division by a1. For every i > 1, aki \equivak1 (mod a1); hence aki = ak1 + ya1 for some integer y > 0. It follows that for ev- ery r = 0, 1, . . . , a1 −1 there is exactly one member of the corresponding (aki)i\geq1 that cannot be represented as xal+yam, and hence at most a1+1 members of (ak) in total are not representable in the given form.