How to look for minimum n so that 10 ^ n ≡ 1 mod (9x) for a given x

Question

For this xI need to calculate a minimum nthat equals true for the formula10^n ≡ 1 (mod 9x)

My algorithm is simple. For i = 1 to infI loop it until I get the result. There is always a result if gcd(10, x) = 1. Meanwhile, if I do not get the result, I increase iby 1.

This is very slow for large numbers or numbers with factorization of large values, so I ask if there is another way to calculate it faster. I tried with threads, getting each thread next 10^ifor calculation. Performance is a little better, but the big touches don't end there.

Answer 1

I just tried the example, it works in less than one second:

public class Main {

    public static void main(String[] args) {
        int n = 1;
        int x =  954661;
        int v = 10;
        while (v != 1) {
            n++;
            v = (v * 10) % (9*x);
        }
        System.out.println(n);
    }
}

For large values, xvariables must be of type long.

Answer 2

You can use Fermat Little Theor .

Assuming yours xis relatively simple with 10, the following holds true:

10 ^ φ(9x) ≡ 1 (mod 9x)

Here φ is the Euler totalizer function . Thus, you can easily calculate at least one n(not necessarily the smallest) for which your equation is satisfied. To find the smallest one n, just go to the list of dividers n.

---

Example: x = 89 (a prime is just for simplicity).

9x = 801
φ(9x) = 6 * (89 - 1) = 528 (easy to calculate for a prime number)

List of 528 dividers:

1
2
3
4
6
8
11
12
16
22
24
33
44
48
66
88
132
176
264
528

, , 44:

10 ^ 44 ≡ 1 (mod 801)

Answer 3

As you pointed out, you are actually trying to get a module with 1, which is equal 1mod(9x). This will always give you 1.

And you do not need to accurately calculate this part, which can reduce your calculation.

On the other hand, for 10^n = 1it will always be 0. So, you can specify exactly what you are trying to do