Finding Integer Pairs Whose Product Consists Only of 1's and 0's

Date: 10/06/2004 at 20:21:23
From: Kris
Subject: How can the product of 2 numbers contain only ones and zeros

Given the base-10 representation of any integer a, does there exist a 
non-zero integer b such that the base-10 representation of the product 
ab contains only ones and zeros?

One example (most obvious) is a = 5 and b = 2 ... ab = 5 x 2 = 10. 
Another is a = 17 and b = 653 ... ab = 17 x 653 = 11101.

How can you come up with two numbers such that the product only 
contains ones and zeros?  I can guess and figure out a few, but there
must be an easier way, or some sort of pattern.

Date: 10/07/2004 at 03:52:29
From: Doctor Jacques
Subject: Re: How can the product of 2 numbers contain only ones and zeros

Hi Kris,

Let us call a number "good" if it statisfies the required property, 
i.e., if there is a number b such that the product a*b contains only 
the digits 0 and 1 when represented in base 10.  We want to show that 
all numbers are "good".

We will first examine a few easy cases.

* 0 and 1 are good

This is obvious.

* If a is good, then 2a is good.

Indeed, if a*b = N, then (2a)(5b) = 10*N, and this is just N with an 
additional 0 on the right--if N contains only 0's and 1's, then so 
does 10*N.

* If a is good, then 5a is good.

The proof is exactly the same--simply interchange 2 and 5.

* If a is good, then 3a is good.

This is a little trickier.  Assume that we have:

  a*b = N

where N consists only of 0's and 1's.  Assume that N contains k 
digits.  Consider the number:

  c = 1O^(2k) + 10^k + 1

This number contains only three 1's (at positions 0, k, and 2k).  By 
the divisibility rules for 3, c is a multiple of 3, and we can write 
c = 3d.  We have therefore

  a*(b*c) = a*(3*b*d) = (3a)*(b*d)= c*N

Now, c*N is simply N repeated 3 times.  If N only contains 1's and 
0's, then so does c*N, and this shows that (3a) is "good".

The conclusion of all this is that we may assume that a >= 2 and a is 
not divisible by 2, 3, or 5.

If a is not divisible by 2 or 5, the decimal expansion of 1/a is 
purely periodic, and, if k is the length of the period, then 
(10^k - 1) is divisible by a; in fact, k is the smallest integer such 
that:

  10^k = 1   (mod a)
 
(If you are not famliliar with this, see, for example:

  Shortcut: Repeating Decimals to Equivalent Fractions
    http://mathforum.org/library/drmath/view/58176.html 

or many other pages you can find in our archive:

  Search Dr. Math
    http://mathforum.org/library/drmath/mathgrepform.html 

by searching for "repeating decimal".)

Of course, any number of the form 10^k - 1 consists only of 9's, and 
is divisible by 9.  We can write:

  10^k - 1 = 9*N

where N is a sequence of 1's.

As a divides 10^k - 1, there is a "b" such that:

  a*b = 10^k - 1 = 9*N

As this number is a multiple of 9, and we assumed that a was not a 
multiple of 3, b must be a multiple of 9, say b = 9c.  We have then:

  a*(9c) = 9N
  a*c = N

and N contains only 1's - "a" is a good number.

To see how it works on an example, let us consider a = 246 = 2*3*41.

We begin by removing all factors 2, 3, and 5, leaving 41.  The decimal 
expansion of 1/41 is;

  1/41 = 0.02439...

and the period has length 5, which shows that 41 divides 10^5 - 1. 
Indeed, we have:

  10^5 - 1 = 99999 = 41*2439 = 41*9*271

and, dividing by 9, we have:

  41*271 = 11111

Note that the number on the right is not a multiple of 3, but a = 246 
is a multiple of 3.  We use the technique explained above, i.e., we 
repeat the number 3 times:

  41*2710027100271 = 111111111111111

(Note that we had to extend the number 271 to 5 digits to match the 
length of the number on the right.)

The factor of 41 is a multiple of 3 (by construction), in fact, we 
have:

  2710027100271 = 3 * 903342366757

and this allows us to write:

  (3*41)*903342366757 = 111111111111111

This already shows that 41*3 = 123 is a good number.  To get to 246, 
we must introduce a factor of 2, and we do this by multiplying by 2
and 5 on both sides:

  (2*3*41)*(5*903342366757) = 1111111111111110
  246 * 4516711833785 = 1111111111111110

which shows that 246 is a good number.

Note that, although this technique proves that all numbers are good, 
and does, in fact, give an explicit method for finding a suitable 
factor "b", it will not, in general, give the smallest possible such 
factor.  In fact, the factor produced by this method is such that all 
the 1's in the product are consecutive, with all the 0's at the end.

For example, we have:

  337*3 = 1011

but, if we start with the number 337, and apply the previous method, 
we will get a very large factor, since the decimal expansion of 337 
has period length 336; the product on the right will consist of 336 
"1" digits.

I do not know any method that could allow you to find the smallest 
possible factor "b" (except, of course, by listing all the multiples 
of a...).

Note also that a similar argument is valid for any base; in that case, 
you have to replace the special factors 2, 3, and 5 by the prime 
factors of b and b-1, if b is the base.

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/