Associated Topics || Dr. Math Home || Search Dr. Math

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.

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search