Saturday, 29 November 2025

Exercise (3.4).9

Prove Proposition (3.24).


Proposition (3.24) is as follows.

Let $n_1, n_2, n_3, \ldots , n_r$ be positive integers which are pairwise prime. Also, integers $c_k$’s satisfy $\gcd (c_k, n_k) = 1$ for $k= 1, 2, \ldots , n$. Then the simultaneous linear congruences

$c_1 x ≡ b_1 \pmod {n_1}$

$c_2 x ≡ b_2 \pmod {n_2}$

$c_r x ≡ br \pmod {n_r}$

have a solution satisfying all these equations. 

Moreover, the solution is unique modulo $n_1 × n_2 × n_3 × ⋯ × n_r$.


We're given that $\gcd(c_k, n_k)=1$ which means a linear congruence of the form $c_k x \equiv b_k \pmod {n_k}$ has a unique solution. This is Corollary (3.19), a specialisation of Proposition (3.16).

This means the simultaneous linear congruences are of the form

$ x \equiv d_1 \pmod {n_1}$

$ x \equiv d_1 \pmod {n_2}$

$\vdots$

$ x \equiv d_r \pmod {n_r}$

Since the modulii are all pair-wise corpime, then the Chinese Remainder Theorem can be used to find a unique solution modulo $n_1 \times n_2 \times \ldots \times n_r$.