Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$

Given $$L$$ and $$D$$ find $$X, \text { such that } X * 10^L + D \equiv 0 \mod M$$. Integer $$M$$ is given and it is the same for all calculations however we need to solve for $$X$$ for more different numbers. One important thing that we know is that $$\gcd(M, 10) = 1$$.

I rewrited the equation in this type: $$X * 10^L \equiv M - D \mod M$$. If $$M$$ was prime number we could just multiply $$M-D$$ by $$(10^L)^{M-2}$$. However $$M$$ might be arbitrary integer. How can we use the fact that $$\gcd(M, 10) = 1$$

• This is essentially a math question, perhaps more appropriate for Mathematics. – Yuval Filmus Jun 3 at 12:33

Since $$10$$ is relatively prime to $$M$$, it has an inverse modulo $$M$$, which can be found efficiently using the extended GCD algorithm. So you can simply calculate $$X = -10^{-L}D$$ (all computations modulo $$M$$).