Friday, 18 October 2013

elementary number theory - Why do some divisibility rules work only in base 10?



Aside from the zero rule (a number ending with zero means it is divisible by the base number and its factors), why is it that other rules cannot apply in different bases?



In particular for 3 one can just sum all digits and see if it is divisible. What relation exists between 10 and 3 to have this property? Does this property exist in another base?



Also:
Are there divisibility rules for base 2?
Are there general divisibility formulae for all bases?



Answer



Two rules that work for any base b.



If n divides b1, then if the sum of the digits is a multiple of n then the number is a multiple of n. (That's why the 3 and 9 rule work).



If the sum of the even place digits is a multiple of b+1 more or less than the sum of the odd place digits then the number is a multiple of b+1.



Proof outline:



Let x=cibi be a number is base b. Then the sum of the digits is N=ci. So xN=ci(bi1).




Each bi1=(b1)(bi1+bi2+....+b+1) so xN is a multiple of b1. So if x is multiple of b1 the sum of the digits is also a multiple of b1.



Same thing if x is a multiple of nb1.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...