Main Data History
Show Index Toggle 0 comments

The Chinese Remainder Theorem

The Chinese Remainder Theorem is used in discrete mathematics to find a unique solution up to a desired modulus. 
The Chinese Remainder Theorem states: If \(m_1\) and \(m_2\) are relatively prime, the the system of congruences \(N\equiv a_1\) (mod \(m_1\)), \(N\equiv a_2\) (mod \(m_2\)) has a unique solution (mod \(m_1m_2\)).

From this theorem, we can generalize and say that if \(m_1\) and \(m_2\) are relatively prime, then we can allow \(a_1\) and \(a_2\) to be any two integers. There will exist an integer \(N\) that satisfies the expressions above. 

With \(\left(m_1,m_2\right)=1,\) there exists \(x\) and \(y\) that satisfies \(m_1x+m_2y=1.\) We can find \(x\) and \(y\) by plugging in numbers to find solutions that work or we can use the Euclidean Algorithm and back substitution to find the solutions. 

From here, the solution to the system of congruences  is found by using our formula: \(N=m_1a_2x+m_2a_1y\)
Let's work through an example where \(N\equiv3\) (mod \(14\)) and \(N\equiv7\) (mod \(19\)).
First, notice that \(\left(14,19\right)=1\). We can find a solution to \(14x+19y=1\).
By playing around with different numbers, we get our solutions to be \(x=-4\) and \(y=3\).
We now have all our values: \(m_1=14,m_2=19,a_1=3,a_2=7,x=-3,y=7\) and can now solve \(N=m_1a_2x+m_2a_1y\).
So \(N=105\), however, our unique solution is up to our desired modulus which is \(14\cdot19=266\).
Thus, \(N=105\) (mod \(266\)).
Suggested Exam Problem: When a high school teacher tries to divide her students into groups, she finds that if she divides them into groups of \(11\), there are \(7\) students left over. When she tries to divide the students into groups of \(13\), there are \(6\) students left over. How many students are in the class?