Exercise 2.1.50* (Multiple of $n$ which contains only the digits 0 and 1)

Proof.

a)

First proof.

Assume first that $n$ is relatively prime with $10$ (i.e. $2\nmid n,5\nmid n$). Then $10^{\varphi (n)}\equiv 1(\mathit{mod}n)$, therefore

$$\underset{k=0}{\overset{n-1}{\sum }}10^{\mathit{k\varphi }(n)}\equiv n\equiv 0(modn).$$

So

$$n\mid m=\underset{k=0}{\overset{n-1}{\sum }}10^{\mathit{k\varphi }(n)}=\frac{10^{\mathit{n\varphi }(n)}-1}{10^{\varphi }(n)-1},$$

and

$$m=\underset{\varphi (n)}{\underset{⏟}{100\cdots 0}}\underset{\varphi (n)}{\underset{⏟}{100\cdots 0}}\cdots \underset{\varphi (n)}{\underset{⏟}{100\cdots 0}}\underset{1}{\underset{⏟}{1}}$$

contains only the digits $0$ and $1$ in its decimal expansion.

General case: Using the decomposition of $n$ in prime numbers, write $n=2^k{5}^l{n}^{\prime }$, where $n^{\prime }\wedge 10=1$. By the preceding argument, there is a multiple $m^{\prime }=\underset{k=0}{\overset{n^{\prime }-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}10^{\mathit{k\varphi }(n^{\prime })}$ of $n^{\prime }$ such that $m^{\prime }$ contains only the digits $0$ and $1$.

Then

$$n\mid 5^k{2}^{l}n=5^k{2}^l(2^k{5}^l{n}^{\prime })=10^{k+l}{n}^{\prime }\mid 10^{k+l}{m}^{\prime }.$$

Therefore $m=10^{k+l}{m}^{\prime }=10^{k+l}\underset{k=0}{\overset{n^{\prime }-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}10^{\mathit{k\varphi }(n^{\prime })}$ is such that $n\mid m$, and

$$m=\underset{\varphi (n)}{\underset{⏟}{100\cdots 0}}\underset{\varphi (n)}{\underset{⏟}{100\cdots 0}}\cdots \underset{\varphi (n)}{\underset{⏟}{100\cdots 0}}\underset{1}{\underset{⏟}{1}}\underset{k+l}{\underset{⏟}{00\cdots 0}}$$

contains only the digits $0$ and $1$.

Second proof (found on the net, math.stackexchange.com, author nonuser)

Let

$$a_k=\underset{k}{\underset{⏟}{111\cdots 11}}=\frac{10^k-1}{9}.$$

So, among $a_1,a_2,\dots ,a_{n+1}$ two must have the same remainder modulo $n$, say $a_i$ and $a_j$ and $i>j$. Thus

$$n\mid a_i-a_j=\frac{10^i-10^j}{9}=10^j\frac{10^{i-j}-1}{9}=\underset{i-j}{\underset{⏟}{111\cdots 11}}\underset{j}{\underset{⏟}{000\cdots 00}}.$$

b)

If $n\mid m$, where $m$ contains only the digits $0$ and $1$ in its decimal expansion, then $n\mid 2m,n\mid 3m,\dots ,n\mid 9m$, and $2m,3m,\dots ,9m$ contain only the digits $0$ and $2$, or $0$ and $3,\dots$, or $0$ and $9$.

c)

If the same hold for another pair of digits $i,j$, then $10\mid m$, where $m$ contains only the digits $i$ and $j$. Since the last digit of $m$ is $0$, $i=0$ or $j=0$.