1
$\begingroup$

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)?$

  • 0
    This 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 1

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.