Question

# Solve the following systems of congruences. xequiv 4(mod 5) xequiv 3(mod 8) xequiv 2(mod 3)

Congruence
Solve the following systems of congruences.
$$x\equiv 4(mod\ 5)$$
$$x\equiv 3(mod\ 8)$$
$$x\equiv 2(mod\ 3)$$

2021-02-22
Formula used:
1) Theorem: System of congruences:
Let m and n be relatively prime and a and b integers. There exists an integer x that satisfies the system of congruences
$$x\equiv (mod\ m)$$
$$x \equiv b(mod\ n)$$
Furthermore, any two solutions x and y are congruent modulo mn.
2) Theorem: Addition and Multiplication Properties:
If $$a = b(mod\ n)$$ and x is any integer, then $$a + x \equiv b + x(mod\ n)\ and\ ax \equiv bx (mod\ n)$$.
3) Theorem: Cancellation Law:
If $$ax \equiv ay (mod\ n)\ and\ (a, n) = 1,\ then\ x \equiv y(mod\ n)$$.
Explanation:
Consider the system of congruences
$$x \equiv 4(mod\ 5)$$
$$x \equiv 2(mod\ 3)$$
Since 5 and 3 are relatively prime, then $$(5, 3) = 1$$.
Then, by using theorem there exists an integer x that satisfies the system of congruences.
From the first congruence $$x = 4 + 5k$$ for some integer k and substitute this expression for x into the second congruence.
$$4 + 5k \equiv 2 (mod\ 3)$$
$$4+5k + (—4) \equiv 2+(—4)(mod\ 3)$$
$$\Rightarrow 5k =—2(mod\ 3)$$
Since $$5 \equiv 2(mod\ 3)$$,
$$\Rightarrow 2k \equiv -2(mod\ 3)$$
Since $$(2, 3) = 1$$ then by using cancellation law,
$$\Rightarrow k\equiv -1(mod\ 3)$$
Now, $$-1 \equiv 2(mod\ 3)$$,
Therefore, $$k = 2 (mod\ 3)$$
Thus, $$x = 4 + 5(2) = 14$$ satisfies the system and $$x = 14 (mod\ 5 * 3)$$ or $$x = 14 (mod\ 15)$$ gives all solutions to the given system of congruences.