Apply the Euclidean algorithm , to find the modular inverse
while ( a > 1 ) { q = Math . floor ( a / m ) ; t = m ; m = a % m ; a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; }