A Story of an Algorithm

The problem is inspired by a comment of Ashwin Padaki in the discussion Divisble by 7? .

Let $c=\overline {a_p a_{p-1} ..........a_0}$ be any multiple of $n$ . As the algorithm involves only the last digit and the remaining number, let's reduce this whole number to $\overline{xy}$ where $y=a_0$ and $x= \overline{a_p a_{p-1}.........a_1} (mod n)$ .

The algorithm is multipying $y$ by $k$ and adding it to $x$ .

So, we will be left with the number

$a=x+k\cdot y$ and we are required to find the number of $n$ 's for which $a=0 (mod n)$ .

Now note that

$10\cdot a (mod n) = 10\cdot x+ 10k\cdot y (mod n)$

Now, $a=0 (mod n)$

$\Rightarrow 10a=0 (mod n)$

$\Rightarrow 10x+10ky=0 (mod n)$

$\Rightarrow 10x+ y- y+ 10ky=0 (mod n)$

$\Rightarrow y(10k-1)=0 (mod n)$ {because its given that- $10x+y=0 (mod n)$

$\Rightarrow 10k=1 (mod n)$

Note that a $k$ satisfying the above derived condition exists for all those $n$ and only for all those $n$ having there last digit as any of $1, 3, 7$ and $9$ .

There are 400 such numbers less than $1000$ .

Thus the answer is $\boxed {400}$ .