Question

Given the following system of linear simultaneous congruences what is the value of x that satisfies them all? x -= 18 mod 29 x -= 20 mod 31 x -= 6 mod 17

Congruence
ANSWERED
asked 2020-11-12
Given the following system of linear simultaneous congruences what is the value of x that satisfies them all?
\(\displaystyle{x}\equiv{18}\text{mod}{29}\)
\(\displaystyle{x}\equiv{20}\text{mod}{31}\)
\(\displaystyle{x}\equiv{6}\text{mod}{17}\)

Answers (1)

2020-11-13
Step 1
According to the given information, it is required to find the value of x that satisfies all simultaneous congruence.
\(\displaystyle{x}\equiv{18}\text{mod}{29}\)
\(\displaystyle{x}\equiv{20}\text{mod}{31}\)
\(\displaystyle{x}\equiv{6}\text{mod}{17}\)
Step 2
Using Chinese remainder theorem:
Let \(\displaystyle{m}_{{1}},{m}_{{2}},\ldots.{m}_{{r}}\) be a collection of pairwise relative prime integers.
then the system of simultaneous congruence
\(\displaystyle{x}\equiv{a}_{{1}}{\left(\text{mod}{m}_{{1}}\right)}\)
\(\displaystyle{x}\equiv{a}_{{2}}{\left(\text{mod}{m}_{{2}}\right)}\)
....
\(\displaystyle{x}={a}_{{r}}{\left(\text{mod}{m}_{{r}}\right)}\)
has a unique solution modulo \(\displaystyle{M}={m}_{{1}}{m}_{{2}}\ldots{m}_{{r}}\) for any integers \(\displaystyle{a}_{{1}},{a}_{{2}}\ldots,{a}_{{r}}\)
Step 3
Now using the above theorem solve the given question.
\(\displaystyle{a}_{{1}}={18},{a}_{{2}}={20},{a}_{{3}}={6}\)
\(\displaystyle{M}={29}\times{31}\times{17}={15283}\)
\(\displaystyle{m}_{{1}}=\frac{{15283}}{{29}}={527}\)
\(\displaystyle{m}_{{2}}=\frac{{15283}}{{31}}={493}\)
\(\displaystyle{m}_{{3}}=\frac{{15283}}{{17}}={899}\)
Step 4
Solving further:
\(\displaystyle{m}_{{1}}\overline{{{m}_{{1}}}}={1}{\left(\text{mod}{29}\right)}\Rightarrow{527}\overline{{{m}_{{1}}}}={1}{\left(\text{mod}{29}\right)}\)
\(\displaystyle{5}\overline{{{m}_{{1}}}}={1}{\left(\text{mod}{29}\right)}\Rightarrow\overline{{{m}_{{1}}}}={35}\)
\(\displaystyle{m}_{{2}}\overline{{{m}_{{2}}}}={1}{\left(\text{mod}{31}\right)}\Rightarrow{493}\overline{{{m}_{{2}}}}={1}{\left(\text{mod}{31}\right)}\)
\(\displaystyle-{3}\overline{{{m}_{{2}}}}={1}{\left(\text{mod}{31}\right)}\Rightarrow\overline{{{m}_{{2}}}}={10}\)
\(\displaystyle{m}_{{3}}\overline{{{m}_{{3}}}}={1}{\left(\text{mod}{17}\right)}\Rightarrow{899}\overline{{{m}_{{3}}}}={1}{\left(\text{mod}{17}\right)}\)
\(\displaystyle{15}\overline{{{m}_{{3}}}}={1}{\left(\text{mod}{17}\right)}\Rightarrow\overline{{{m}_{{3}}}}={8}\)
Step 5
Therefore, the value of x is:
\(\displaystyle{x}={a}_{{1}}{m}_{{1}}\overline{{{m}_{{1}}}}+{a}_{{2}}{m}_{{2}}\overline{{{m}_{{2}}}}+{a}_{{3}}{m}_{{3}}\overline{{{m}_{{3}}}}\)
\(\displaystyle={\left({18}\times{527}\times{35}\right)}+{\left({20}\times{493}\times{10}\right)}+{\left({6}\times{899}\times{8}\right)}\)
=332010+98600+43152
=473762(mod15283)
x=15272
0
 
Best answer

expert advice

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