 # 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 Dottie Parra 2020-11-12 Answered
Given the following system of linear simultaneous congruences what is the value of x that satisfies them all?
$x\equiv 18\text{mod}29$
$x\equiv 20\text{mod}31$
$x\equiv 6\text{mod}17$
You can still ask an expert for help

## Want to know more about Congruence?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it davonliefI
Step 1
According to the given information, it is required to find the value of x that satisfies all simultaneous congruence.
$x\equiv 18\text{mod}29$
$x\equiv 20\text{mod}31$
$x\equiv 6\text{mod}17$
Step 2
Using Chinese remainder theorem:
Let ${m}_{1},{m}_{2},\dots .{m}_{r}$ be a collection of pairwise relative prime integers.
then the system of simultaneous congruence
$x\equiv {a}_{1}\left(\text{mod}{m}_{1}\right)$
$x\equiv {a}_{2}\left(\text{mod}{m}_{2}\right)$
....
$x={a}_{r}\left(\text{mod}{m}_{r}\right)$
has a unique solution modulo $M={m}_{1}{m}_{2}\dots {m}_{r}$ for any integers ${a}_{1},{a}_{2}\dots ,{a}_{r}$
Step 3
Now using the above theorem solve the given question.
${a}_{1}=18,{a}_{2}=20,{a}_{3}=6$
$M=29×31×17=15283$
${m}_{1}=\frac{15283}{29}=527$
${m}_{2}=\frac{15283}{31}=493$
${m}_{3}=\frac{15283}{17}=899$
Step 4
Solving further:
${m}_{1}\stackrel{―}{{m}_{1}}=1\left(\text{mod}29\right)⇒527\stackrel{―}{{m}_{1}}=1\left(\text{mod}29\right)$
$5\stackrel{―}{{m}_{1}}=1\left(\text{mod}29\right)⇒\stackrel{―}{{m}_{1}}=35$
${m}_{2}\stackrel{―}{{m}_{2}}=1\left(\text{mod}31\right)⇒493\stackrel{―}{{m}_{2}}=1\left(\text{mod}31\right)$
$-3\stackrel{―}{{m}_{2}}=1\left(\text{mod}31\right)⇒\stackrel{―}{{m}_{2}}=10$
${m}_{3}\stackrel{―}{{m}_{3}}=1\left(\text{mod}17\right)⇒899\stackrel{―}{{m}_{3}}=1\left(\text{mod}17\right)$
$15\stackrel{―}{{m}_{3}}=1\left(\text{mod}17\right)⇒\stackrel{―}{{m}_{3}}=8$
Step 5
Therefore, the value of x is:
$x={a}_{1}{m}_{1}\stackrel{―}{{m}_{1}}+{a}_{2}{m}_{2}\stackrel{―}{{m}_{2}}+{a}_{3}{m}_{3}\stackrel{―}{{m}_{3}}$
$=\left(18×527×35\right)+\left(20×493×10\right)+\left(6×899×8\right)$
=332010+98600+43152
=473762(mod15283)
x=15272