2
$\begingroup$

I ran into this version of the Chinese Remainder Theorem:

Show that the solutions to the simultaneous system of congruences $x\equiv a_1\pmod{m_1},$ $x\equiv a_2\pmod{m_2},$ $...$ $x\equiv a_r\pmod{m_r},$ where the $m_j$ are pairwise relatively prime, are given by $x\equiv a_1M_1^{\phi(m_1)}+a_2M_2^{\phi(m_2)}+\cdots+a_rM_r^{\phi(m_r)}\pmod{M},$ where $M=m_1m_2\cdots m_r$ and $M_j=M/m_j$ for $j=1, 2, ..., r.$

This is basically the exact Chinese Remainder Theorem, except that instead of $x_jM_jy_j$, we have $x_jM_j^{\phi(m_j)}$. Would it then suffice to show that $x_jM_j^{\phi(m_j)}\equiv x_jM_jy_j\pmod{M}$? If so, how could I go about it? Thanks in advance!

  • 0
    @GerryMyerson, $y_j$ is the inverse of $M_j$ modulus $m_j$. I will try what you suggested.2012-03-07

1 Answers 1

2

Hint $\ $ Both $\rm\: M_i^{\phi(m_i)}$ and $\rm\:M_i ({M_i}^{-1}\ mod\ m_i)\:$ are $\rm\:\equiv 1\pmod{m_i},\:$ and $\rm\:\equiv 0\pmod{m_j},\ j\ne i$

since $\rm\:gcd(M_i,m_i) = 1,\:$ and $\rm\:j\ne i\:\Rightarrow\:m_j\ |\ M_i $