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

### 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/
```
Associated Topics:
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