A simple python Chinese Reminder Theorem snippet to solve a system of congruences

crt.py

def extendedEuclid(a,b):
	#print 'extendedEuclid of ',a,b
	if b==0:
		return (a,1,0)

	tuplPrime = extendedEuclid(b,a % b)
	return [tuplPrime[0], tuplPrime[2], (tuplPrime[1] - (a//b)*tuplPrime[2])]



N = int(raw_input("No of congruences:"))
a = list()
n = list()
for i in xrange(0,N):
	a.append(int(raw_input("a_"+str(i+1)+": ")))
	n.append(int(raw_input("n_"+str(i+1)+": ")))

prod_n = reduce(lambda x,y: x*y, n)

print prod_n

p = list()

for i in xrange(0,N):
	p.append(prod_n//n[i])

print p
#find p-1 mod n1
t = list()
for i in xrange(0,N):
	print 'extendedEuclid of ',p[i],n[i]
	t.append((extendedEuclid(p[i],n[i])[1])%n[i])
A = 0
for i in xrange(0,N):
	A += a[i]*t[i]*p[i]
A = A%prod_n

print 'Solution: ',	A