Question

Let \({m_1}\) and \({m_2}\) be two relatively prime integers. This implies \({m_1} = \)

Prime decomposition.

Short answer

This implies Proven using the \({m_1}\; = \) prime decomposition

Step-by-step solution

Step 1

Let \({m_1} = \)and \({m_2}\) be two relatively

Prime decomposition. prime integers. This implies \({m_1} = \)

\(p_1^{{\alpha _1}} \ldots p_k^{{\alpha _k}}\) and \({m_2} = q_1^{{\beta _1}} \ldots q_l^{{\beta _l}}\)

with\({p_i} \ne {q_j}\) for any i , j.

Given\(a \equiv b\,\bmod \,{m_1}\)and\(a \equiv b\,\bmod \,{m_2}\),that is\((a - b)\) is divisible by \({m_1}\)and \({m_2}\)

Decompose (a-b) into prime factors and note that \({p_i} \ne {q_j}\) for any i, j.

Then\(\left( {a - b} \right)\) = \(p_1^{{\alpha _1}} \ldots p_k^{{\alpha _k}}q_1^{{\beta _1}} \ldots q_l^{{\beta _l}}\)

Where s is an integer.

Thus \(a \equiv b\bmod {m_1}{m_2}\)

Step 2

We will repeatedly apply the above result to obtain the general result

Could have proved by induction

Suppose \({m_1}, \ldots {m_n}\)are relatively prime integers such that\(a \equiv b\,\bmod \,m\) for all i.

Apply the above result to \({m_1},{m_2}\) get a new system with one lower number of equations.

Note that all the conditions are still satisfied, that is \({m_1}*\)

\({m_2},{m_3}, \ldots ,{m_n}\)are relatively prime still and the congruences are satisfied.

The above process is repeated till We obtain the desired result