How to find Inverse Modulus of a number i.e (a%m) when m is not prime

Question

I searched the answer for this question, i got various useful links but when i implemented the idea, i am getting wrong answer.

This is what I understood :

If m is prime, then it is very simple. Inverse modulus of any number 'a' can be calculated as:inverse_mod(a) = (a^(m-2))%m

but when m is not prime, the we have to find the prime factors of m , i.e. m= (p1^a1)*(p2^a2)*....*(pk^ak). Here p1,p2,....,pk are the prime factors of m and a1,a2,....,ak are their respective powers.

then we have to calculate :

m1 = a%(p1^a1),

m2 = a%(p2^a2), 

.......

mk = a%(pk^ak)

then we have to combine all these remainders using Chinese Remainder Theorem (https://en.wikipedia.org/wiki/Chinese_remainder_theorem)

I implemented this idea for m=1000,000,000,but still i am getting Wrong Answer.

Here is my explanation for m=1000,000,000 which is not prime

m= (2^9)*(5^9) where 2 and 5 are m's prime factors.

let a is the number for which have to calculate inverse modulo m.

m1 = a%(2^9) = a^512

m2 = a%(5^9) = a^1953125

Our answer will be = m1*e1 + m2*e2

where e1= {  1 (mod 512)

             0 (mod 1953125)
          }
  and e2= {     1 (mod 1953125)

                0 (mod 512)
           } 

Now to calculate 'e1' and 'e2' , I used Extended Euclidean Algorithm. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

The Code is :

    void extend_euclid(lld a,lld b,lld& x,lld& y)
    {
          if(a%b==0)
          {
             x=0;
             y=1;
             return ;
          }
          extend_euclid(b,a%b,x,y);
          int tmp=x;
          x=y;
          y=tmp-(a/b)*y;
    }

Now e1= 1953125*y and e2=512*y;

So, Our final answer will be = m1*e1 + m2*e2 .

But after doing all this, I am getting wrong answer.

please explain and point out any mistakes which I have made while understanding Chinese Remainder Theorem .

Thank You Very Much.

Answer 1

The inverse of a modulo m only exists if a and m are coprime. If they are not coprime, nothing will help. For example: what is the inverse of 2 mod 4?

2*0 = 0 mod 4
2*1 = 2 mod 4
2*2 = 0 mod 4
2*3 = 2 mod 4

So no inverse.

This can indeed be computed by using the extended euclidean algorithm (although I'm not sure if you're doing it right), but the simplest way, in my opinion, is by using Euler's theorem:

a^phi(m) = 1 (mod m)
a*a^(phi(m) - 1) = 1 (mod m)
=> a^(phi(m) - 1) is the invers of a (mod m)

Where phi is the totient function:

phi(x) = x * (1 - 1/f1)(1 - 1/f2)...(1 - 1/fk)
where fi > 1 is a divisor of x (not necessarily a prime divisor)

phi(36) = 36(1 - 1/2)(1 - 1/3)(1 - 1/4)(1 - 1/6)(1 - 1/9)(1 - 1/12)(1 - 1/18)(1 - 1/36)

So it can be computed in O(sqrt n).

The exponentiation can then be computed using exponentiation by squaring.

If you want to read about how you can use the extended Euclidean algorithm to find the inverse faster, read this. I don't think the Chinese remainder theorem can help here.

Answer 2

I believe the following function will do what you want. Change from long to int if appropriate. It returns -1 if there is no inverse, otherwise returns a positive number in the range [0..m).

  public static long inverse(long a, long m) { // mult. inverse of a mod m
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    long tmp;
    while (nr != 0) {
      long q = r/nr;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) return -1; // no inverse
    if (t < 0) t += m;
    return t;
  }

I can't follow your algorithm to see exactly what is wrong with it, but I have a few general comments: Euler's totient function is rather slow to calculate in general, depending as it does on prime factorizations. The Chinese Remainder Theorem is useful in many contexts for combining results mod coprimes but it's not necessary here and again overcomplicates this particular issue because you end up having to factor your modulus, a very slow operation. And it's faster to implement GCD and modular inverse in a loop, rather than using recursion, though of course the two methods are equally effective.

Answer 3

If you're trying to compute a^(-1) mod p^k for p prime, first compute a^(-1) mod p. Given an x such that ax = 1 (mod p^(k-1)), you can "Hensel lift"---you're looking for the y between 0 and p-1 such that a(x + y p^(k-1)) = 1 (mod p^k). Doing some algebra, you find that you're looking for the y such that a y p^(k-1) = 1 - ax (mod p^k)---i.e. a y = (1 - ax)/p^(k-1) (mod p), where the division by p^(k-1) is exact. You can work this out using a modular inverse for a (mod p).

(Alternatively, simply notice that a^(p^(k-1)(p-1) - 1) = 1 (mod p^k). I mention Hensel lifting because it works in much greater generality.)