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:
x2(mod5)
2x22(mod8)
3x12(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.
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
Learn more

Solve your problem for the price of one coffee

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

Expert Answer

curwyrm
Answered 2021-01-14 Author has 87 answers
Step 1
i)Given that
x2(mod5)
2x22(mod8)
3x12(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
M1y11(mod5)168y11(mod5)
M2y21(mod8)105y21(mod8)
M3y31(mod21)40y31(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+56124802
=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, kZ.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

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