We have a number, say 23865, we want to see whether if 37 divides it. Then we do the following:-
- 37+1 = 38
- 23865 decimal -> (16)(20)1 base 38
- 16 + 20 + 1 = 37 divisible by 37
- hence 23865 is divisible by 37
My modulo arithmetic isn't that good, so I can't understand the proof on Wikipedia thoroughly. However, here's an easier proof:
23865
= 16 * 38^2 + 20 * 38^1 + 1
= 16 * (37+1)^2 + 20 * (37+1) + 1
= 16 * (37^2 + 2*37 + 1) + 20 * (37+1) + 1
= 16 * 37^2 + 52 * 37 + 16 + 20 + 1
= 17 * 37^2 + 15 * 37 + 16 + 20 + 1
Therefore, as long as 16 + 20 + 1 is divisible by 37, 23865 is divisible by 37. This can be generalized to any number.
abc are the digits that forms the dividend, d is a number, which is the divisor. e = d + 1.
abc
= X0 + X1 * e + X2 * e^2 + X3 * e^3 + ... + Xn * e^n (changing base)
= X0 + X1 * (d+1) + X2 * (d+1)^2 + X3 * (d+1)^3 + ... + Xn * (d+1)^n
By Binomial expansion, we know that (d+1)^n for n = 1,2,3,..., there must be a term which is a single 1, and all the other terms are the multiple of d, expanding
= X0 + X1 + X2 + X3 + ... + Xn + d * (complicated expression)
For the "special case" of dividing by 9,
abc
= c + b * 10 + a * 10^2
= c + b * (9+1) + a * (9+1)^2
= c + b + a + 9 * (b + 9a + 2a)
= 9 * (11a + b) + a + b + c
As long as a+b+c is divisible by 9, abc is divisible by 9.
Posts
