Let $m_1$, $m_2$, ..., $m_k$ be pairwise relatively prime; $M=m_1m_2\cdots m_k$; $M_1=M/m_1$, $M_2=M/m_2$, ..., $M_k=M/m_k$; and $M_1y_1\equiv1(\text{mod }m_1)$, $M_2y_2\equiv1(\text{mod }m_2)$, ..., $M_ky_k\equiv1(\text{mod }m_k)$. How can I show that $M_1y_1+M_2y_2+\cdots+M_ky_k\equiv1(\text{mod }M)?$
Evaluating a Simple Congruence
1
$\begingroup$
elementary-number-theory
-
0This is the last step of a long theorem I am trying to prove. I just cannot seem to find a way. :/ – 2012-03-07
1 Answers
3
Hint $\rm\ mod\ m_i\!:\ y_i\equiv M_i^{-1}\Rightarrow M_i y_i\equiv M_i M_i^{-1}\equiv 1 $.
And $\rm\:j\ne i\:\Rightarrow\ m_i\ |\ M_j\:\Rightarrow\: M_j y_j\equiv 0\pmod{ m_i}$
Thus, mod $\rm\:m_i,\:$ the $\rm\:i$'th term of the sum is $1$ and all other terms are $0$.
The expression is the solution of $\rm\: x\equiv 1 \pmod{m_i},\:$ as constructed by Chinese remainder.