Consider the system of linear congruences below: x≡2(mod5) 2x≡22(mod8) 3x≡12(mod21) (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.

Question

Consider the system of linear congruences below:  x≡2(mod5)  2x≡22(mod8)  3x≡12(mod21)  (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.

curwyrm · Accepted Answer

Step 1  i)Given that  x≡2(mod5)  2x≡22(mod8)  3x≡12(mod21)  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,   m1=5,m2=8,m3=21  M=m1m2m3=5.8.21  M=840  M1=Mm1=8405=168  M2=Mm2=8408=105  M3=Mm3=84021=40  Step 2  Now the linear congruences   M1y1≡1(mod5)⇒168y1≡1(mod5)  M2y2≡1(mod8)⇒105y2≡1(mod8)  M3y3≡1(mod21)⇒40y3≡1(mod21)  which are satisfied by  y1=2  y2=18  y3=−12  Thus the solution to the system is given by  x=(2.168.2)+(22.105.18)+(12.40.(−12))  =672+5612−4802  =672+812  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∈Z.

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.

Answered question

Answer & Explanation

New Questions in High school geometry