Modulus of 9

We all learn from our school that to test the divisibility of a number by 9, we just need to add up their digits and see if the sum of digits is divisible by 9. It is actually beyond that, the remain of a number divided by 9 is equal to the remain of the sum of digits by 9, which we can prove here:

Assume the digits are n(1)n(2)n(3)….n(k) in decimal system,
The value of number= n(1)*10^(k-1)+n(2)*10^(k-2)+n(3)*10^(k-3)+….+n(k)
= n(1)*[10^(k-1)-1]+n(2)*[10^(k-2)-1]+n(3)*[10^(k-3)-1}+....+[n(1)+n(2)+n(3)+....+n(k)]

Given that 10^n-1 is also divisible by 9 when n>=1,
thus the remain of the number divided by 9 is equal to the remain of the sum [n(1)+n(2)+n(3)+....+n(k)] divided by 9
which means the remain of the sum of its digits in decimal system when divided by 9 is equal to the remainder of the value of the number when divided by 9.

To give an example,
12345678=1*10^7+2*10^6+3*10^5+4*10^4+5*10^3+6*10^2+7*10^1+8
=(1*10^7+2*10^6+3*10^5+4*10^4+5*10^3+6*10^2+7*10^1+8 )
=((1*9999999+1)+(2*999999+2)+(3*99999+3)+(4*9999+4)+(5*999+5)+(6*99+6)+(7*9+7)+8 )
=(1*9999999+2*999999+3*99999+4*9999+5*999+6*99+7*9)+(1+2+3+4+5+6+7+8 )
(1*9999999+2*999999+3*99999+4*9999+5*999+6*99+7*9) is divisible by 9
thus 12345678 modulus 9=(1++2+3+4+5+6+7+8 ) modulus 9=0
12345678 is divisible by 9

There is nothing special about that, however, if we consider a number in k-base system,
i.e. The value of 12345678(k)=(1*k^7+2*k^6+3*k^5+4*k^4+5*k^3+6*k^2+7*k^1+8 )

Consider that 12345678(k)=(1*k^7+2*k^6+3*k^5+4*k^4+5*k^3+6*k^2+7*k^1+8 )
=[1*(k^7-1)+2*(k^6-1)+3*(k^5-1)+4*(k^4-1)+5*(k^3-1)+6*(k^2-1)+7*(k^1-1)]+(1+2+3+4+5+6+7+8 )

By the remainder theorem,
[1*(k^7-1)+2*(k^6-1)+3*(k^5-1)+4*(k^4-1)+5*(k^3-1)+6*(k^2-1)+7*(k^1-1)] is divisible by k-1,
i.e. when k=1 is substitute into the polynomail, it give the value of zero.

Thus the modulus of 12345678 in k-base system when divided by k-1 is equal to the modulus of (1+2+3+4+5+6+7+8 ) when divided by k-1

Therefore we can generalize from this result that in 10-base system, we can test the divisibility of a number by 9 by testing its divisibility of its sum of digits. We could also test the divisibility of a number in 9 base-system by 8 by testing its divisibility of its sum of digits when divided by 8. We could also test the divisibility of a number in 8 base-system by 7 by testing its divisibility of its sum of digits when divided by 6;…. etc.