Friday, 28 November 2025

Exercise (3.4).3

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


The problem can be formulated as solving the following simultaneous linear congruencies

$ x \equiv 2 \pmod 7 $

$ x \equiv 3 \pmod 9 $

$ x \equiv 6 \pmod {11} $

The modulii 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  = 2(9 \times 11)x_1 + 3(7 \times 11)x_2 + 6(7 \times 9)x_3 $$

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

$$ \begin{align} 99 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 1 \pmod 7  \end{align}$$

and

$$ \begin{align} 77 x_2 & \equiv 1 \pmod 9 \\ \\ 5 x_2 & \equiv 1 \pmod 9 \\ \\ x_2 & \equiv 2 \pmod 9  \end{align}$$

also

$$ \begin{align} 63 x_3 & \equiv 1 \pmod {11} \\ \\ 8 x_3 & \equiv 1 \pmod {11}  \\ \\ x_3 & \equiv 7 \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  = 2(9 \times 11)1 + 3(7 \times 11)2 + 6(7 \times 9)7 = 3306 $$

The general unique solution is 

$$ \begin{align} x & \equiv 3306 \pmod {7 \times 9 \times 11} \\ \\ x & \equiv 534 \pmod {693} \end{align}$$

That is, for some integer $t$

$$ x = 534 + 693t$$

The least positive solution is $x=534$.