(a) Prove that if $m \mid n$ and $a ≡ b \pmod n$ then $a ≡ b \pmod m$.
(b) Prove that if $ka ≡ kb \pmod {kn}$ then $a ≡ b \pmod n$ where $k > 0$.
(c) Prove that if $a ≡ b \pmod n$ and $a ≡ b \pmod m$ then $a ≡ b \pmod {m × n}$, provided $\gcd (m, n) = 1$.
(d) Let $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. Prove that $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r}$.
(e) Prove that if $n = p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$ where $p_j$’s are distinct primes and $a ≡ b \pmod n$ then $a ≡ b \pmod {p_j}$ for $j= 1, 2, \ldots , m$.
(a) $m \mid n$ means, for some integer $k$
$$ n = km $$
Also $a \equiv b \pmod n$ means, for some integer $j$
$$ a - b = jn $$
Substituting for $n$ we have
$$ a - b = (jk)m $$
which, by definition, is $a \equiv b \pmod m$.
(b) We're given $ka \equiv kb \pmod {kn}$, which by definition means, for some integer $j$
$$\begin{align} ka - kb & = jkn \\ \\ k(a-b) & = k(jn) \\ \\ a - b & = jn \quad \text{for } k>0\end{align}$$
Which, by definition, is $a \equiv b \pmod n$.
(c) We are given $a ≡ b \pmod n$ and $a ≡ b \pmod m$. This means, for some integers $j,k$
$$ a - b = jn $$
$$ a - b = km $$
By Bezout's identity, then for some integers $p,q$
$$ pm + qn = \gcd(m,n) = 1 $$
Multiplying by $a-b$
$$ \begin{align} a-b & = pm(jn) + qn(km) \\ \\ & a - b = (pj + qk)mn \end{align}$$
Which by definition means $a \equiv b \pmod{mn}$ as long as $\gcd(m,n)=1$
(d) We'll do this by induction. Let $P(r)$ be the statement
Let $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. Then $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r}$.
We need to prove the base case $P(2)$, and the inductive step $P(r) \implies P(r+1)$.
The base case $P(2)$ is
Let $a ≡ b \pmod {n_k}$ for $k= 1, 2$ where $\gcd (n_1,n_2) = 1$. Then $a ≡ b \pmod {n_1 × n_2 }$.
We proved this in exercise (c) above.
To prove $P(r) \implies P(r+1)$, we assume the induction hypothesis $P(r)$ and show $P(r+1)$, which is
Let $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r, r+1$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. Then $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r \times n_{r+1}}$.
Let's abbreviate $n_1 \times n_2 \times \ldots \times n_r$ as $A$.
The antecedent conditions of the induction hypotheses hold, namely that $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. This means the consequent holds, namely $a ≡ b \pmod A$.
Given $a \equiv b \pmod {A}$ and $a \equiv b \pmod {n_{r+1}}$, and it is true that $\gcd(A, n_{r+1})=1$ then by exercise (c) we have $a \equiv b \pmod {A \times n_{r+1}}$. Unabbreviating, that is $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r \times n_{r+1}}$.
Why is it true that $\gcd(A,n_{r+1}) = 1$? Well, we are given that $n_{r+1}$ is coprime to all $n_k$ for $k=1, 2, 3, \ldots, r$, and so $n_{r+1}$ shares no common factors with $A = n_1 \times n_2 \times \ldots \times n_r$.
So by induction we have shown the statement to be true for all $r$.
(e) We are given the prime decomposition of $n$ as
$$n = p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$$
where $p_j$’s are distinct primes.
We are also given $a ≡ b \pmod n$ which means that for integer $k$
$$ a - b = kn $$
Substituting for $n$
$$ a - b = k \times p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$$
Selecting a $p_j$ where $1 \le j \le m$, we factor it out
$$ a - b = \left ( k \times p_1^{k_1} × p_2^{k_2} × \ldots × p_j^{k_m - 1} \times \ldots \times p_m^{k_m} \right ) \times p_j$$
That is,
$$ a - b = m \times p_j$$
where $m$ is an integer, and so by definition
$$ a \equiv b \pmod {p_j} $$
for any $j$ in $1 \le j \le m$.
Note: the author's solution is neater. We're given $a ≡ b \pmod n$ which means $n \mid (a-b)$. Similarly we're given $n = p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$ which means $p_j \mid n$. Since $p_j \mid n$ and $n \mid (a-b)$ we have $p_j \mid (a-b)$, which by definition means $a \equiv b \pmod {p_j}$.