Chinese Remainder Theorem | Set 2 ( Inverse Modulo based Implementation ) | 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 / ; Apply extended Euclid Algorithm ; q is quotient ; m is remainder now , process same as euclid 's algo ; Make x1 positive ; k is size of num [ ] and rem [ ] . Returns the smallest number x such that : x % num [ 0 ] = rem [ 0 ] , x % num [ 1 ] = rem [ 1 ] , ... ... ... ... ... ... x % num [ k - 2 ] = rem [ k - 1 ] Assumption : Numbers in num [ ] are pairwise coprime ( gcd for every pair is 1 ) ; Compute product of all numbers ; Initialize result ; Apply above formula ; Driver method
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 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 = x1 + m0 NEW_LINE DEDENT return x1 NEW_LINE DEDENT def findMinX ( num , rem , k ) : NEW_LINE INDENT prod = 1 NEW_LINE for i in range ( 0 , k ) : NEW_LINE INDENT prod = prod * num [ i ] NEW_LINE DEDENT result = 0 NEW_LINE for i in range ( 0 , k ) : NEW_LINE INDENT pp = prod // num [ i ] NEW_LINE result = result + rem [ i ] * inv ( pp , num [ i ] ) * pp NEW_LINE DEDENT return result % prod NEW_LINE DEDENT num = [ 3 , 4 , 5 ] NEW_LINE rem = [ 2 , 3 , 1 ] NEW_LINE k = len ( num ) NEW_LINE print ( " x ▁ is ▁ " , findMinX ( num , rem , k ) ) NEW_LINE