40th IMO shortlist 1999/N5 solution

40th IMO 1999 shortlist

Problem N5

Show that for any n not divisible by 3 and k ≥ n, there is a multiple of n which has sum of digits k.

Solution

We start by considering n not divisible by 2 or 5. We can find a positive integer h such that 10^h = 1 mod n. Consider the number N = (10^h + 10^2h + 10^3h + ... + 10^Ah) + (10^h+1 + 10^2h+1 + 10^3h+1 + ... + 10^Bh+1). Each number in the first group is 1 mod n and each number in the second group is 10 mod n, so N = A + 10B mod n. Also N has A + B digits 1 and the rest 0, so its sum of digits is A + B. We want A + B = k. But since N is relatively prime to 9, one of k, k + 9, k + 2.9, ... , k + (n-1)9 must be 0 mod n. So we can find B such that k + 9B = 0 mod n and 0 ≤ B < n. Then take A = k - B. Since k ≥ n, A is positive. Also A + B = k and A + 10B = k + 9B = 0 mod n. Hence N = 0 mod n, so N is a multiple of n.

Now if n = 2^a5^bm, where m is not divisible by 2 or 5, then we can find N which is a multiple of n and has sum of digits k. Take c = max(a, b). Then N.10^c meets the requirements.

For example, take n = 19 and k = 22. Then we can take h = 18. We have 22 + 9.6 = 0 mod 19, so we take B = 6, A = 16. Hence we get N = (10¹⁸ + 10³⁶ + 10⁵⁴ + ... + 10²⁸⁸) + (10¹⁹ + ... + 10¹⁰⁹). So the process does not generate small numbers!

40th IMO shortlist 1999