Peter L. Peres wrote: > > The theorem that 'a number is divisible by 3 if the sum of its > > digits is divisible by 3' is not valid in base 2 and afaik in no > > other base than 10. and Bob Ammerman replied: > I believe it is valid in any base 3N+1, when N is a positive > integer. Correct. To generalize it further, the rule is: A non-zero number in base ax+1, where a and x are integers, is divisible by x if the sum of its digits is divisible by x. Even the weird cases like base 1 (if you define "divisible by 0" as true for 0) and base 2 work. This, by the way, makes it easy to test for divisibility by 7 (for which no base-10 rule exists) in base 8: Test decimal 84 for divisibility by 7: 84 decimal = 124 octal 1 + 2 + 4 = 7 7 is divisible by 7, therefore 124 octal is divisible by 7, therefore 84 decimal is divisible by 7. The base-10 test for divisibility by 11 can also be generalized for other bases: A non-zero number in base ax-1 is divisible by x if the sum of its even-numbered digits differs from the sum of its odd-numbered digits by a number diviible by x or equal to 0. An example in base 10: Test decimal 1353 for divisibility by 11: 1 + 5 = 6, 3 + 3 = 6 6 - 6 = 0 Therefore, 1353 is divisible by 11. An example in base 21, (21 = ax-1 where a = 2 and x = 11): In base 21, test 1353 decimal for divisibility by 11: 1353 decimal = 319 base 21 3 + 9 = C base 21 (12 decimal), 1 = 1 C base 21 - 1 = B base 21 (11 decimal) B base 21 is divisible by 11 decimal, so 319 base 21 is divisible by 11 decimal. Base 21 is sorta useless, but this test IS useful for testing divisibility by 3 in base 2: 201 decimal = 11001001 binary 1 + 0 + 1 + 0 = 10, 1 + 0 + 0 + 1 = 10 10 - 10 = 0 Therefore, 11001001 binary is divisible by 3. -Andy === Andrew Warren - fastfwd@ix.netcom.com === Fast Forward Engineering - San Diego, CA === http://www.geocities.com/SiliconValley/2499 -- http://www.piclist.com hint: To leave the PICList mailto:piclist-unsubscribe-request@mitvma.mit.edu