3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.