Chinese Remainder Theorem | Set 1 ( Introduction ) | 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 forevery pair is 1 ) ; As per the Chinise remainder theorem , this loop will always break . ; Check if remainder of x % num [ j ] is rem [ j ] or not ( for all j from 0 to k - 1 ) ; If all remainders matched , we found x ; Else try next number ; Driver Code
def findMinX ( num , rem , k ) : NEW_LINE INDENT while ( True ) : NEW_LINE INDENT j = 0 ; NEW_LINE while ( j < k ) : NEW_LINE INDENT if ( x % num [ j ] != rem [ j ] ) : NEW_LINE INDENT break ; NEW_LINE DEDENT j += 1 ; NEW_LINE DEDENT if ( j == k ) : NEW_LINE INDENT return x ; NEW_LINE DEDENT x += 1 ; NEW_LINE DEDENT 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