Divisibility Proof

Date: 03/09/98 at 02:03:29
From: Itay Ackerman
Subject: algebra

Dear Dr. Math,

I have been wondering about this problem for a long time:

Is it true that for any positive integer (call it X), there is always 
another positive integer that is built from only 1's and 0's digits 
(like 100 or 10111, you know what I mean ... call it Y), such that Y 
is divisible by X (i.e., leaving no residue)?

If it's true, then what is the proof?

Thanks...
  
Itay Ackerman

Date: 03/09/98 at 16:38:59
From: Doctor Rob
Subject: Re: algebra

Yes, it's true. Furthermore, the number Y can have a single 
uninterrupted string of 1's followed by a single uninterrupted string 
of 0's.

Consider the remainders left when you take powers of 10 ...
 
    1, 10, 100, 1000, 10000, ...

... and divide them by X. There are only X possible remainders,

    0, 1, ..., X-1, 

so as soon as you get to 10^X, you will have encountered a repeat. 
Then say 10^(m+k) and 10^k leave the same remainder, where m > 0. That 
means that their difference 10^(m+k) - 10^k is exactly divisible by X. 
But

    10^(m+k) - 10^k = 10^k*(10^m-1),
                    = 999...999000...000,
                    = 9*111...111000...000,
                    = 9*N,

where there are m 1's and k 0's in N. X must divide into this number 
with remainder zero.

If X is not divisible by 3, we can immediately conclude that X must 
divide Y = N,

         = 10^k*(10^m-1)/9,
         = 111...111000...000

with remainder zero.

If X is divisible by 3 but not by 9, then X/3 divides N with remainder
zero. Then triple the number of 1's in N (from m to 3*m) to get

       Y = 10^k*(10^[3*m]-1)/9,
         = (10^[2*m]+10^m+1)*N.

Then X divides Y with remainder zero. The reason is that tripling the
number of 1's in N is gotten by multiplying N by

       10^[2*m]+10^m+1 = 1000...0001000...0001,

which is divisible by 3. Here, each of the two blocks of 0's has 
length m-1, and three 1's appear.

If X is divisible by 9, then X/9 divides N with remainder zero. Then
increase the number of 1's in N by a factor of 9 (from m to 9*m) to 
get

       Y = 10^k*(10^[9*m]-1)/9.

Then D divides Y with remainder zero. The reason is that increasing 
the number of 1's in N by a factor of 9 is gotten by multiplying N by

    10^[8*m]+10^[7*m]+10^[6*m]+10^[5*m]+10^[4*m]+10^[3*m]
            +10^[2*m]+10^m+1

 =  100...00100...00100...00100...00100...00100...00100...00100...001,

which is divisible by 9. Here, each of the eight blocks of 0's has 
length m-1, and nine 1's appear.

To see why these multipliers are divisible by 3 and 9, see the 
following URL:
  
    http://mathforum.org/dr.math/faq/faq.divisibility.html   

Example: X = 945.

  n   remainder of 10^n
  0           1
  1          10
  2         100
  3          55
  4         550
  5         775
  6         190
  7          10  REPEAT!

Now k = 1, m = 6, so 945 divides evenly into 9999990 (the quotient is 
10582). But 945 = 9*105, so we are sure that 945 divides

    Y = 10*(10^54-1)/9,
      = 1111111111111111111111111111111111111111111111111111110.

It does, and the quotient is

    1175778953556731334509112286890064667842445620223398.

Example: X = 328.

  n   remainder of 10^n
  0           1
  1          10
  2         100
  3          16
  4         160
  5         288
  6         256
  7         264
  8          16  REPEAT!

Now k = 3, m = 5, so 328 divides evenly into 99999000. Since 328 is 
not divisible by 3, 328 must also divide 11111000. It does, and the 
quotient is 33875.

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