# Prove by using Pigeon Hole Principle

Let $k \in \mathbb Z^+$. Prove that there exists a positive integer $n$ such that $k|n$ and the only digits in $n$ are 0's and 3's

-

HINT: Let $$m_n=\underbrace{3\dots3}_{n\text{ threes}}\;.$$ Let $r_n$ be the remainder when you divide $m_n$ by $k$. Use the fact that if $r_n=r_\ell$ with $n>\ell$, then $k\mid m_n-m_\ell$.
the digits in $m_n$ are only 3 or consist on 3 and 0 ? –  chihiroasleaf Feb 6 '13 at 7:35
@chihiroasleaf: The digits of $m_n$ are all $3$’s. Note that you’re only required to find a number that has no digit other than $0$ and $3$: it need not have both $0$ and $3$. However, in many cases the number that you get from this hint won’t be one of the $m_n$’s, and it will have both $3$’s and $0$’s. –  Brian M. Scott Feb 6 '13 at 7:37
is this correct? I make $k+1$ $m_n$ they are $m_1$ = 3 $m_2$ = 33 . –  chihiroasleaf Feb 6 '13 at 7:46
@chihiroasleaf: Yes, two of $m_1,\dots,m_{k+1}$ must have the same remainder. Now what can you do with them to get a multiple of $k$ that has only $3$’s and maybe some $0$’s? –  Brian M. Scott Feb 6 '13 at 7:48