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)\)

By using addition property,

\(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.

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)\)

By using addition property,

\(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.