Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/26/83; site ihuxl.UUCP
Path: utzoo!linus!decvax!harpo!gummo!whuxlb!pyuxll!eisx!npoiv!npois!hogpc!houxm!ihnp4!ihuxl!leo
From: leo@ihuxl.UUCP
Newsgroups: net.math
Subject: RE : proff of divide by 3
Message-ID: <511@ihuxl.UUCP>
Date: Fri, 26-Aug-83 12:45:09 EDT
Article-I.D.: ihuxl.511
Posted: Fri Aug 26 12:45:09 1983
Date-Received: Sun, 28-Aug-83 22:57:53 EDT
Organization: BTL Naperville, Il.
Lines: 31

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.