# A positive multiple of any positive integer exists that only has the digits {0,1}

#### whiteman

1. The problem statement, all variables and given/known data
Let k be any positive integer. Prove that there exists a positive
integer multiple n of k such that the only digits in n are 0s and
1s. (Use the pigeonhole principle.)

2. Relevant equations
The General Pigeonhole Principle
If more than mk things are distributed into k boxes then
at least one box receives more than m things.

3. The attempt at a solution
Don't know where to start off. I just need a bit of a nudge and hopefully that'll get me started. thanks :)

Related Precalculus Mathematics Homework News on Phys.org

#### Dick

Homework Helper
Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?

#### jbunniii

Homework Helper
Gold Member
Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?
Very nice! I thought about this problem on the drive home and came up with a solution, but it's a bit more complicated, entailing two cases depending on whether 10 is a unit or a zero divisor mod k. Your solution is much quicker and more elementary. On the other hand, I think my method might find the smallest possible answer, but I haven't written down the details yet.

#### Dick

Homework Helper
Very nice! I thought about this problem on the drive home and came up with a solution, but it's a bit more complicated, entailing two cases depending on whether 10 is a unit or a zero divisor mod k. Your solution is much quicker and more elementary. On the other hand, I think my method might find the smallest possible answer, but I haven't written down the details yet.
Yeah, it is nice. This is sort of a classic problem, I've seen it at least once before. It's classic pigeonhole. I didn't make up the solution. I just remembered it. I hadn't even thought about finding the smallest solution. If you can do that it would be interesting.

Last edited:

#### aldebaran19

Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?
This is an interesting question but can't figure out what to do! What do you do with the sequence {1,11,111,...}?

#### Dick

Homework Helper
This is an interesting question but can't figure out what to do! What do you do with the sequence {1,11,111,...}?
You don't do anything in particular with it as a sequence. You just think about the possible values of the remainders after dividing by k of those values. Then think 'pigeonhole principle'.

#### whiteman

thanks for all the help, guys, especially Dick. i was able to get it from the first post you gave :)

"A positive multiple of any positive integer exists that only has the digits {0,1}"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving