leo@ihuxl.UUCP (08/26/83)
SORRY ABOUT PREVIOUS NOTE, I SOMEHOW LOST SOME LINES.
If you don't know what modular arithmetic is, read no further.
The proof of the divide by three rule is pretty simple.
I present it here as a more general proof.
given n,r where is is an integer and r is the radix
of the number system, r = 1 modulo n
lemma 1: any power of r = 1 modulo n
r*r*r...*r = 1*1*1...*1 mudulo n
= 1 modulo n
Consider number with k digits (abcdef...)
This number is a*(r**k)+b*(r**(k-1))+...
By the above lemma, it is then equivalent to
a+b+c... modulo n because any power of r is
equivalent to 1 modulo n.
Thus if r = 1 modulo n, then any number is
equivalent to the sum of its digits modulo n.
( A number is divisible by n if the number = 0 modulo n)
This proves both the rules for 9 and 3, since
10 = 1 modulo 3 and 10 = 1 modulo 9.
For the REAL hackers, it should be noted that
the divide by 3 rule also works in hex since
16 = 1 modulo 3.
Leo R.