A challenging arithmetic / number theory problem

While visiting MIT on Thursday I stumbled on this really interesting problem:

Show that any positive integer has a (positive) multiple which has only the digits 1 and 0 when represented in base 10.

This is – obviously – not a problem intended for kids, but I thought that it would be fun to talk through it with them since the ideas in the solution are actually accessible to kids.

Here’s the introduction to the problem and a few initial thoughts from my kids:

After their initial thoughts we moved on to talking about the solution. The first step involves looking at numbers that only have 1’s. This step gives us a nice opportunity to talk about remainders.

Also, finding a way to describe the patter in the remainders is a nice challenge for the kids.

Now that we’ve understood a little bit about the remainders, we move to the key idea in the solution – as we look through the numbers 1, 11, 111, and etc, we’ll eventually find two numbers that have the same remainder when we divide by .

This is a challenging idea for kids to understand, but we make some nice progress towards understanding that idea. It is a surprise application of the Pigeonhole Principle.

Now for the last step in the solution – once we find a two numbers in the list 1, 11, 111, 1111, and etc with the same remainder when we divide by , how do we find a multiple of with only 1’s and 0’s?

Finally, we wrap up by exploring a few other similar ideas – for example, do all positive integers have a multiple consisting of only 3’s and 0’s? How about one consisting of only 2’s and 3’s?

So, a really neat (though advanced) math idea that kids can understand. Working through this problem is a nice way to talk about remainders and also about place value. I don’t go through problems like this one very often, but with the right problem it is neat to be able to talk about some advanced ideas with kids!