Skip to main content
OlympiadHQ

Browse · MathNet

Print

Baltic Way shortlist

Baltic Way number theory

Problem

Let's say that a digit is eternal for a positive integer , if it is contained in every multiple of . Find all digits which are eternal for at least one positive integer.
Solution
The only such a digit is , it is contained in every multiple of . Let's show that no other digit is eternal for any positive integer.

Assume that some digit is eternal for integer . Consider remainders of numbers modulo . By the pigeonhole principle two of these remainders are equal, therefore their difference which has the form , is a multiple of . If we multiply this number by then we get a multiple of of the form . But the only common digit for these two multiples is .
Final answer
0

Techniques

Divisibility / FactorizationModular ArithmeticPigeonhole principle