Why can iteratively searching from (N mod K)*10+1 in this problem find the length of the smallest repunit?

Question

Leetcode problem: Given a positive integer $K$, you need find the smallest positive integer $N$ such that $N$ is divisible by $K$, and $N$ only contains the digit $1$.

Return the length of $N$. If there is no such $N$, return $-1$.

Why does this following algorithm work here?

I'm asking here because although this was presented as a programming problem, it is at its core a math problem.

https://leetcode.com/problems/smallest-integer-divisible-by-k/

def smallestRepunitDivByK(K):

if K % 2 == 0 or K % 5 == 0:
    return -1
N = 1
cnt = 1
while N % K > 0:
    N = (N % K) * 10 + 1
    cnt += 1
return cnt

Answer 1

Partial answer: I put together the demonstration below to motivate the mathematics to follow. But I don't have time to pursue the rest right now, so I'm putting this much out because I think it is instructive. If someone wants to invert the logic to derive the algorithm, feel free. If not, I'll do that later.

---

Let's follow it for $K = 7$

$$\begin{array}{c|c|c|c} \text{Cnt} & N & N \% K & 10(N\% K) + 1\\\hline 1&1&1&11\\2&11&4&41\\3&41&6&61\\4&61&5&51\\5&51&2&21\\6&21&0&-\end{array}$$

So the claim is $111111$ is divisible by $7$. Let's try to prove that in steps. In each step, I'll subtract the largest multiple of $7$ less than the left two digits:

$$\begin{align}111111&- 700000 = 41111\\41111&-350000 = 6111\\6111&-56000 = 511\\511& - 490 = 21\\21& - 21 = 0\end{align}$$

What jumps out here is that the values of $N$ in the algorithm are the first two digits of the remainders in this validation.

Answer 2

Here's another way to think about it. Following Paul Sinclair, take $K=7$ as an example. Divide a row of 1s by 7, using long division. Keep going until the division comes out exact, that is, with a remainder of 0 -- this indicates that our row of 1s is a multiple of 7 as desired. At the start, we don't yet know how many 1s we'll need, so just obey the rule that whenever the division doesn't come out exact, the next digit you bring down is another 1.

7)111111
   7
  --
   41
   35
   --
    61
    56
    --
     51
     49
     --
      21
      21
      ==

Now that we see that we needed six 1s, we can see, looking back up, that 21, 511, 6111, 41111 and 111111 are multiples of 7, as Paul Sinclair showed.