An \(n\)-digit number \(2\ldots 2\) can be expressed as \(\frac{2}{9}(10^n-1)\). Therefore, the problem is equivalent to “given \(M\), find minimum \(n\geq 1\)s such that \(\frac{2}{9}(10^n-1) \equiv 0 \bmod M\).”

Generally,

• \(ax\equiv 0 \bmod M \Longleftrightarrow x\equiv 0 \bmod \frac{M}{\gcd(M,a)}\)
• \(\frac{x}{b}\) is an integer and \(\frac{x}{b} \equiv 0 \bmod M \Longleftrightarrow x\equiv 0\bmod bM\)

so this problem can be rephrased again to

“Find minimum \( 10^n\equiv 1 \bmod M'\) such that \(n\geq 1\)m where \(M'\) is \(\frac{9M}{2}\) if \(M\) is even, or \(9M\) if \(M\) is odd.”

This problem can be solved with one of the following two approaches.

Brute force through limited candidates of solutions

By Euler’s theorem, \(10^{\phi(M')}\equiv 1 \mod M'\), so minimum desired \(n\) is a divisor of \(\phi(M')\).

Why?

We prove it by contradiction. Assuming that \(n\) is not a divisor of \(\phi(M')\), then \(d=\gcd(n,\phi(M'))\) is less than \(n\). Moreover, there exists integers \(a,b\) such that \(an+b\phi(M')=d\), and \(10^d\equiv (10^n)^a (10^{\phi(M')})^b\equiv 1 \bmod M'\), so a solution \(d\) less than \(n\) exists, which is a contradiction.

Therefore, the answer can be found by iterating the divisors of \(\phi(M')\) and inspect it in the increasing order. Finding \(\phi(M')\) and enumerating the divisors of \(\phi(M')\) can be done in \(O(\sqrt{M'})\) time each, so the problem has been solved in a total of \(O(\sqrt{M'})\) time.

Sample code (C++)

Solve as a discrete logarithm problem

The problem “given \(a\), \(b\) and \(M\), find (minimum) \(x\) such that \(a^x=b \mod M\)” is called “Discrete Logarithm problem,” which can be solved in a total of \(O(\sqrt{M} \log M)\) time with an algorithm called Baby-step Giant-step. With a hashmap, it can be expected \(O(\sqrt{M})\).

For a general discrete logarithm problem, the process for cases where \(\gcd(a,M)>1\) is a little bit complex, but this time \(b=1\) so it can always be proved that the solution does not exist.

Sample code (C++)
Sample code (Python)