Is it true that every integer you can think of has a multiple written out only with \(0\)s and \(1\)s?

Problem statement

Let \(k \in \mathbb{Z}\) be an integer. Is there an integer \(n\) such that \(n\) is a multiple of \(k\) and \(n\) only has \(0\)s and \(1\)s in its decimal expansion?

As an example, if \(k = 2\) we could have \(n = 10\).

If you need any clarification whatsoever, feel free to ask in the comment section below.

Solution

The answer is yes, any integer \(k\) has a "binary multiple" \(n\). To show this is true, we will build \(n\) starting from \(k\).

Assume \(k\) is positive, and consider the following \(k\) integers:

\[ \big\{ 1, 11, 111, \cdots, \underbrace{1\cdots1}_{k\ 1\text{s}} \big\}\]

(which can be formally written out as taking \(\{c_i\}_{i = 1}^k\) with \(c_1 = 1\) and \(c_{i+1} = 10*c_i + 1\)).

Then only one of two things can happen. Either one of \(c_i\) is a multiple of \(k\) (in which case all is good) or not. But if no \(c_i\) is a multiple of \(k\), then we can consider the remainders of the \(c_i\) modulo \(k\):

\[ \{ c_1\ \text{mod}\ k, c_2\ \text{mod}\ k, \cdots, c_k\ \text{mod}\ k \} \subseteq \{ 1, \cdots, k - 1 \}\]

We say that the remainders of the \(c_i\) are contained in the set to the right because none of the remainders is \(0\), otherwise one of the \(c_i\) would be a multiple of \(k\).

Notice the left-hand set is built by taking the remainders of the \(k\) different \(c_i\) but the right-hand set only has \(k - 1\) elements. The [pigeonhole principle][pigeonhole-principle-wiki] then says that there are at least two different \(c_i\), \(c_j\) being mapped to the same element in the right-hand set, i.e. \(c_i \equiv c_j \ \text{mod}\ k\). Assume we have \(j > i\), meaning \(c_j > c_i\) and, in particular:

\[ \begin{cases} c_j - c_i \equiv 0\ \text{mod}\ k \\ c_j - c_i = \underbrace{1\cdots 1}_{j-i\ 1\text{s}} \underbrace{0\cdots 0}_{i\ 0\text{s}} \end{cases}\]

Thus \(n = c_j - c_i\) is a "binary multiple" of \(k\).

If \(k\) is negative, we repeat the above for \(-k\). If \(k = 0\), then \(n = 0\).

Example

If \(k = 4\) we consider \(c_1 = 1\), \(c_2 = 11\), \(c_3 = 111\), \(c_4 = 1111\) and realize none of these numbers is a multiple of \(4\).

Now we take the remainders:

\[ \begin{cases} 1 \equiv 1\ \text{mod}\ 4 \\ 11 \equiv 3\ \text{mod}\ 4 \\ 111 \equiv 3\ \text{mod}\ 4 \\ 1111 \equiv 3\ \text{mod}\ 4 \end{cases}\]

and see that, for example, \(c_3 \equiv c_2\ \text{mod}\ 4\), implying that \(c_3 - c_2 = 100 \equiv 0\ \text{mod}\ 4\).

Don't forget to subscribe to the newsletter to get bi-weekly problems sent straight to your inbox and to add your reaction below.

Thanks for reading this far! If you would like to show your appreciation for my work and would like to contribute to the development of this project, consider buying me a slice of pizza 🍕.