Solve the following simultaneous equations. Write down the general solution and the least positive integer which satisfies these equations:
(a) $2x ≡ 1 \pmod 3$, $5x ≡ 2 \pmod 7$
(b) $2x ≡ 1 \pmod {13}$, $3x ≡ 2 \pmod {19}$
(c) $3x ≡ 5 \pmod 7$, $5x ≡ 2 \pmod {11}$, $9x ≡ 1 \pmod {5}$
(d) $x ≡ 3 \pmod 7$, $x ≡ 9 \pmod {11}$
(a) We rewrite the equations to isolate the variable $x$
$ 2x \equiv 1 \pmod 3 \iff 4x \equiv 2 \pmod 3 \iff x \equiv 2 \pmod 3 $
$ 5x \equiv 2 \pmod 7 \iff 15x \equiv 6 \pmod 7 \iff x \equiv 6 \pmod 7$
The modulii 3 and 7 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 2 \pmod 3 $
$x ≡ 6 \pmod 7$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 2(7)x_1 + 6(3)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 7 x_1 & \equiv 1 \pmod 3 \\ \\ x_1 & \equiv 1 \pmod 3 \end{align}$$
and
$$ \begin{align} 3 x_2 & \equiv 1 \pmod 7 \\ \\ x_2 & \equiv 5 \pmod 7 \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 2(7)1 + 6(3)5 = 104$$
The general unique solution is
$$ \begin{align} x & \equiv 104 \pmod {3 \times 7} \\ \\ x & \equiv 20 \pmod {21} \end{align}$$
That is, for some integer $t$
$$ x = 20 + 21t$$
The least positive solution is $x=20$.
(b) We rewrite the equations to isolate the variable $x$
$ 2x \equiv 1 \pmod {13} \iff 14x \equiv 7 \pmod {13} \iff x \equiv 7 \pmod {13} $
$ 3x \equiv 2 \pmod {19} \iff 39x \equiv 26 \pmod {19} \iff x \equiv 7 \pmod {19} $
The modulii 13 and 19 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$ x \equiv 7 \pmod {13} $
$ x \equiv 7 \pmod {19} $
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 7(19)x_1 + 7(13)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 19 x_1 & \equiv 1 \pmod {13} \\ \\ 6 x_1 & \equiv 1 \pmod {13} \\ \\ x_1 & \equiv 11 \pmod {13} \end{align}$$
and
$$ \begin{align} 13 x_2 & \equiv 1 \pmod {19} \\ \\ x_2 & \equiv 3 \pmod {19} \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 7(19)11 + 7(13)3 = 1736$$
The general solution is
$$ \begin{align} x & \equiv 1736 \pmod {13 \times 19} \\ \\ x & \equiv 7 \pmod {247} \end{align}$$
That is, for some integer $t$
$$ x = 7 + 247t$$
The least positive solution is $x=7$.
(c) We rewrite the equations to isolate the variable $x$
$ 3x \equiv 5 \pmod 7 \iff 15x \equiv 25 \pmod 7 \iff x \equiv 4 \pmod 7 $
$ 5x \equiv 2 \pmod {11} \iff 45x \equiv 18 \pmod {11} \iff x \equiv 7 \pmod {11} $
$ 9x \equiv 1 \pmod {5} \iff 4x \equiv 1 \pmod 5 \iff 16x \equiv 4 \pmod 5 \iff x \equiv 4 \pmod 5$
The modulii 7, 11 and 5 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve.
$ x \equiv 4 \pmod 7 $
$ x \equiv 7 \pmod {11} $
$ x \equiv 4 \pmod 5$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 4(11 \times 5)x_1 + 7(7 \times 5)x_2 + 4(7 \times 11)x_3$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 55 x_1 & \equiv 1 \pmod 7 \\ \\ 6 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 6 \pmod 7 \end{align}$$
and
$$ \begin{align} 35 x_2 & \equiv 1 \pmod {11} \\ \\ 2 x_2 & \equiv 1 \pmod {11} \\ \\ x_2 & \equiv 6 \pmod {11} \end{align}$$
also
$$ \begin{align} 77 x_3 & \equiv 1 \pmod 5\\ \\ 2 x_3 & \equiv 1 \pmod 5 \\ \\ x_3 & \equiv 3 \pmod 5 \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 4(11 \times 5)6 + 7(7 \times 5)6 + 4(7 \times 11)3 = 3714 $$
The general solution is
$$ \begin{align} x & \equiv 3714 \pmod {7 \times 11 \times 5} \\ \\ x & \equiv 249 \pmod {385} \end{align}$$
That is, for some integer $t$
$$ x = 249 + 385t$$
The least positive solution is $x=249$.
(d) The modulii 7 and 11 are pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 3 \pmod 7$
$x ≡ 9 \pmod {11}$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 3(11)x_1 + 9(7)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 11 x_1 & \equiv 1 \pmod {7} \\ \\ 4 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 2 \pmod 7 \end{align}$$
and
$$ \begin{align} 7 x_2 & \equiv 1 \pmod {11} \\ \\ x_2 & \equiv 8 \pmod {11} \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 3(11)2 + 9(7)8 = 570$$
The general solution is
$$ \begin{align} x & \equiv 570 \pmod {7 \times 11} \\ \\ x & \equiv 31 \pmod {77} \end{align}$$
That is, for some integer $t$
$$ x = 31 + 77t$$
The least positive solution is $x=31$.