# Prove that, for any natural number $k$ $\exists m \in M$ s.t i) $m$ has exactly $k$ $1$'s, an

Let $M$ be the set of natural numbers that can be written using only $0$ and $1$(in the decimal system). Prove that, for any natural number $k$ $\exists m \in M$ s.t

i) $m$ has exactly $k$ $1$'s, and ii) $m$ is divisible by $k$. (e.g, if $k=3$, then the number $101010 \in M$ is divisible by $3$)

Any hint or solution is welcome. If anyone have any hint in mind please give me step by step. Problem seems to be very interesting to me.

## 2 Answers

The sequence $10^n \pmod{k}$ yields an infinity of numbers in between $\{0,1,2,...,k-1\}$. By pigeonhole, there is an integer $j\in \{0,1,2,...,k-1\}$ such that for at least $k$ different integers $a_1,\ldots,a_k$, one has $10^{a_i} \equiv j \pmod{k}$. Set $m=\sum_{i=1}^k10^{a_i}\equiv jk \equiv 0 \pmod{k}$.

• That's a really nice and short proof! – rtybase Jan 28 '17 at 20:12

For numbers $k$ that are coprime to $10$, there will be some power of $10$ such that $10^s \equiv 1 \bmod k$. Then $\sum_{i=1}^k 10^{si} \equiv 0 \bmod k$. (Euler's theorem gives us that $s=\phi(k)$ is suitable).

For numbers $k$ that are not coprime to $10$, you will have $k=2^m5^nj$ where $j$ is coprime to $10$. Then find $s$ for $j$ as above and find a multiple of $s$ such that $rs>m,n$. Then $\sum_{i=r}^{j+r-1} 10^{si} \equiv 0 \bmod j$ and $\bmod 2^m5^n$ so also $\bmod k$, and then $\sum_{i=r}^{k+r-1} 10^{si} \equiv 0 \bmod k$

There are also far smaller numbers that will do the job, of course.

• (+1) but may I suggest a reference to Euler's theorem for the $\gcd(10,k)=1$ case? – rtybase Jan 28 '17 at 19:51
• @rtybase good idea, done. – Joffan Jan 28 '17 at 19:53