Returns modulo inverse of a with respect to m using extended Euclid Algorithm . Refer below post for details : https : www . geeksforgeeks . org / multiplicative - inverse - under - modulo - m /
def inv ( a , m ) : NEW_LINE INDENT m0 = m NEW_LINE x0 = 0 NEW_LINE x1 = 1 NEW_LINE if ( m == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT