Ask question
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

expert advice

...