(a) Let $p$ and $q$ be distinct primes such that $x ≡ M \pmod p$ and $x ≡ M \pmod q$ . Show that $x ≡ M \pmod {pq}$.
(b) Let $p_1, p_2, p_3, \ldots , p_k$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2, 3, \ldots , k$. Show that $x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k}$.
(c) Prove that $a ≡ b \pmod {m_k} \iff a ≡ b \pmod {[m_1, m_2, \ldots , m_n]}$.
(a) We're given $x ≡ M \pmod p$ and $x ≡ M \pmod q$, which means
$$ p \mid (x - M) $$
$$ q \mid (x - M) $$
That is, $(x-M)$ is a multiple of $p$ and also a multiple of $q$.
This means $(x-M)$ is a multiple of the lowest common multiple of $p$ and $q$, denoted $[p,q]$.
$$ [p,q] \mid (x - M)$$
By Proposition (2.22) which states that $\gcd(a,b) \times [a,b] = a \times b$, and noting that $\gcd(p,q)=1$ because $p$ and $q$ are distinct primes, we have
$$ p \times q \mid (x - M) $$
which is equivalent to the statement
$$ x \equiv M \pmod {pq} $$
(b) We show this by induction on $k$.
Let statement $P(k)$ be
Let $p_1, p_2, p_3, \ldots , p_k$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2, 3, \ldots , k$. Then $x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k}$.
We need to show both the base case $P(2)$ and the inductive step $P(k) \implies P(k+1)$.
Base Case $P(2)$
The base case $P(2)$ is
Let $p_1, p_2$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2$. Then $x ≡ M \pmod {p_1 × p_2}$.
We showed this in part (a), and so the base case is true.
Inductive Step $P(k) \implies P(k+1)$
We assume $P(k)$ is true as the induction hypothesis, and show $P(k+1)$ which is
Let $p_1, p_2, p_3, \ldots , p_k, p_{k+1}$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2, 3, \ldots , k, k+1$. Then $x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k \times p_{k+1}}$.
We have
$$ \begin{align} \prod_{i=1}^k p_i & \mid (x - M) \quad \text{induction hypothesis} \\ \\ p_{k+1} & \mid (x - M) \end{align}$$
That is, $(x-M)$ is a multiple of both $ \prod_{i=1}^k p_i$ and $p_{k+1}$. This means $(x-M)$ is a multiple of the lowest common multiple of $ \prod_{i=1}^k p_i$ and $p_{k+1}$, denoted $[ \prod_{i=1}^k p_i, p_{k+1}]$.
By Proposiiton (2.22)
$$ \gcd(\prod_{i=1}^k p_i , p_{k+1}) \times [\prod_{i=1}^k p_i , p_{k+1}] = \prod_{i=1}^{k+1} p_i $$
The $p_1, p_2, \ldots, p_{k+1}$ are all prime, so $ \gcd(\prod_{i=1}^k p_i , p_{k+1}) =1$, which gives us
$$ [\prod_{i=1}^k p_i , p_{k+1}] = \prod_{i=1}^{k+1} p_i $$
That is, $(x-M)$ is a multiple of $ \prod_{i=1}^{k+1} p_i$, which is equivalent to
$$ x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k \times p_{k+1}} $$
And so the inductive step is proven, $P(k) \implies P(k+1)$.
By induction we have proven the given statement.
(c) The statement
$$ a \equiv b \pmod {m_k} \iff a \equiv b \pmod {[m_1, m_2, \ldots , m_n]} $$
means, for all $k \in \{1,2, \ldots, n\}$, that $a \equiv b \pmod {m_k}$ is equivalent to $a \equiv b \pmod {[m_1, m_2, \ldots , m_n]}$.
($\impliedby$)
We assume $a \equiv b \pmod {[m_1, m_2, \ldots , m_n]}$. This means
$$ [m_1, m_2, \ldots, m_n] \mid (a-b) $$
Since by definition $ [m_1, m_2, \ldots, m_n] $ is a multiple of any one $m_k$, then we have
$$ m_k \mid [m_1, m_2, \ldots, m_n] \quad \land \quad [m_1, m_2, \ldots, m_n] \mid (a-b) $$
from which we have
$$ m_k \mid (a-b) $$
That is,
$$ a \equiv b \pmod {m_k} $$
($\implies$)
We assume $a \equiv b \pmod {m_k}$ for all $k \in \{1,2, \ldots, n\}$. This means
$$ m_k \mid (a-b) $$
That is, $(a-b)$ is a multiple of all $m_k$. Which means $(a-b)$ is a multiple of the lowest common multiple of all the $m_k$.
$$ [m_1, m_2, \ldots, m_n] \mid (a-b) $$
Which is equivalent to
$$ a \equiv b \pmod {[m_1, m_2, \ldots, m_n]} $$
We have shown both directions of the implication, and so we have shown that
$$ a \equiv b \pmod {m_k} \iff a \equiv b \pmod {[m_1, m_2, \ldots , m_n]} $$
Alternative Solution
By definition of congruence, we rewrite $a \equiv b \pmod {m_k}$ as $m_k \mid (a-b)$, which holds for all $k \in \{1,2, \ldots, n\}$.
Since $(a-b)$ is a multiple of all $m_k \in \{m_1, m_2, \ldots, m_n\}$ then $(a-b)$ is a multiple of the lowest common multiple of all the elements of $\{m_1, m_2, \ldots, m_n\}$.
$$ \forall_{k \in \{1,2, \ldots, n\}}\; a \equiv b \pmod {m_k} \quad \iff \quad \forall_{k \in \{1,2, \ldots, n\}}\; m_k \mid (a-b) \quad \iff \quad [m_1, m_2, \ldots, m_n] \mid (a-b) $$
which is equivalent to $a \equiv b \pmod {[m_1, m_2, \ldots, m_n]}$, and so we can conclude
$$ a \equiv b \pmod {m_k} \iff a \equiv b \pmod {[m_1, m_2, \ldots , m_n]} $$