Number Theory Olympiad Problem

Heres a beasty number theory problem. Actually, I'm sure that to seasoned number...uh, theorists, that it's pretty easy.

Prove that every integer has a multiple which consists of only the digits 1 and 0

Consider the first n+1 integers which consist of only 1's:

. Where the (n+1)th integer has n+1 1's.

Now consider taking a number modulo n. The only possible values (after simplification) are , for a total of n possible "remainders".

Now consider taking each of our strings of 1's modulo n. There are n+1 of these strings, but only
n possible remainders. Therefore, two of them must have the same remainder when divided by n.

Let these two strings of 1's be:



And let their remainder, when divided by n, be r.

First, it is clear that will only consist of 1's and 0's. Specifically, the first digits will be 1's, and the last digits will be 0's.

Also consider taking this difference modulo n. We know they have the same remainder, r, when divided by n.



Since it has a remainder of 0 when divided by n, it must be a multiple of n. Problem solved.