# 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?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it

## Expert Answer

curwyrm
Answered 2021-01-14 Author has 87 answers
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}$.
###### Not exactly what you’re looking for?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it