Chinese Remainder Theorem | Set 2 ( Inverse Modulo based Implementation ) | A Java program to demonstrate working of Chinise remainder Theorem ; 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
import java . io . * ; class GFG { static int inv ( int a , int m ) { int m0 = m , t , q ; int x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = a / m ; t = m ; m = a % m ; a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; } static int findMinX ( int num [ ] , int rem [ ] , int k ) { int prod = 1 ; for ( int i = 0 ; i < k ; i ++ ) prod *= num [ i ] ; int result = 0 ; for ( int i = 0 ; i < k ; i ++ ) { int pp = prod / num [ i ] ; result += rem [ i ] * inv ( pp , num [ i ] ) * pp ; } return result % prod ; } public static void main ( String args [ ] ) { int num [ ] = { 3 , 4 , 5 } ; int rem [ ] = { 2 , 3 , 1 } ; int k = num . length ; System . out . println ( " x ▁ is ▁ " + findMinX ( num , rem , k ) ) ; } }