IMO 1999 SL N5

Origin: ARM | Category: Number Theory

Problem

Let n, k be positive integers such that n is not divisible by 3 and k \geqn. Prove that there exists a positive integer m that is divisible by n and the sum of whose digits in decimal representation is k.

Solution

Since one can arbitrarily add zeros at the end of m, which increases divis- ibility by 2 and 5 to an arbitrary exponent, it suffices to assume 2, 5 ∤n. If (n, 10) = 1, there exists an integer w \geq2 such that 10w \equiv1 (mod n). We also note that 10iw \equiv1 (mod n) and 10jw+1 \equiv10 (mod n) for all integers i and j. Let us assume that m is of the form m = u i=1 10iw+v j=1 10jw+1 for integers u, v \geq0 (where if u or v is 0, the corresponding sum is 0). Obviously, the sum of the digits of m is equal to u + v, and also m \equivu + 10v (mod n). Hence our problem reduces to finding integers u, v \geq0 such that u + v = k and n | u + 10v = k + 9v. Since (n, 9) = 1, it follows that there exists some v0 such that 0 \leqv0 < n \leqk and 9v0 \equiv

−k (mod n) ⇒n | k + 9v0. Taking this v0 and setting u0 = k −v0 we obtain the desired parameters for defining m.