Friday, 28 November 2025

Exercise (3.4).4

Find the least positive integer which leaves remainder 1 when divided by 5, remainder 2 when divided by 7, remainder 3 when divided by 9, and remainder 4 when divided by 11.


The problem can be formulated as solving the following simultaneous linear congruences.

$ x \equiv 1 \pmod 5 $

$ x \equiv 2 \pmod 7 $

$ x \equiv 3 \pmod 9 $

$ x \equiv 4 \pmod {11} $

The modulii 5, 7, 9 and 11 are coprime, so we can use the Chinese Remainder Theorem.

Formula (3.23) here is

$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3  + a_4 N_4 x_4 = 1(7 \times 9 \times 11)x_1 + 2(5 \times 9 \times 11)x_2 + 3(5 \times 7 \times 11)x_3 + 4(5 \times 7 \times 9)x_4 $$

where $N_k x_k \equiv 1 \pmod {n_k}$, and so

$$ \begin{align} 693 x_1 & \equiv 1 \pmod 5 \\ \\  3 x_1 & \equiv 1 \pmod 5 \\ \\ x_1 & \equiv 2 \pmod 5  \end{align}$$

and

$$ \begin{align} 495 x_2 & \equiv 1 \pmod 7 \\ \\ 5 x_2 & \equiv 1 \pmod 7 \\ \\ x_2 & \equiv 3 \pmod 7  \end{align}$$

also

$$ \begin{align} 385 x_3 & \equiv 1 \pmod 9 \\ \\ 7 x_3 & \equiv 1 \pmod 9 \\ \\ x_3 & \equiv 4 \pmod 9 \end{align}$$

and also

$$ \begin{align} 315 x_4 & \equiv 1 \pmod {11} \\ \\ 7 x_4 & \equiv 1 \pmod {11} \\ \\ x_4 & \equiv 8 \pmod {11} \end{align}$$

This gives

$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3  + a_4 N_4 x_4 = 1(7 \times 9 \times 11)2 + 2(5 \times 9 \times 11)3 + 3(5 \times 7 \times 11)4 + 4(5 \times 7 \times 9)8 =  19056$$

The general unique solution is 

$$ \begin{align} x & \equiv 19056 \pmod {5 \times 7 \times 9 \times 11} \\ \\ x & \equiv 1731 \pmod {3465} \end{align}$$

That is, for some integer $t$

$$ x = 1731 + 3465t$$

The least positive solution is $x=1731$.