Question: Solve the system of linear congruences below by finding all x that satisfy it. Hint — try rewriting each congruence in the form x≡a(mod b).2x≡1(mod 3)3x≡2(mod 5)5x≡4(mod 7)So I tried following that hint, and I have:x≡2(mod 3)x≡4(mod 5)x≡5(mod 7)Firstly, is this correct? Second, where do I go from here? I calculated that M=3×5×7=105 and the individual Mi's, but now I'm stuck in a circle, because reducing from there gives me back the original equations. Any tips?

Question

Question: Solve the system of linear congruences below by finding all x that satisfy it. Hint — try rewriting each congruence in the form x≡a(mod b).2x≡1(mod 3)3x≡2(mod 5)5x≡4(mod 7)So I tried following that hint, and I have:x≡2(mod 3)x≡4(mod 5)x≡5(mod 7)Firstly, is this correct? Second, where do I go from here? I calculated that M=3×5×7=105 and the individual Mi&#039;s, but now I&#039;m stuck in a circle, because reducing from there gives me back the original equations. Any tips?

Yosef Krause · Accepted Answer

from the first both equations we get  32(1+3m)=2+5n  or  9m−10n=1  solving this Diophantine equation we get  m=9+10C  n=8+9C  with this two equations you can calculate x

Zernerqcw · Accepted Answer

Using the Extended Euclidean Algorithm, one implementation can be found in this answer, we can solve the three equations  3x+35y=1=12⋅3−1⋅35  5x+21y=1=−4⋅5+1⋅21  7x+15y=1=−2⋅7+1⋅15  which gives the equations  −35≡1(mod 3)  −35≡0(mod 5)  −35≡0(mod 7)  and  21≡0(mod 3)  21≡1(mod 5)  21≡0(mod 7)  and  15≡0(mod 3)  15≡0(mod 5)  15≡1(mod 7)  Adding 2 times (1) to 4 times (2) and 5 times (3) should give an answer mod 105.

Question: Solve the system of linear congruences below by finding all x that satisfy it. Hint — try

Answered question

Answer & Explanation

New Questions in Algebra I