parnass@ihuxf.UUCP (08/23/83)
One of my favorite arithmetic shortcuts is:
o+ any integer N is divisible by 3 if the sum of N's
digits is divisible by 3.
I sometimes use this property recursively to avoid
performing long division.
--
============================================================================
Robert S. Parnass, Bell Laboratories ihnp4!ihuxf!parnass (312)979-5760 ecn-ec:ecn-pc:ecn-ed:vu@pur-ee.UUCP (08/24/83)
This is the complete bag of tricks in divisibility I learned in 6th grade:
+ A number N is divisible by 3 or 9 if and only if the sum of the digits
of N is divisible by 3 or 9 respectively
+ An even number divisible by 3 is divisible by 6 (trivial)
+ A number N is divisible by 11 if the sum of its 1st,3rd,5th,... digits is
equal to the sum of its 2nd,4th,6th,... digits. This demands a proof:
(not quite, but good enough to be generalize)
abcdefg
x 11
-------
abcdefg
abcdefg
--------
(bunch of numbers)
add "or differ by a multiple of 11" after "equal to"
+ A number N is divisible by 4 or 8 if its last 2 or 3 digits resp. form
a number divisible by 4 or 8 resp. (Since 4|100 and 8|1000 where | means
divides)
+ A number is divisible by 5 or 10 if its last digit is 5 or 0 (for 5) or
0 (for 10)
Combining them all together, you get a lot of composite number. I have not
yet found anything about divisibility for primes other than 2, 3, 5, 11
In an article in Math. Monthly, one of its editor told the story about a
suggestion for divibility for 7:
Write N in base 8 (by the way, we have been talking only about base 10)
then add the digits of N (base 8). If the sum (in base 8) is divisible by 7
then N is divisible by 7. Example: 21 = 25(base 8) whose sum is 7(base 8).
One wonders who is going to do the base conversion !!!
In fact, in base n, a number N is divisible by n-1 if and only if
the sum of N's digit is divisible by n-1 (in base n).
Hao-Nhien Vu (pur-ee!vu, changing into pur-ee!norris)crandell@ut-sally.UUCP (08/25/83)
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)dje@5941ux.UUCP (08/25/83)
pur-ee!vu stated that an integer is divisible by 11 if the sum of the digits in odd positions and the sum of the digits in even positions are equal (e.g. 781, 2585). This is not the complete test: consider the number 814, which is divisible by 11. The odd-digits sum is 12 and the even-digits sum is 1. The correct rule is that the two digit-sums must differ by a multiple of 11.
dje@5941ux.UUCP (09/23/83)
Some time ago, I submitted an article on testing for divisibility by 7.
The rule is: 10t+u is divisible by 7 if and only if t-2u is divisible by 7.
Examples and proof available on request.
Dave Ellis / Bell Labs, Piscataway NJ
...!{hocda,ihnp4}!houxm!houxf!5941ux!dje
...!floyd!vax135!ariel!houti!hogpc!houxm!houxf!5941ux!dje