# crt.py
# brute force impl. of Chinise Remainder Theorem 
'''
  Return the smallest x such that: 
  x % mods[0] = rems[0], 
  x % mods[1] = rems[1], 
    :
  x % mods[k-2] = rems[k-1] 

  Assumption: Numbers in mods[] are pairwise coprime 
  (gcd for every pair is 1) 
'''

import math

def crt(mods, rems): 
  M = math.prod(mods)
  n = len(mods)
  x = 1 
  for x in range(M): # Check x against all mods and rems
    j = 0 
    while j < n: 
      if x % mods[j] != rems[j]: 
        break 
      j += 1 
    # if all remainders  matched, we found x 
    if j == n: 
      return x 

rems = [2, 3, 1] 
mods = [3, 4, 5] 
print("Rems=", rems, " Mods=", mods)
print("x =", crt(mods, rems));