Q: Prove that for any natural number, there exists a multiple that (in decimal form) only uses digits 0 and 1

Question

I'm supposed to prove the theorem in the title for a combinatorics class (continuation of discrete structures class). At the moment I have no idea how to aproach this question.

I would appreciate some pointers to set me on the right path. I don't really want to just copy a full solution and hand it over as mine.

Any help will be greatly appreciated.

Answer 1

Hints:

1. Prove this for prime powers first. (you will have to use a little trick to to extend this to all natural numbers and ensure that the digits remain $0$s and $1$s)
2. Consider all numbers with digits $0$s and $1$s. Apply the pigeonhole principle.

I hope this is helpful! Feel free to ask for further clarification.