number theory of multiples of 3

圖片參考：http://i187.photobucket.com/albums/x22/cshung/7007102804453.jpg
　　　　　

首先，以十進制來說，一個數x皆可以以下面的形式寫出：

x = an (10)n + an - 1 (10)n - 1 + …… + a1 (10)1 + a0

其中n是整數

重寫成這樣：

x = an (9 + 1)n + an - 1 (9 + 1)n - 1 + ……

　　+ a1 (9 + 1)1 + a0

然後再用二項式定理拆出後：

x = an (9n + nC1 9n - 1 + …… + nCn - 1 9 + 1)

　　+ an - 1 (9n - 1 + n - 1C1 9n - 2 + ……

　　+ n - 1Cn - 2 9 + 1) + …… + a1 (9 + 1) + a0

　= an (9Kn + 1) + an - 1 (9Kn - 1 + 1) + ……

　　+ a1 (9 + 1) + a0

　= 3(3an Kn + 3an - 1 Kn - 1 + …… + 3a1)

　　+ (an + an - 1 + …… + a1 + a0)

由此可見，前半部分必可被3整除，所以只要後半部分

an + an - 1 + …… + a1 + a0

也能被3整除，x便為3的倍數。

而此表達式：an + an - 1 + …… + a1 + a0，

事實上就是x的所有數位的數的總和，若此為3的倍數，則x便是3的倍數。