Question

Complete the proof of the Chinese remainder theoremby showing that the simultaneous solution of a systemof linear congruences modulo pairwise relatively primemoduli Is unique modulo the product of these moduli.[Hint: Assume that x and y are two simultaneous solutions. Show that $\mathbf{mi}\mathbf{\mid }\mathbf{x}\mathbf{-}\mathbf{y}$for all i. Using Exercise 29,

conclude that$\mathbf{m}\mathbf{=}\mathbf{m}\mathbf{1}\mathbf{m}\mathbf{2}\mathbf{\cdots }\mathbf{mn}\mathbf{\mid }\mathbf{x}\mathbf{-}\mathbf{y}\mathbf{.}\mathbf{]}$

Short answer

$\mathbf{m}\mathbf{=}\mathbf{m}\mathbf{1}\mathbf{m}\mathbf{2}\mathbf{\cdots }\mathbf{mn}\mathbf{\mid }\mathbf{x}\mathbf{-}\mathbf{y}\mathbf{.}\mathbf{]}$The solution is unique

Step-by-step solution

Step1

The Chinese remainder theorem can be applied to systems with moduli that are not co-prime, but a solution to such a system does not always exist. $\{\mathrm{x}\equiv 5(mod6)\mathrm{x}\equiv 3(mod8)\cdot 5(mod6)\equiv 3(mod8)$ Note that the greatest common divisor of the moduli is 2.

Step2

Suppose X and Y are two simultaneous solutions to a system of congruences. Then we have the following congruences –

$\mathrm{x}\equiv {\mathrm{a}}_{1}mod{\mathrm{m}}_1,,,\mathrm{y}\equiv {\mathrm{a}}_{1}mod{\mathrm{m}}_1$

\dots

$\mathrm{x}\equiv {\mathrm{a}}_{\mathrm{n}}mod{\mathrm{m}}_{\mathrm{n}},,,\mathrm{y}\equiv {\mathrm{a}}_{\mathrm{n}}mod{\mathrm{m}}_{\mathrm{n}}$

Combining the two congruences in the rows we have

$\mathrm{x}\equiv \mathrm{y}mod{\mathrm{m}}_1$

\dots

$\mathrm{x}\equiv \mathrm{y}mod{\mathrm{m}}_{\mathrm{n}}$

Exercise 29 shows that

$\mathrm{x}\equiv \mathrm{y}mod{\mathrm{m}}_1\dots {\mathrm{m}}_{\mathrm{n}}$

Hence the solution is unique