evinda
Gold Member
MHB
- 3,741
- 0
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)
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)