IMO 1987 SL 8

Origin: HUN

Problem

(a) Let (m, k) = 1. Prove that there exist integers a1, a2, . . . , am and b1, b2, . . . , bk such that each product aibj (i = 1, 2, . . ., m; j = 1, 2, . . . , k) gives a different residue when divided by mk. (b) Let (m, k) > 1. Prove that for any integers a1, a2, . . . , am and b1, b2, . . . , bk there must be two products aibj and asbt ((i, j) ̸= (s, t)) that give the same residue when divided by mk.

Solution

(a) Consider ai = ik + 1, i = 1, 2, . . ., m; bj = jm + 1, j = 1, 2, . . ., k. Assume that mk | aibj −asbt = (ik + 1)(jm + 1) −(sk + 1)(tm + 1) = km(ij −st)+m(j −t)+k(i−s). Since m divides this sum, we get that m | k(i −s), or, together with gcd(k, m) = 1, that i = s. Similarly j = t, which proves part (a).

(b) Suppose the opposite, i.e., that all the residues are distinct. Then the residue 0 must also occur, say at a1b1: mk | a1b1; so, for some a′ and b′, a′ | a1, b′ | b1, and a′b′ = mk. Assuming that for some i, s ̸= i, a′ | ai −as, we obtain mk = a′b′ | aib1 −asb1, a contradiction. This shows that a′ \geqm and similarly b′ \geqk, and thus from a′b′ = mk we have a′ = m, b′ = k. We also get (1): all ai’s give distinct residues modulo m = a′, and all bj’s give distinct residues modulo k = b′. Now let p be a common prime divisor of m and k. By (∗), exactly p−1 p m of ai’s and exactly p−1 p k of bj’s are not divisible by p. Therefore there are precisely (p−1)2 p2 mk products aibj that are not divisible by p, although from the assumption that they all give distinct residues it follows that the number of such products is p−1 p mk ̸= (p−1)2 p2 mk. We have arrived at a contradiction, thus proving (b).