Use the Chinese Remainder theorem to solve the simultaneous congruences x Tmod(2

Question

Use the Chinese Remainder theorem to solve the simultaneous congruences x Tmod(20) and x 2mod(17) The Chinese Remainder Theorem states that if the modulus are pairwise coprime a system of simultaneous congruences can be solved. This is not the only time where that can happen. One of the below pairs of congruences can be solved, one can't. Solve the one that you can, and explain why you can't solve the other one. (Be careful to find all solutions) x 7mod(14) and x lmod(24) x 7mod(14) and x 4mod(24)

Explanation / Answer

X=7[MOD 20]...............................1

X=2[MOD 17]........................................2

X=2+17P.....................................3

WHERE P IS AN INTEGER

PUTTING 3 IN 1

2+17P=7[MOD 20]

17P=5[MOD 20]..................GCD[17,20]=1 ...1|5....OK....SOLUTION EXISTS

0=80[MOD 20]

ADDING

17P=85[MOD 20]

P=5[MOD 20]

P=5+20Q

PUTTING IN 3 WE GET

X=2+17[5+20Q]=87+340 Q

X=87 [MOD 340]

X=[.....-933,-593,-253,87,427,767,1107,....ETC]......ANSWER

==============================================

X=7[MOD 14]

X=1[MOD 24]

PROCEEDING AS ABOVE ...

X=1+24P

1+24P=7[MOD 14]

24P=6[MOD 14]..............GCD[24,14]=2 ...2|6....OK....SOLUTION EXISTS

0=42 [MOD 14]

ADDING

24P=48[MOD 14]

P=2[MOD 14]

P=2+14Q

X=1+24[2+14Q]=49+336Q

X=[........-959,-623,-287,49,385,721,1057,......]

==============================================

X=7[MOD 14]

X=4[MOD 24]

X=4+24P

4+24P=7[MOD 14]

24P=3[MOD 14]

WE HAVE GCD[24,14]=2

2 IS NOT A DIVISOR OF 3

SO THERE IS NO SOLUTION.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.