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
ANSWERED
asked 2021-02-04
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}\).

Answers (1)

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\)

0
 
Best answer

expert advice

Have a similar question?
We can deal with it in 3 hours
...