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

i searched answer question, got various useful links when implemented idea, getting wrong answer.

this understood :

if m prime, simple. inverse modulus of number 'a' can calculated as:inverse_mod(a) = (a^(m-2))%m

but when m not prime, have find prime factors of m , i.e. m= (p1^a1)*(p2^a2)*....*(pk^ak). here p1,p2,....,pk prime factors of m , a1,a2,....,ak respective powers.

then have calculate :

m1 = a%(p1^a1),  m2 = a%(p2^a2),  

.......

mk = a%(pk^ak) 

then have combine these remainders using chinese remainder theorem (https://en.wikipedia.org/wiki/chinese_remainder_theorem)

i implemented idea m=1000,000,000,but still getting wrong answer.

here explanation m=1000,000,000 not prime

m= (2^9)*(5^9) 2 , 5 m's prime factors.

let number have calculate inverse modulo m.

m1 = a%(2^9) = a^512  m2 = a%(5^9) = a^1953125  our answer = m1*e1 + m2*e2  e1= {  1 (mod 512)               0 (mod 1953125)           }   , e2= {     1 (mod 1953125)                  0 (mod 512)            }  

now calculate 'e1' , 'e2' , used extended euclidean algorithm. https://en.wikipedia.org/wiki/extended_euclidean_algorithm

the code :

    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;     }  e1= 1953125*y , e2=512*y;  so, our final answer = m1*e1 + m2*e2 . 

but after doing this, getting wrong answer.

please explain , point out mistakes have made while understanding chinese remainder theorem .

thank much.

the inverse of a modulo m exists if a , m coprime. if not coprime, nothing help. example: 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 computed using extended euclidean algorithm (although i'm not sure if you're doing right), simplest way, in opinion, using euler's theorem:

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

where phi totient function:

phi(x) = x * (1 - 1/f1)(1 - 1/f2)...(1 - 1/fk) fi > 1 divisor of x (not 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 can computed in o(sqrt n).

the exponentiation can computed using exponentiation squaring.

if want read how can use extended euclidean algorithm find inverse faster, read this. don't think chinese remainder theorem can here.