

This puzzle was posted at www.mathpuzzle.com:
This week's puzzle comes from Juha Saukkola, who helped me tremendously with my Leaper's page. 3x37=111, 4*25=100, 6*185=1110, 1999*5502751375687899=11000000000000110101. Is any integer n a perfect divisor of a larger integer N which consists entirely of ones and zeroes? If so, prove it ( Send Proof). Rick Heylen has calculated n = 1 to 2000. Does anyone see any patterns or revalations? 
This proof was devised by Erich Friedman:
Divide n into 1, 11, 111, 1111, 11111 .... and note the remainder. By the Pigeonhole Principle, eventually a remainder will repeat. Subtract.
The answer is yes  any positive integer n is a perfect divisor of some number N which consists entirely of ones and zeroes. The requirement that N > n is trivial since if n = N can only occur if n itself is a series of 1's and 0's ; take N = 10n.
Proof:
I've
tried
to
make
this
proof
understandable
to
people
who
aren't
into
number
theory.
The
decimal
expansion
of
1/n
is
a
pattern:
<leading
digits>
<decimal
point>
<0
or
more
nonrepeating
digits>
<r
=1ormore
digits,
infinitely
repeated>,
e.g.:
n  1/n  leading digits  decimal point  0
or
more
non repeating digits  r
digits repeated forever  r 
1  1.0000 ...  1  .  0  1  
22  0.0454545 ...  0  .  0  45  2 
42  0.02380950238095 ...  0  .  0  238095  6 
96  .0104166666 ...  0  .  01041  6  1 
[ Note: If you haven't seen that result before, the statement can be seen to be true by looking what happens in the process of expanding 1/n by long division of n into 1.00000 ; at each step in the long division, you have to carry over a remainder ; the remainder is < n, so there are only so many remainders you can carry over, so you eventually have to repeat yourself by carrying over some previously carriedover remainder  all further digits obtained in the expansion after that point will be repeats of digits previously expanded ]
Once we have the expansion ending in 'r' repeating digits, we can multiply by 10^r and subtract the original to get a terminating decimal, e.g.:
n  r
(#
of
digits repeated)  10^r  
1  1  10  10/n  10.0... 
1/n  1.0...  
9/n  9.0...  
22  2  100  100/n  4.54545... 
1/n  0.04545...  
99/n  4.50000...  
42  6  1000000  1000000 / n  23809.5238095238095... 
1 / n  0.0238095238095...  
999999 / n  23809.5000000000000...  
96  1  10  10 / n  0.1041666666... 
1 / n  0.0104166666...  
9 / n  0.0937500000... 
In each case we end up with:
999...999/n = <some number with k decimal places> (there are r 9's)
We can multiply both sides by 10^k to obtain:
999...999000...000 / n = <some number> (there are k zeros)
999...999000...000 = n * <some number>
Dividing both sides by 9 we get
111...111000...000
=
n
*
<some
number>
/
9
or
written
another
way:
(r
1's)
(k
0's)
If the left side has 'd' digits altogether (r 1's and k 0's so d=r+k), we can multiply both sides by the number:
1
(d
0's)
1
(d
0's)
....
1
(d
0's)
1
where
there
are
9
1's,
each
separated
by
d
0's.
This
number
is
divisible
by
9
(since
the
sum
of
its
digits
=
1+1+1+1+1+1+1+1+1
=
9)
We end up with:
(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)(r
1's)(k
0's)
= n
*
<some
number>
/
9
*
1
(d
0's)
1
(d
0's)
1
(d
0's)
....
=
n
*
<some
number>
/
9
*
<some
other
number>
*
9
=
n
*
<some
number>
*
<some
other
number>
I.e. n is an exact divisor of some number whose decimal representation consists only of 1's and 0's.
Examples:
n  
1  9 = 9 * 1 / 1  1 = 1  111111111 = 1 x 111111111 (ok, that's overkill) 
22  990 = 22 * 45  110 = 22 * 45 / 9  110110110110110110110110110 = 22 * 45 * somehorriblenumber 
42  9999990 = 42 * 238095  1111110 = 42 * 238095 / 9  111111011111101111110111111011111101111110111111011111101111110 = 42 * yuck 
96  900000 = 96 * 9375  100000 = 96 * 9375 / 9  100000100000100000100000100000100000100000100000100000 = 96 * yuck 


