Base Conversion Divisibility Test

Since I'm dealing with divisibility these few days, I found this interesting divisibility test on Wikipedia.

We have a number, say 23865, we want to see whether if 37 divides it. Then we do the following:-

1. 37+1 = 38
2. 23865 decimal -> (16)(20)1 base 38
3. 16 + 20 + 1 = 37 divisible by 37
4. hence 23865 is divisible by 37

Proof.

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.

General rules of divisibility for all bases

I has discovered some interesting traits when I was studying prime numbers. It's a common rule that if the sum of digits of a decimal is divisible by 9, then the decimal is divisible by 9. I tried this rule for a number in base 3, and divided it by 2, interestingly enough, the sum of digits of this based-3 number appears to be divisible by 2. Thus I googled and found this useful stuff:-

Given a number in base B,

1. If the sum of digits is divisible by B-1 (or one of the factors of B-1), the number itself is divisible by B-1 (or that factor). For B = 10, this holds for 9 and 3.
   
   E.g. 145283769 / 9 = 16142641 >> 1+4+5+2+8+3+7+6+9 = 45 (4 + 5 = 9 too)
   
   
2. If the alternating sum of digits is divisible by B+1 (or by one of the factors of B+1), the number itself is divisible by B+1 (or that factor). For B = 10, this holds for 11.
   
   E.g. 170138210 / 11 = 15467110 >> 1-7+0-1+3-8+2-1+0 = -11
   
   
3. If K is a factor of B, then the number is divisible by K^n if and only if the last n digits of the number are divisible by K^n, where n is natural numbers (n = 1, 2, 3, ...). For B = 10, where factor(10) = 1, 2, 5, 10, this holds for 1 (trivial), 2, 4, 5, 8, 10, 25, .....
   
   

Adapted from http://www.derkeiler.com/Newsgroups/sci.crypt/2003-02/1039.html

ストレス

来週はいろいろなテストがある。。。

月曜日は日本語のオーラルテストある。
水曜日はEE3204の二つ目のテストある。
木曜日は朝EE2012の二つ目のテストあって、午後日本語のスキットある。

大変なあ。。。特に電子工学のテストはきっと難しいと思う。実は勉強はまだ終わらないけど。。。いくら大変でも、今日は勉強の気持ちが全然なかった。あまり勉強しなかった。本当に時間のむだだった。

今週森田先生がいるクラスが終わった。最後のTAとTCで写真を撮った。森田先生がいるクラスはいつも楽しくて、おもしろかった。私はいつまでもクラスのことを覚えている。甘くていい記憶だから、もしいつか思い出したら、絶対うれしくなると思う。

森田先生とクラスのみんな

明日勉強の気持ちはたぶんあると思う。時間が本当に足らないから、なくても勉強する。じゃ、ここまで。

T_T

後でCTWのオラルテストある。。。