Chinese remainder theorem

Implementación del Chinese remainder theorem (teorema chino del resto) [1] para Python. Para esta implementación es necesario que todos los módulos deban ser relativamente primos entre si, en caso contrario se necesitaría otro algoritmo para resolver las congruencias.

En la descripción original del problema en clase se pidió encontrar un $x$ tal que satisfaga las siguientes congruencias:

$4 \equiv x \mod 2$
$5 \equiv x \mod 3$
$6 \equiv x \mod 5$
$7 \equiv x \mod 7$
$8 \equiv x \mod 11$
$9 \equiv x \mod 13$

Si la anterior congruencia la expresamos como $a \equiv x \mod m$, entonces es posible expresar el problema de la siguiente manera: $x \equiv a \mod m$.

$x \equiv 4 \mod 2$
$x \equiv 5 \mod 3$
$x \equiv 6 \mod 5$
$x \equiv 7 \mod 7$
$x \equiv 8 \mod 11$
$x \equiv 9 \mod 13$

Se define $k = |A|$, $i = 1, ..., k$, $N = m_{1} * m_{2}* ... * m_{k}$, $A$ como el conjunto de los elementos $a$ y $M$ como el conjunto de los elementos $m$. $\forall m \in M$ se calcula $e_{i} =( m_{i} ^{-1} \mod N / m_{i}) * (N / m_{i})$. Ya que definimos todos los $e_{i}$, entonces $x$ se resuelve con la siguiente sumatoria: $x = \sum\limits_{i=1}^k a_{i}e_{i}$

References: [1] Chinese remainder theorem, n,d. http://en.wikipedia.org/wiki/Chinese_remainder_theorem (accessed September 18, 2014)