Take the 2-minute tour ×
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.

I recently solved a problem, which says that,

a positive integer can be multiplied with another integer resulting in a positive integer that is composed only of one and zero as digits.

How can I prove that this is true(currently I assume that it is). Also, is it possible to establish an upper bound on the length(number of digits) of the number generated?

Thanks !

share|improve this question
add comment

2 Answers 2

up vote 33 down vote accepted

Not only is it possible to find a multiple of $n$ whose decimal expansion consists solely of $0$s and $1$s, it is possible to arrange for all the $1$s to come before all the $0$s.

Suppose first that $n$ is coprime to $10$. Then by Fermat–Euler, $10^{\varphi (9n)} \equiv 1 \pmod{9n}$. Thus $(10^{\varphi (9n)} -1)/9 \equiv 0 \pmod{n}$, and so there is a multiple of $n$ which consists solely of $1$s, namely $(10^{\varphi (9n)} -1)/9$.

Now consider the opposite case that $n=2^a 5^b$ for some natural $a, b$. Then some multiple of $n$ is a power of $10$: either $2^{b-a}n$ or $5^{a-b}n$, depending on whether $a$ or $b$ is greater.

Thus for general $n$, we can express $n$ as $2^a 5^b m$, where $m$ is coprime to $10$. Then we can find a multiple of $m$ which is a string of $1$s and a multiple of $2^a 5^b$ which is a power of $10$, and hence a multiple of $n$ which is a string of $1$s followed by a string of $0$s. Specifically, there are $\varphi (9m)$ $1$s and $\max(a,b)$ $0$s, so $\varphi (9m)+\max(a,b)$ gives an upper bound on the number of digits needed.

share|improve this answer
    
Awesome! Thank you for explaining in such detail :). –  Priyank Bhatnagar Nov 20 '11 at 13:53
add comment

Here is an alternate solution, which is based on the Pigeon principle:

List all the numbers 1, 11, 111, ... , 111...1 where the last one contains $n+1$ ones.

Look now at their remainders when divided by $n$. By the pigeon principle, two of them have the same remainder. But then their difference is of the form $1111..100000..0$ and is divisible by $n$..

share|improve this answer
1  
This solution is a lot simpler. It needs more votes :) –  wircho Nov 20 '11 at 16:50
6  
True, but there is always a price to pay for simplicity...The other solution yields extra information: you can actually find how many 1's and 0's you need ;) –  N. S. Nov 20 '11 at 17:03
1  
Very intuitive! :) Thanks for sharing this :) –  Priyank Bhatnagar Nov 20 '11 at 18:05
20  
+1 though that'd be the Pigeon hole principle. –  Mark Hurd Nov 21 '11 at 6:08
add comment

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.