I had always appreciated the orderness of decimal number system. And that is why i always believed that even number 7 should have a divisibility rule. And with this belief, i had tried many times to find it. Well i had actually never tried seriously, i spent time thinking on it only when i had nothing else to do like when i was travelling on the train or on the bus or when i was sitting idle in my village. However I never succeeded in getting any closer to a solution.
But still i maintained my belief. And i was awarded for it when i was once looking into tutorial for programming in basic c++ in topcoder here. After going through the tutorial, i looked into the sample programming problems . That is when i found this problem statement and the wonderful theory about decimal number system. The theory stated that, for a ‘n’-digit number,x, to be divisble by a number ‘p’, there should exist a set of numbers a={a1,a2,a3…,an; a1=1, ai<=p}
y=(X1.a1)+(X2.a2)+(X3.a3)+….+(Xn.an),
is divisible by p where X1,X2,X3 are the n digits of the number x. For example, in case of 7, a1=1,a2=3,a3=2,a4=6,a5=4,a6=5…. Consider X=357, so X1=7,X2=5,X3=3. So
y = (X1.a1) +(X2.a2)+(X3.a3)
= (7.1)+(5.3)+(3.2)
= 7+15+6
= 28 which is divisble by 7.
Hence X=357 is divisible by 7.
This divisbility rule can be applied to any number and is very useful if to find whether a big number is divisible by a another big prime number. I still have not understood the rule completely like what is the reason behind it and whether there exist a proof for such rule. But,really, I was very happy to know this proof. It just requires that you know the number set, a.
Also finding the number set,a, is very easy. For Example, consider that we have to find the number set,a, for p=13. We know that,always, a1=1. Also for any n-digit number, p, ai=pow(10,i), where i<=n. Hence in this case, a1=1,a2=10. To find a3, consider a 3-digit number which is divisible by 13, like 117. So X1=7,X2=1,X3=1. Hence y=(1.a3)+(1.10)+(7.1). So now solve the above Equation by substituting values for a3 which are less than 13, such that y is divisible by 13. We find a unique solution, which is, 9. Following the same method, we find for p=13, a1=1,a2=10,a3=9,a4=12,a5=3.
