Tuesday, June 7, 2016

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 $b-1$, 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 = \sum c_i*b^i$ be a number is base $b$. Then the sum of the digits is $N=\sum c^i$. So $x - N = \sum c_i*(b^i - 1)$.



Each $b^i - 1 = (b-1)(b^{i-1}+b^{i-2} + .... + b + 1)$ so $x - N$ is a multiple of $b - 1$. So if $x$ is multiple of $b-1$ the sum of the digits is also a multiple of $b-1$.




Same thing if $x$ is a multiple of $n\mid b-1$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...