"Solve the system of congruences" solved and explained

Brennan Flores

Answered question

2021-02-03

Solve the system of congruences

Answer & Explanation

timbalemX

Skilled2021-02-04Added 108 answers

Step 1
Systems of linear congruences may be solved using methods from linear algebra: Matrix inversion, Cramer's rule. In case the modulus is prime, everything we know from linear algebra goes over to systems of linear congruences
Step 2
Consider the system of congruence
$x \equiv 1 (mod 3)$
$x \equiv 4 (mod 5)$
$x \equiv 6 (mod 7)$
Try a solution of the form
$x = 3 \cdot 5 \cdot a + 3 \cdot 7 \cdot b + 5 \cdot 7 \cdot c$
Taking the remainders mod 3,5, and 7. It gives the three equations
$1 \equiv 35 c \equiv 2 c \equiv - c (mod 3)$
$4 \equiv 21 b \equiv b (mod 5)$
$6 \equiv 15 a \equiv a (mod 7)$
$\Rightarrow a = 6, b = 4, c = - 1$
One solution is therefore
$x = 3 \cdot 5 \cdot 6 + 3 \cdot 7 \cdot 4 + 5 \cdot 7 \cdot (- 1) = 139 (\mod 105) = 34$

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school geometry

Didn't find what you were looking for?