Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

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

share|improve this question

1 Answer

up vote 5 down vote

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

share|improve this answer
the digits in $m_n$ are only 3 or consist on 3 and 0 ? – chihiroasleaf Feb 6 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 at 7:37
@chihiroasleaf Said differently, consider the set {3, 33, 333, 3333, ...., (3 repeated k times)}. Now, any number when divided by k can give remainders between 0 and k - 1. Now, divide each number in the given set with k and observer the remainders that they give. What happens if one of the remainders is zero and what happens if none of the remainders are zero? – TenaliRaman Feb 6 at 7:46
is this correct? I make $k+1$ $m_n$ they are $m_1$ = 3 $m_2$ = 33 . – chihiroasleaf Feb 6 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 at 7:48
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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