IMO 2004 SL N5

Origin: IRN | Category: Number Theory

Problem

We call a positive integer alternate if its decimal digits are alternately odd and even. Find all positive integers n such that n has an alternate multiple.

Solution

If n is divisible by 20, then every multiple of n has two last digits even and hence it is not alternate. We shall show that any other n has an alternate multiple. (i) Let n be coprime to 10. For each k there exists a number Ak(n) = 10 . . . 010 . . .01 . . .0 . . . 01 = 10mk−1 10k−1 (m \inN) that is divisible by n (by Euler’s theorem, choose m = ϕ[n(10k −1)]). In particular, A2(n) is alternate.

(ii) Let n = 2 \cdot 5r \cdot n1, where r \geq1 and (n1, 10) = 1. We shall show by induction that, for each k, there exists an alternative k-digit odd num- ber Mk that is divisible by 5k. Choosing the number 10A2r(n1)M2r will then solve this case, since it is clearly alternate and divisible by n. We can trivially choose M1 = 5. Let there be given an alternate r-digit multiple Mr of 5r, and let c \in{0, 1, 2, 3, 4} be such that Mr/5r \equiv −c \cdot 2r (mod 5). Then the (r + 1)digit numbers Mr + c \cdot 10r and Mr + (5 + c) \cdot 10r are respectively equal to 5r(Mr/5r + 2r \cdot c) and 5r(Mr/5r + 2r \cdot c + 5 \cdot 2r), and hence they are divisible by 5r+1 and exactly one of them is alternate: we set it to be Mr+1. (iii) Let n = 2r\cdotn1, where r \geq1 and (n1, 10) = 1. We show that there exists an alternate 2r-digit number Nr that is divisible by 22r+1. Choosing the number A2r(n1)Nr will then solve this case. We choose N1 = 16, and given Nr, we can prove that one of Nr + m \cdot 102r, for m \in{10, 12, 14, 16}, is divisible by 22r+3 and therefore suitable for Nr+1. Indeed, for Nr = 22r+1d we have Nr + m \cdot 102r = 22r+1(d + 5rm/2) and d + 5rm/2 \equiv0 (mod 4) has a solution m/2 \in {5, 6, 7, 8} for each d and r. Remark. The idea is essentially the same as in (SL94-24).