Rikki edited untitled.html  about 8 years ago

Commit id: 28c8a2f1e146f84bfc1851ef9d31c93c7b9343ad

deletions | additions      

       

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 data-equation="a_2">\(a_2\) be data-equation="a_2">\(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 by using our equation: \(N=m_1a_2x+m_2a_1y\)