Browse · MathNet
PrintBaltic 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 .
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