Maths Olympiad Prep

Library / /475 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

28. N5 (IRN) IMO6{ }^{\mathrm{IMO} 6} We call a positive integer alternate if its decimal digits are alternately odd and even. Find all positive integers nn such that nn has an alternate multiple.

Solution

28. If nn is divisible by 20, then every multiple of nn has two last digits even and hence it is not alternate. We shall show that any other nn has an alternate multiple. (i) Let nn be coprime to 10. For each kk there exists a number Ak(n)=A_{k}(n)= 1001001001=10mk110k1(mN)\overline{10 \ldots 010 \ldots 01 \ldots 0 \ldots 01}=\frac{10^{m k}-1}{10^{k}-1}(m \in \mathbb{N}) that is divisible by nn (by Euler's theorem, choose m=φ[n(10k1)])\left.m=\varphi\left[n\left(10^{k}-1\right)\right]\right). In particular, A2(n)A_{2}(n) is alternate. (ii) Let n=25rn1n=2 \cdot 5^{r} \cdot n_{1}, where r1r \geq 1 and (n1,10)=1\left(n_{1}, 10\right)=1. We shall show by induction that, for each kk, there exists an alternative kk-digit odd number MkM_{k} that is divisible by 5k5^{k}. Choosing the number 10A2r(n1)M2r10 A_{2 r}\left(n_{1}\right) M_{2 r} will then solve this case, since it is clearly alternate and divisible by nn. We can trivially choose M1=5M_{1}=5. Let there be given an alternate rr-digit multiple MrM_{r} of 5r5^{r}, and let c{0,1,2,3,4}c \in\{0,1,2,3,4\} be such that Mr/5rM_{r} / 5^{r} \equiv c2r(mod5)-c \cdot 2^{r}(\bmod 5). Then the (r+1)(r+1) digit numbers Mr+c10rM_{r}+c \cdot 10^{r} and Mr+(5+c)10rM_{r}+(5+c) \cdot 10^{r} are respectively equal to 5r(Mr/5r+2rc)5^{r}\left(M_{r} / 5^{r}+2^{r} \cdot c\right) and 5r(Mr/5r+2rc+52r)5^{r}\left(M_{r} / 5^{r}+2^{r} \cdot c+5 \cdot 2^{r}\right), and hence they are divisible by 5r+15^{r+1} and exactly one of them is alternate: we set it to be Mr+1M_{r+1}. (iii) Let n=2rn1n=2^{r} \cdot n_{1}, where r1r \geq 1 and (n1,10)=1\left(n_{1}, 10\right)=1. We show that there exists an alternate 2r2 r-digit number NrN_{r} that is divisible by 22r+12^{2 r+1}. Choosing the number A2r(n1)NrA_{2 r}\left(n_{1}\right) N_{r} will then solve this case. We choose N1=16N_{1}=16, and given NrN_{r}, we can prove that one of Nr+N_{r}+ m102rm \cdot 10^{2 r}, for m{10,12,14,16}m \in\{10,12,14,16\}, is divisible by 22r+32^{2 r+3} and therefore suitable for Nr+1N_{r+1}. Indeed, for Nr=22r+1dN_{r}=2^{2 r+1} d we have Nr+m102r=N_{r}+m \cdot 10^{2 r}= 22r+1(d+5rm/2)2^{2 r+1}\left(d+5^{r} m / 2\right) and d+5rm/20(mod4)d+5^{r} m / 2 \equiv 0(\bmod 4) has a solution m/2m / 2 \in {5,6,7,8}\{5,6,7,8\} for each dd and rr. Remark. The idea is essentially the same as in (SL94-24).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.