Maths Olympiad Prep

Library / /31 of 92

Number theory Difficulty 6.2 National olympiad Prove it Iran

We call a natural number nn nice if it has no zero digit in its decimal representation and it has a digit bb in this representation such that the resulting number would be a divisor of nn, after its removal. Prove that there are only finitely many nice numbers.

Solution

We prove that a nice number has at most 20 digits which proves that there are finitely many nice numbers. Assume that n=abcn = \overline{abc} where a,ca, c can have more than one digit and bb is a digit such that ac=nk\overline{ac} = nk for some natural number kk. If cc has tt digits, then n=acn = \overline{ac} (mod 10t110^{t-1}) therefore we have kn=nkn = n (mod 10t110^{t-1}). Because there is no zero digit in nn, we know that gcd(n,2)=1\text{gcd}(n, 2) = 1 or gcd(n,5)=1\text{gcd}(n, 5) = 1. If gcd(n,2)=1\text{gcd}(n, 2) = 1 then we have k=1k = 1 (mod 2t12^{t-1}), on the other hand n<100acn < 100\overline{ac} so k<7k < 7 which implies that t<9t < 9. Similarly if gcd(n,2)=5\text{gcd}(n, 2) = 5 we have t<4t < 4.

Now assume that aa has more than 10 digits, we have acac0\overline{ac} \mid \overline{ac0}, acabc\overline{ac} \mid \overline{abc} therefore acabcac0\overline{ac} \mid \overline{abc} - \overline{ac0}. But the previous paragraph implies that abcac0\overline{|abc - ac0|} has at most 10 digits which implies that abcac0ac\overline{abc} - \overline{ac0} \mid \overline{ac}. So we should have n=ac0n = \overline{ac0} which is in contradiction with the fact that nn is an interesting number.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.