Maths Olympiad Prep

Library / /2 of 31

Number theory Difficulty 7.5 National olympiad, round 2 Prove it Baltic Way

Let's say that a digit is *eternal* for a positive integer nn, if it is contained in every multiple of nn. Find all digits which are eternal for at least one positive integer.

Solution

The only such a digit is 00, it is contained in every multiple of 1010. Let's show that no other digit is eternal for any positive integer.

Assume that some digit is eternal for integer nn. Consider remainders of numbers
1,11,111,,1111n+1 1, 11, 111, \dots, \underbrace{11\dots11}_{n+1}
modulo nn. By the pigeonhole principle two of these remainders are equal, therefore their difference which has the form 11100011\ldots100\ldots0, is a multiple of nn. If we multiply this number by 22 then we get a multiple of nn of the form 22200022\ldots200\ldots0. But the only common digit for these two multiples is 00.

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.