Multiples of one number in base-$10$

229 Views Asked by At

How can I prove that all the natural numbers has one multiple in base-$10$ such that this numbers is written just with zeros and ones?

For example, let $n=3$ then, exists al least one number, the $111$, such that is in base-10 and is written just using zeros and ones, in this case just ones or let $n=5$, in this case exists the $10$, that is multiple of $5$ and is written just using zeros and ones. I must use the Pigeonhole principle to prove this fact.

1

There are 1 best solutions below

3
On BEST ANSWER

Given a number $n$, recall that a number divided by $n$ can have $n$ possible remainders.

Now consider the $n$ numbers $$1; 11; 111; \cdots; \underbrace{11\ldots1}_{n\,\, 1\text{'s}}$$ If one of the above leaves a remainder $0$, we are done. If none of them leave a remainder $0$, by pigeonhole principle, since we have $n$ numbers and $n-1$ remainders (recall none of them have a remainder zero), two of them leave the same remainder. Subtract the smaller from the larger to get what you want.

As an example, let us see for $n=6$. Consider the numbers, $$1; 11; 111; 1111; 11111; 111111$$ Note that none of them leave a remainder $0$.

$1$ leaves a remainder $1$.

$11$ leaves a remainder $5$.

$111$ leaves a remainder $3$.

$1111$ leaves a remainder $1$.

$11111$ leaves a remainder $5$.

$111111$ leaves a remainder $3$.

Since $1$ and $1111$ leave the same remainder, subtract $1$ from $1111$ to get $1110$ and clearly $6 \vert 1110$.