MHB Why Must We Solve Linear Congruences in the Chinese Remainder Theorem?

[evinda]

Hey! (Wasntme)

I am looking at the proof of the Chinese remainder theorem,which is:
Let $m_1,m_2, \dots, m_n$ be pairwise coprime.
Then the system $$\left\{\begin{matrix}
x \equiv c_1 \pmod {m_1}\\
\dots \dots\\
x \equiv c_n \pmod {m_n}
\end{matrix}\right.$$

is equivalent with one linear congruence of the form $x \equiv c \pmod {m_1 \dots m_n} $ for a ($\text{ unique } \pmod {m_1 \dots m_n} c$).

At the proof,we consider the numbers:

$M=m_1 \cdots m_n $
$M_j=\frac{M}{m_j}, 1 \leq j \leq n$

$\forall j$ we solve the linear congruence

$$M_j \cdot x \equiv c_j \pmod{m_j}$$

But...why do we have to solve this linear congruence? (Thinking)

 

[chisigma]

Hey! (Wasntme)

I am looking at the proof of the Chinese remainder theorem,which is:
Let $m_1,m_2, \dots, m_n$ be pairwise coprime.
Then the system $$\left\{\begin{matrix}
x \equiv c_1 \pmod {m_1}\\
\dots \dots\\
x \equiv c_n \pmod {m_n}
\end{matrix}\right.$$

is equivalent with one linear congruence of the form $x \equiv c \pmod {m_1 \dots m_n} $ for a ($\text{ unique } \pmod {m_1 \dots m_n} c$).

At the proof,we consider the numbers:

$M=m_1 \cdots m_n $
$M_j=\frac{M}{m_j}, 1 \leq j \leq n$

$\forall j$ we solve the linear congruence

$$M_j \cdot x \equiv c_j \pmod{m_j}$$

But...why do we have to solve this linear congruence? (Thinking)

The procedure is explained here...

http://mathhelpboards.com/number-theory-27/applications-diophantine-equations-6029.html#post28283

Kind regards

$\chi$ $\sigma$

 

[evinda]

The procedure is explained here...

http://mathhelpboards.com/number-theory-27/applications-diophantine-equations-6029.html#post28283

Kind regards

$\chi$ $\sigma$

I still haven't understood why we have to solve the system $M_j \cdot x \equiv c_j \pmod {m_j}$... (Sweating)

 

[I like Serena]

I still haven't understood why we have to solve the system $M_j \cdot x \equiv c_j \pmod {m_j}$... (Sweating)

Hey! (Emo)

It's the first step in the proof...
The reason why we're solving that system will become apparent in a later step where everything cancels nicely. (Nerd)

 

[evinda]

Hey! (Emo)

It's the first step in the proof...
The reason why we're solving that system will become apparent in a later step where everything cancels nicely. (Nerd)

Ok..thank you very much! :)