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
< ? php function findMinX ( $ num , $ rem , $ k ) { while ( true ) { $ j ; for ( $ j = 0 ; $ j < $ k ; $ j ++ ) if ( $ x % $ num [ $ j ] != $ rem [ $ j ] ) break ; if ( $ j == $ k ) return $ x ; $ x ++ ; } return $ x ; } $ num = array ( 3 , 4 , 5 ) ; $ rem = array ( 2 , 3 , 1 ) ; $ k = sizeof ( $ num ) ; echo " x ▁ is ▁ " , findMinX ( $ num , $ rem , $ k ) ; ? >