Chinese Remainder Theorem
Given a list of congruences for \(x\), where
[x \space \cong a_{1} \space mod \space n_{1},]
[x \space \cong a_{2} \space mod \space n_{2},]
[.]
[.]
[x \space \cong a_{k-1} \space mod \space n_{k-1},]
[x \space \cong \space a_{k} \space mod \space n_{k}]
and \(n_{1}, \space .., \space n_{k}\) are coprime positive integers. Then \(x\) has a solution, and the solution is unique modulo \(N = n_{1}n_{2}..n_{k}.\)
Explanation
Consider the problem,
\(x \space \cong 3 \space mod \space 5,\)
\(x \space \cong 5 \space mod \space 7,\)
\(x \space \cong 7 \space mod \space 11,\)
and solve for x.
Let us solve try to solve the problem with the help of primary number theory tools. Now imagine a 3d plane (x, y, z) whose axis boundaries are 5, 7 and 11 respectively. Now, we know that there exists only one such coordinate or number whose value or remainder is (3, 5, 7). We can simplify the problem by finding a number \(x_{1}\) that yields remainder (1, 0, 0), \(x_{2}\) with (0, 1, 0) and \(x_{3}\) having (0, 0, 1).
To be more precise, find \(x_{1}\) that has,
\(x_{1} \cong 1 \space mod \space 5,\)
\(x_{1} \cong 0 \space mod \space 7,\)
\(x_{1} \cong 0 \space mod \space 11.\)
It’s clear that \(x_{1}\) is a multiple of 7 * 11 and we need to find the inverse of (7*11) with respect to the modulo 3.
The value of \(x_{1} = \space (7*11) * (7*11)^{-1} \space \cong \space 1 \space mod \space 5\).
Similarly solve for \(x_{2} \space and \space x_{3}\). Now we have numbers \(x_{1}, x_{2} \space and \space x_{3}\) that has points (1, 0, 0), (0, 1, 0) and (0, 0, 1) respectively.
By multiplying the corresponding \(a_{i} * x_{i}\), we get points (3, 0, 0), (0, 5, 0) and (0, 0, 7). And let \(X_{1}, X_{2} \space and \space X_{3}\) be the new numbers
obtained after multiplying by its remainders. By adding the numbers
\(X_{1} + X_{2} + X_{3}\) , we get x. In the coordinate plane it’s addition of (3, 0, 0) + (0, 5, 0) + (0, 0, 7) = (3, 5, 7).
And to know more about finding modular inverse take a look at my Solving Linear Diophantine Equation using Extended Euclid Method.
For references: