Question about finding simultaneous congruences using Chinese Remainder Therom

Question

I have these 3 congruence equations

x ≅ 37 mod 43

x ≅ 22 mod 49

x ≅ 18 mod 71

I have been using the Chinese Remainder Theorem to solve this question by converting the first two equations together into 37 + 43y ≅ 22 mod 49. When I finish I get a y value of 272 and when I find the x value it is way too big. I typed it into an online calculator and the result was way different than expected. Could anyone give me a step by step walkthrough? Please and Thank you

Answer 1

You have the correct idea. In general, we can write that x = 37 + 43a = 22 + 49b = 18 + 71c, for some a,b,c nonnegative integers. Therefore, we want to write x = 43*49A + 43*71B + 49*71C. We can determine A,B,C by taking our expression mod 43, 49, 71, respectively.

If we take this mod 43, then we want 49*71C = 37 mod 43. Since 49 = 6 mod 43 and 71 = 28 mod 43, we have that this is 6*28C = 37 mod 43. Since 6 is -37 mod 43 this is 28C = -1 mod 43. Since 14^(-1) = -3 = 40 mod 43 and 2^(-1) = 22 mod 43 we have that C = -40*22 = -880 = 23 mod 43.

Taking this mod 49 we want 43*71B = (-6)(22)B = 22 mod 49. Therefore -6B = 1 mod 49, and so B = 8 mod 49.

Taking this mod 71, we want 43*49A = 48A = 18 mod 71. Therefore, 8A = 3 mod 71. Since 8 has inverse 9 mod 71 this is A = 27 mod 71.

Therefore, x = 43*49*27 + 43*71*8 + 49*71*23 = 161330 mod (49*43*71). Then, since 43*49*71 = 149597, this is 11733 mod (149597).