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 forevery pair is 1 ) ; Compute product of all numbers ; Initialize result ; Apply above formula ; Driver Code
function inv ( a , m ) { let m0 = m ; let x0 = 0 ; let x1 = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { let q = parseInt ( a / m ) ; let t = m ; m = a % m ; a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; } function findMinX ( num , rem , k ) { let prod = 1 ; for ( let i = 0 ; i < k ; i ++ ) prod *= num [ i ] ; let result = 0 ; for ( let i = 0 ; i < k ; i ++ ) { pp = parseInt ( prod / num [ i ] ) ; result += rem [ i ] * inv ( pp , num [ i ] ) * pp ; } return result % prod ; } let num = new Array ( 3 , 4 , 5 ) ; let rem = new Array ( 2 , 3 , 1 ) ; let k = num . length ; document . write ( " " + findMinX ( num , rem , k ) ) ;