Chinese Remainder Theorem

x % num[0]    =  rem[0], 
x % num[1]    =  rem[1], 
.......................
x % num[k-1]  =  rem[k-1] 

source https://www.geeksforgeeks.org/

Method 1

Pengecekan nilai satu-persatu
Time Complexity : O(M)

def findMinX(num, rem, k):
    x = 1
    while(True):
        j = 0
        while(j < k):
            if (x % num[j] != rem[j]):
                break
            j += 1
        if (j == k):
            return x
        x += 1

num = [3, 4, 5]
rem = [2, 3, 1]
k = len(num)
print("x is", findMinX(num, rem, k))

Method 2

Recommended
Time Complexity : O(N*LogN)

x =  ( ∑ (rem[i]*pp[i]*inv[i]) ) % prod

num[] = {3, 4, 5}, rem[] = {2, 3, 1}
prod  = 60           // 3*4*5
pp[]  = {20, 15, 12} // 60/3, 60/4, 60/5
inv[] = {2,  3,  3}  // (20*2)%3 = 1, (15*3)%4 = 1,
                     // (12*3)%5 = 1

x = (rem[0]*pp[0]*inv[0] + rem[1]*pp[1]*inv[1] + rem[2]*pp[2]*inv[2]) % prod
  = (2*20*2 + 3*15*3 + 1*12*3) % 60
  = (80 + 135 + 36) % 60
  = 11

from Crypto.Util.number import inverse

def findMinX(num, rem, k) :
	prod = 1
	for i in range(0, k) :
		prod = prod * num[i]
	result = 0
	for i in range(0,k):
		pp = prod // num[i]
		result = result + rem[i] * inverse(pp, num[i]) * pp	
	return result % prod

num = [3, 4, 5]
rem = [2, 3, 1]
k = len(num)
print( "x is " , findMinX(num, rem, k))