Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site ut-sally.UUCP
Path: utzoo!linus!decvax!harpo!seismo!hao!kpno!ut-sally!crandell
From: crandell@ut-sally.UUCP
Newsgroups: net.math
Subject: Re: interesting division by 3 property
Message-ID: <171@ut-sally.UUCP>
Date: Wed, 24-Aug-83 22:04:35 EDT
Article-I.D.: ut-sally.171
Posted: Wed Aug 24 22:04:35 1983
Date-Received: Sat, 27-Aug-83 18:19:55 EDT
References: <657@ihuxf.UUCP>
Organization: U. Texas CS Dept., Austin, Texas
Lines: 21


     The "divisable by 3" rule is also a "divisable by 9" rule (i.e.,
an integer is divisable by 9 iff the sum of its digits is).  The most
general theorem I've found is (this is probably in a reference somewhere,
but it's too simple to waste time looking up): given a positive integer
N expressed in radix r, the modulo-(r-1) sum of the digits in the
representation of N is equal to the remainder of division of N by (r-1).
Stated another way, N and the sum of its digits are congruent modulo-(r-1),
assuming representation in radix r.
     I thought of this theorem a couple years ago when searching for
a cheap (hardware) algorithm for converting hex to decimal.  If r = 16,
then end-around-carry addition of the digits yields the remainder from
division by 15, which is interesting, because 15 is a multiple of 5.
Since 16 is even, it's very easy to determine if a hexadecimal integer
is even (i.e., to obtain the remainder from division by 2).  Of course,
2 * 5 = 10, so a very simple function of these two remainders yields the
units digit in the decimal representation.  Unfortunately, I needed the
quotient to go any further, and I couldn't think of a neat method that
would give me that without dividing or multiplying.

				  Jim (ihnp4!ut-sally!crandell)