x ≡ 2 mod 5 x ≡ 3 mod 11 x ≡ 5 mod 17 Form: x = a % m m0 = 5 * 11 * 17 z1 = m0 / 5 z2 = m0 / 11 z3 = m0 / 17 y1 = modinv(z1, m1) y2 = modinv(z2, m2) y3 = modinv(z3, m3) w1 = (y1 * z1) % m0 w2 = (y2 * z2) % m0 w3 = (y3 * z3) % m0 x = a1 * w1 + a2 * w2 + a3 * w3 https://www.geeksforgeeks.org/using-chinese-remainder-theorem-combine-modular-equations/ # function implementing Chinese remainder theorem # list m contains all the modulii # list x contains the remainders of the equations def crt(m, x): # We run this loop while the list of # remainders has length greater than 1 while True: # temp1 will contain the new value # of A. which is calculated according # to the equation m1' * m1 * x0 + m0' # * m0 * x1 temp1 = modinv(m[1],m[0]) * x[0] * m[1] + modinv(m[0],m[1]) * x[1] * m[0] # temp2 contains the value of the modulus # in the new equation, which will be the # product of the modulii of the two # equations that we are combining temp2 = m[0] * m[1] # we then remove the first two elements # from the list of remainders, and replace # it with the remainder value, which will # be temp1 % temp2 x.remove(x[0]) x.remove(x[0]) x = [temp1 % temp2] + x # we then remove the first two values from # the list of modulii as we no longer require # them and simply replace them with the new # modulii that we calculated m.remove(m[0]) m.remove(m[0]) m = [temp2] + m # once the list has only one element left, # we can break as it will only contain # the value of our final remainder if len(x) == 1: break # returns the remainder of the final equation return x[0] # driver segment m = [5, 11, 17] x = [2, 3, 5] print(crt(m, x))