A starter problem that might be useful: Suppose A has remainder p when divided by n, and suppose B has remainder q when divided by n. What will the remainder be when (A - B) is divided by n? (In particular, what happens if p = q?)

 

Now the main problem, which is quite hard!

Take any integer n that is coprime to 10, and any n-digit number.

Ryan claims that you can find a string of consecutive digits within that number that forms a multiple of n.

For example, in the 7-digit number 1523439 I can find the string 343, which is a multiple of 7.

Can you prove it?

Bonus: can you explain why it's necessary that n is coprime to 10?

 

Hint: a neat approach uses the "pigeonhole principle": if I have n categories, and n+1 objects to assign to those categories, then at least one of those categories will get more than one object.

For example, if I have to share 10 ice creams among 9 of my friends, someone is going to get more than 1 ice cream.