Question

# Solve the system of congruence's xequiv1(mod 3), xequiv 4(mod 5), xequiv6(mod 7)

Congruence
Solve the system of congruence's $$x\equiv1(mod\ 3), x\equiv 4(mod\ 5), x\equiv6(mod\ 7)$$

2021-02-01
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*5*a+3*7*b+5*7*c$$
Taking the remainders mod 3, 5, and 7. It gives the three equations
$$1 \equiv 35 c \equiv 2c \equiv -c(mod\ 3)$$
$$4 \equiv 21b \equiv b(mod\ 5)$$
$$6 \equiv 15 \equiv a(mod\ 7)$$
$$\Rightarrow a=6,b=4,c=-1$$
One solution is therefore
$$x=3*5*6+3*7*+5*7*(—1) = 139(mod\ 105) = 34$$