 # Consider the system of linear congruences below: x -= 2(mod 5) 2x -= 22(mod 8) 3x -= 12(mod 21) (i)Determine two different systems of linear congruences for which the Chinese Remainder Theorem can be used and which will give at least two of these solutions. sodni3 2021-01-13 Answered
Consider the system of linear congruences below:
$x\equiv 2\left(\text{mod}5\right)$
$2x\equiv 22\left(\text{mod}8\right)$
$3x\equiv 12\left(\text{mod}21\right)$
(i)Determine two different systems of linear congruences for which the Chinese Remainder Theorem can be used and which will give at least two of these solutions.
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 curwyrm
Step 1
i)Given that
$x\equiv 2\left(\text{mod}5\right)$
$2x\equiv 22\left(\text{mod}8\right)$
$3x\equiv 12\left(\text{mod}21\right)$
Notice first that the moduli are pairwise relatively prime, therefore, we can use the Chinese remainder theorem. In the notation of the Chinese remainder theorem,
${m}_{1}=5,{m}_{2}=8,{m}_{3}=21$
$M={m}_{1}{m}_{2}{m}_{3}=5.8.21$
M=840
${M}_{1}=\frac{M}{{m}_{1}}=\frac{840}{5}=168$
${M}_{2}=\frac{M}{{m}_{2}}=\frac{840}{8}=105$
${M}_{3}=\frac{M}{{m}_{3}}=\frac{840}{21}=40$
Step 2
Now the linear congruences
${M}_{1}{y}_{1}\equiv 1\left(\text{mod}5\right)⇒168{y}_{1}\equiv 1\left(\text{mod}5\right)$
${M}_{2}{y}_{2}\equiv 1\left(\text{mod}8\right)⇒105{y}_{2}\equiv 1\left(\text{mod}8\right)$
${M}_{3}{y}_{3}\equiv 1\left(\text{mod}21\right)⇒40{y}_{3}\equiv 1\left(\text{mod}21\right)$
which are satisfied by
${y}_{1}=2$
${y}_{2}=\frac{1}{8}$
${y}_{3}=-\frac{1}{2}$
Thus the solution to the system is given by
$x=\left(2.168.2\right)+\left(22.105\frac{.1}{8}\right)+\left(12.40.\left(-\frac{1}{2}\right)\right)$
$=672+\frac{561}{2}-\frac{480}{2}$
$=672+\frac{81}{2}$
x=676.5
x=677
modulo 840.So the solutions form the congruence class of 677 modulo 840.
Thus, the general solution is
x=677 + 840k, $k\in \mathbb{Z}$.