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

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 \equiv a (mod b)

.

2 x \equiv 1 (mod 3)

3 x \equiv 2 (mod 5)

5 x \equiv 4 (mod 7)

So I tried following that hint, and I have:

x \equiv 2 (mod 3)

x \equiv 4 (mod 5)

x \equiv 5 (mod 7)

Firstly, is this correct? Second, where do I go from here? I calculated that

M = 3 \times 5 \times 7 = 105

and the individual

M_{i}

's, but now I'm stuck in a circle, because reducing from there gives me back the original equations. Any tips?

Answer 1

from the first both equations we get

\frac{3}{2} (1 + 3 m) = 2 + 5 n

or

9 m - 10 n = 1

solving this Diophantine equation we get

m = 9 + 10 C

n = 8 + 9 C

with this two equations you can calculate x

Answer 2

Using the Extended Euclidean Algorithm, one implementation can be found in this answer, we can solve the three equations

3 x + 35 y = 1 = 12 \cdot 3 - 1 \cdot 35

5 x + 21 y = 1 = - 4 \cdot 5 + 1 \cdot 21

7 x + 15 y = 1 = - 2 \cdot 7 + 1 \cdot 15

which gives the equations

- 35 \equiv 1 (mod 3)

- 35 \equiv 0 (mod 5)

- 35 \equiv 0 (mod 7)

and

21 \equiv 0 (mod 3)

21 \equiv 1 (mod 5)

21 \equiv 0 (mod 7)

and

15 \equiv 0 (mod 3)

15 \equiv 0 (mod 5)

15 \equiv 1 (mod 7)

Adding 2 times (1) to 4 times (2) and 5 times (3) should give an answer mod 105.

Expert Answer