Suppose is a sequence of integers such that and are two distinct digits of the number , and for all .
Let be the number given by the string repeated times. Show that cannot be for any positive integer .
, 2014
Solution
Note first that
Hence, if , then .
Given the possible values for and , we see that is congruent to either or modulo , depending on whether or not we select as one of the two initial terms of the sequence. Similarly, is congruent to either or modulo , depending on whether or not . In any case, neither nor is divisible by .
By the Little Theorem of Fermat, unless .
Therefore, if neither nor is divisible by , then
By induction it follows now that for all .
Finally, using that any integer is congruent to its sum of digits modulo , we find that
and we conclude that for all .
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.