Apply the Euclidean algorithm , to find the modular inverse
while ( a > 1 ) : NEW_LINE INDENT q = a // m NEW_LINE t = m NEW_LINE m = a % m NEW_LINE a = t NEW_LINE t = x0 NEW_LINE x0 = x1 - q * x0 NEW_LINE x1 = t NEW_LINE DEDENT if ( x1 < 0 ) : NEW_LINE INDENT x1 += m0 NEW_LINE DEDENT return x1 NEW_LINE