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
< ? php function inv ( $ a , $ m ) { $ m0 = $ m ; $ x0 = 0 ; $ x1 = 1 ; if ( $ m == 1 ) return 0 ; while ( $ a > 1 ) { $ q = ( int ) ( $ a / $ m ) ; $ 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 ) { $ prod = 1 ; for ( $ i = 0 ; $ i < $ k ; $ i ++ ) $ prod *= $ num [ $ i ] ; $ result = 0 ; for ( $ i = 0 ; $ i < $ k ; $ i ++ ) { $ pp = ( int ) $ prod / $ num [ $ i ] ; $ result += $ rem [ $ i ] * inv ( $ pp , $ num [ $ i ] ) * $ pp ; } return $ result % $ prod ; } $ num = array ( 3 , 4 , 5 ) ; $ rem = array ( 2 , 3 , 1 ) ; $ k = sizeof ( $ num ) ; echo " x ▁ is ▁ " . findMinX ( $ num , $ rem , $ k ) ; ? >