# crtInv.py
# Nikita Tiwari
# inverse modulo impl. of Chinese Remainder Theorem 
# https://www.geeksforgeeks.org/implementation-of-chinese-remainder-theorem-inverse-modulo-based-implementation/
'''
  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
from egcd import *


def modinv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  iv = x % m
  if iv < 0:
    iv += m
  return iv


def crt(mods, rems):
  n = len(mods)
  M = math.prod(mods)
  result = 0
  for i in range(0, n): 
    pp = M // mods[i] 
      # product of all other modulos except i-th
    result += rems[i] * modinv(pp, mods[i]) * pp 
  return result % M 


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