## Chinese Remainder Theory (CRT)[Back] CRT allows us to determine n, giving a number of equations, such as n mod a = w, n mod b = y, n mod c = z, where we know [a,b,c] and [w,x,y] and where there are no common factors in the values a, b and c [gcd(a,b,c)=1]: |

## Quiz

Can you solve this [Try]:

x mod 3 = 2 x mod 5 = 3 x mod 11 = 2

## Examples

The following are some examples:

**x mod 3 = 2, x mod 5 = 2, x mod 7 = 2 ([3,5,7][2,3,2])?**. Try**x mod 3 = 2, x mod 7 = 4, x mod 13 = 11 ([3,7,13] [2,4,11])?**. Try**([3,7,17,14],[2,5,13,8])**. Try**([3,7,17,19,11,23],[2,5,13,8,11,20])**. Try

## Code

nval = [3,5,7] aval = [2,3,2] def chinese_remainder(n, a): sum = 0 prod = reduce(lambda a, b: a*b, n) for n_i, a_i in zip(n, a): p = prod / n_i sum += a_i * mul_inv(p, n_i) * p return sum % prod def mul_inv(a, b): b0 = b x0, x1 = 0, 1 if b == 1: return 1 while a > 1: try: q = a / b a, b = b, a%b x0, x1 = x1 - q * x0, x0 except: print "Bad N values (check no common factors in N vals)" return 0 if x1 < 0: x1 += b0 return x1 def gcd(L): return reduce(fractions.gcd, L) n = nval a = aval g = gcd(nval) print "GCD of N values: "+ str(g) if (g>1): print "Cannot compute - check your N values for a common factor" else: print "Result (x) is: "+str(chinese_remainder(n, a))+"\n" count=0 for str1 in nval: print "x mod "+str(str1)+"="+str(aval[count]) count=count+1