IMO 1978 SL 5

Origin: GDR

Problem

For every integer d \geq1, let Md be the set of all positive integers that cannot be written as a sum of an arithmetic progression with difference d, having at least two terms and consisting of positive integers. Let A = M1, B = M2 ∖{2}, C = M3. Prove that every c \inC may be written in a unique way as c = ab with a \inA, b \inB.

Solution

We first explicitly describe the elements of the sets M1, M2. x ̸\inM1 is equivalent to x = a+(a+1)+\cdot \cdot \cdot+(a+n−1) = n(2a+n−1)/2 for some natural numbers n, a, n \geq2. Among n and 2a + n −1, one is odd and the other even, and both are greater than 1; so x has an odd factor \geq3. On the other hand, for every x with an odd divisor p > 3 it is easy to see that there exist corresponding a, n. Therefore M1 = {2k | k = 0, 1, 2, . . .}. x ̸\inM2 is equivalent to x = a+(a+2)+\cdot \cdot \cdot+(a+2(n−1)) = n(a+n−1), where n \geq2, i.e. to x being composite. Therefore M2 = {1} \cup{p | p = prime}. x ̸\inM3 is equivalent to x = a + (a + 3) + \cdot \cdot \cdot + (a + 3(n −1)) = n(2a + 3(n −1))/2. It remains to show that every c \inM3 can be written as c = 2kp with p prime. Suppose the opposite, that c = 2kpq, where p, q are odd and q \geqp \geq3. Then there exist positive integers a, n (n \geq2) such that c = n(2a + 3(n −1))/2 and hence c ̸\inM3. Indeed, if k = 0, then n = 2 and 2a + 3 = pq work; otherwise, setting n = p one obtains a = 2kq − 3(p −1)/2 \geq2q −3(p −1)/2 \geq(p + 3)/2 > 1.