Explanation for why new_remainder = (old_remainder * 10 + 1)%K
Edit\nI explain two methods below, but at the bottom there\'s also a TL;DR version if that\'s what suits you.\n\n\nThis post is just an explanation to why\nnew_
## Edit\nI explain two methods below, but at the bottom there\'s also a TL;DR version if that\'s what suits you.\n<hr>\n\nThis post is just an explanation to why\n`new_remainder = ((old_remainder * 10) + 1) % K`\nis the same as\n`new_remainder = ((old_number * 10) + 1) % K`\n\nI will write \n`((old_remainder * 10) + 1) % K`\nas \n` (old_remainder * 10 + 1) % K`\nfrom now as it\'s more succinct and means the same thing.\n\nSo this was pretty confusing for me, and I\'ve found atleast two easy ways to understand why this is true, there are other ways too but they were a bit beyond me and these two seem the simplest to grasp.\n<br>\n## The first method:\nThis is kind of straightforward, we just express numbers in a manner that makes the relation obvious.\n\nSo notice that every number `x` can be written as `aK + b`, \nwhere `a` is `x//K` and `b` is`x%K`.\n\nNow let\'s begin, `1 = aK+b`. So `1%K` is `b`.\n\nNext, we\'d want to find out 11%K.\nGenerally, you\'d do `next_remainder = (old_number * 10 + 1) % K`\n(Because old_number * 10 + 1 gives you the next number, 1\\*10 + 1 = 11, 11\\*10+1 = 111, so on..)\n\nAnd the natural way to do this would be `11 % K = (1 * 10 + 1) % K`\nAnd then for 111, we\'d do 111 % K = (11 * 10 + 1) % K\nFor 1111, we\'d do 1111 % K = (111 * 10 + 1) % K.\nHowever, this is bad because it\'ll lead to an overflow very soon.\n\nNow let\'s try to use the fact that `1 = aK + b`\n\nSo to find out 11%K :\n\n`11 % K = ((aK + b) * 10 + 1) % K`\n=> `11 % K = (10aK + 10b + 1) % K`\nbut `10aK` is a multiple of `K`, so we can just get rid of that\n(Example, 3 % 10, (10 + 3) % 10, (100 + 3) % 10, (1000 + 3) % 10 all evaluate to 3)\n=> `11 % K =  (10b + 1) % K`\n\nAnd voila, `b` was our remainder earlier (remember, `1%K` is `b` as we saw above).\n\nLet\'s do this for 111 just so that we\'re sure we get it.\n\nSo `11 = cK + d`. Notice `d` is the remainder, `11%K = d`\n`111 % K = ((cK + d) * 10 + 1) % K`\n=> `111 % K = (10cK + 10d+ 1) % K`\n=> `111 % K = (10d + 1) % K`\nand `d` was again the remainder we had when we divided 11 by K.\n\nSo from this, it\'s easy to observe that \n`new_remainder % K = (10 * old_remainder + 1) % K`\n\nHopefully that made sense but if it didn\'t, here\'s another way\n<br>\n## The second method:\n\nHere we make use of two modular arithmetic rules:\n1) ` (a + b) % m = (a%m + b%m) % m`\n2) `(a * b) % m = (a%m * b%m) % m`\n\nNow we have `new_number = old_number * 10 + 1`\nie `m = n * 10 + 1`\nthen `m % K = (n * 10 + 1) % K`\n\nNow let\'s focus on the right hand side, `(n * 10 + 1) % K`\n\nlet `n * 10` be denoted by `a`, and `1` be denoted by `b`,\nthen `(n * 10 + 1) % K` can be represented as `(a + b) % K`.\nAnd we saw above that ` (a + b) % K = (a%K + b%K) % K`.\n\nSo we have `(n * 10 + 1) % K` = `((n * 10)%K + 1%K)) % K`.\nNow` (n * 10)%K` can be simplified using rule 2 from above as\n`(n%K * 10%K) % K`\n\nSo finally, we get \n`(n*10 + 1)%K = ((n%K * 10%K)%K + 1%K)%K`\nwhich using rule 1(stated the other way around) can be simplified to \n`(n*10 + 1)%K = (n%K * 10%K + 1%K)%K`\nwhich further reduces to \n`(n*10 + 1)%K = (n%K * 10 + 1)%K`\n(because if we allow K to be 1, then it trivially reduces to (0 * 0 + 0)%1 which is 0, \nand if we allow K to be a multiple of 10, it simply boils down to (n%10 * 0 + 1)%10 which is 1)\n \nSo notice that `(n*10 + 1)%K = (n%K * 10 + 1)%K` which shows that you can simply replace `n` by `n%K`, \nthat is replace `old_number` by `old_number%K`, essentially leading to\n`new_remainder % K = (10 * old_remainder + 1) % K`\n\nI hope that helps.<hr>\n\n## Edit\nI came back to the problem a year later, today. I had forgotten everything and had to re-derive the solution, then noticed I had written this post a year ago(26 Novemeber 2020), haha.\nJust want to give a TL;DR version of the way I derived it today(30 December 2021), just the way I worked it out on paper without any words.. just in case that\'s something that helps it to click if the two methods above didn\'t.\n\nNeed to show that \n`[(n%k)*10 + 1] %k == (n*10 + 1) %k`\n\n```[(n%k)*10 + 1] %k```\n`-> [ { (n%k) * 10 }%k + 1%k] %k` \nbecause (a+b)%m = (a%m + b%m)%m\n\n`-> [ { (n%k%k) * 10%k }%k +1%k] %k`\nbecause (a\\*b)%m = (a%m * b%m)%m\n\n`-> [ {n%k * 10%k}%k + 1%k] %k`\nbecase a%m%m = a%m\n\n`-> [ {n*10}%k + 1%k] %k`\nbecause (a%m * b%m)%m = (a\\*b)%m\n\n`-> [n*10 + 1] %k`\nbecause 1%k is 1 for all k != 1. \n(And if k is 1, the whole thing evaluates to 0 anyway so it\'s fine)\n\nSo `[(n%k)*10 + 1] %k == (n*10 + 1) %k`
[]