{"id":180,"date":"2008-06-05T16:16:00","date_gmt":"2008-06-05T16:16:00","guid":{"rendered":"http:\/\/2paisasbyviggy.wordpress.com\/2008\/06\/05\/wonderful-divisibility-rule"},"modified":"2008-06-05T16:16:00","modified_gmt":"2008-06-05T16:16:00","slug":"wonderful-divisibility-rule","status":"publish","type":"post","link":"http:\/\/blog.viggy.in\/?p=180","title":{"rendered":"Wonderful Divisibility Rule"},"content":{"rendered":"<p>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.<br \/>  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 <a href=\"http:\/\/www.topcoder.com\/tc?module=Static&amp;d1=tutorials&amp;d2=primeNumbers\">here<\/a>. After going through the tutorial, i looked into the sample programming problems . That is when i found this <a href=\"http:\/\/www.topcoder.com\/stat?c=problem_statement&amp;pm=4481&amp;rd=6538\">problem statement<\/a> and the wonderful theory about decimal number system. The theory stated that, for a &#8216;n&#8217;-digit number,x, to be divisble by a number &#8216;p&#8217;, there should exist a set of numbers a={a1,a2,a3&#8230;,an; a1=1, ai&lt;=p}  <\/p>\n<p>                y=(X1.a1)+(X2.a2)+(X3.a3)+&#8230;.+(Xn.an),<\/p>\n<p>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&#8230;. Consider X=357, so X1=7,X2=5,X3=3. So<\/p>\n<p>           y    = (X1.a1) +(X2.a2)+(X3.a3)  <br \/>                 = (7.1)+(5.3)+(3.2)  <br \/>                 = 7+15+6  <br \/>                 = 28 which is divisble by 7.<br \/>       Hence X=357 is divisible by 7.<\/p>\n<p>  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.<br \/>  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&lt;=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. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_s2mail":"","footnotes":""},"categories":[1],"tags":[108],"class_list":["post-180","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-divisibility-rule"],"_links":{"self":[{"href":"http:\/\/blog.viggy.in\/index.php?rest_route=\/wp\/v2\/posts\/180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.viggy.in\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.viggy.in\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.viggy.in\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.viggy.in\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=180"}],"version-history":[{"count":0,"href":"http:\/\/blog.viggy.in\/index.php?rest_route=\/wp\/v2\/posts\/180\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.viggy.in\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.viggy.in\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=180"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.viggy.in\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}