Divisibility ProofDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/