Question

# Find all solutions to the following system of linear congruences: x-= 1 mod 2, x -= 2 mod 3, x-= 3 mod 5, x -= 4 mod 7, x -= 5 mod 11.

Congruence
Find all solutions to the following system of linear congruences: $$\displaystyle{x}\equiv{1}\text{mod}{2},{x}\equiv{2}\text{mod}{3},{x}\equiv{3}\text{mod}{5},{x}\equiv{4}\text{mod}{7},{x}\equiv{5}\text{mod}{11}$$.

2021-02-05

Step 1
The system of linear congruence’s are given by,
$$\displaystyle{x}\equiv{1}\text{mod}{2}$$
$$\displaystyle{x}\equiv{2}\text{mod}{3}$$
$$\displaystyle{x}\equiv{3}\text{mod}{5}$$
$$\displaystyle{x}\equiv{4}\text{mod}{7}$$
$$\displaystyle{x}\equiv{5}\text{mod}{11}$$
Step 2
According to the Chinese Remainder Theorem,
$$M=2 \cdot3 \cdot 5 \cdot 7 \cdot 11=2310$$
$$\displaystyle{M}_{{1}}=\frac{{M}}{{2}}=\frac{{2310}}{{2}}={1155}$$
$$\displaystyle{M}_{{2}}=\frac{{M}}{{3}}=\frac{{2310}}{{3}}={770}$$
$$\displaystyle{M}_{{3}}=\frac{{M}}{{5}}=\frac{{2310}}{{5}}={462}$$
$$\displaystyle{M}_{{4}}=\frac{{M}}{{7}}=\frac{{2310}}{{7}}={330}$$
$$\displaystyle{M}_{{5}}=\frac{{M}}{{11}}=\frac{{2310}}{{11}}={210}$$
Step 3
Find the value of $$\displaystyle{y}_{{1}},{y}_{{2}},{y}_{{3}},{y}_{{4}},{y}_{{5}}$$.
$$\displaystyle{1}{y}_{{1}}\equiv{1}\text{mod}{2}\Rightarrow{y}_{{1}}={1}$$
$$\displaystyle{2}{y}_{{2}}\equiv{1}\text{mod}{3}\Rightarrow{y}_{{2}}={2}$$
$$\displaystyle{2}{y}_{{3}}\equiv{1}\text{mod}{5}\Rightarrow{y}_{{3}}={3}$$
$$\displaystyle{1}{y}_{{4}}\equiv{1}\text{mod}{7}\Rightarrow{y}_{{4}}={1}$$
$$\displaystyle{1}{y}_{{5}}\equiv{1}\text{mod}{11}\Rightarrow{y}_{{5}}={1}$$
Step 4
Solution is,
$$\displaystyle{x}={\left({1}{M}_{{1}}{y}_{{1}}+{2}{M}_{{2}}{y}_{{2}}+{3}{M}_{{3}}{y}_{{3}}+{4}{M}_{{4}}{y}_{{4}}+{5}{M}_{{5}}{y}_{{5}}\right)}\text{mod}{M}$$
$$\displaystyle{x}={\left({1}\times{1155}\times{1}+{2}\times{770}\times{2}+{3}\times{462}\times{3}+{4}\times{330}\times{1}+{5}\times{210}\times{1}\right)}\text{mod}{2310}$$
$$x=10763 \mod 2310$$
$$x=1403 \mod 2310$$