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 a(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 = y(mod\ n)\).

Explanation:

Consider \(3x + 2 \equiv 3 (mod\ 8)\)

By using addition property,

\(3x +2 + (-2) \equiv 3 + (—2) (mod\ 8)\)

\(\Rightarrow 3x \equiv 1 (mod\ 8)\)

By using multiplication property,

\(\Rightarrow 3*3x=1*3(mod\ 8)\)

\(Rightarrow\ 9x \equiv 3 (mod\ 8)\)

Since \(9 \equiv 1 (mod\ 8)\),

\(\Rightarrow x \equiv 3(mod\ 8)\)

Therefore, the system of congruences is

\(x \equiv 4 (mod\ 7)\)

\(x \equiv 3(mod\ 8)\)

Since 7 and 8 are relatively prime then \((7, 8) = 1\).

Then, by using theorem there exists an integer x that satisfies the system of congruences.

From the first congruence \(x = 4 + 7k\) for some integer k and substitute this expression for x into the second congruence.

\(4+ 7k \equiv 3 (mod\ 8)\)

By using addition property,

\(4+7k + (—4) \equiv 3+ (—4) (mod\ 8)\)

\(\Rightarrow 7k \equiv —1(mod\ 8)\)

Since \(— 1 \equiv 7(mod\ 8)\),

\(\Rightarrow 7k \equiv 7 (mod\ 8)\)

Since (7, 8) = I then by using cancellation law,

\(\Rightarrow k \equiv 1 (mod\ 8)\)

Thus, \(x = 4 + 7(1) = 11\) satisfies the system and \(x = 11 (mod\ 7 * 8)\ or\ x \equiv 11 (mod\ 56)\) 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 a(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 = y(mod\ n)\).

Explanation:

Consider \(3x + 2 \equiv 3 (mod\ 8)\)

By using addition property,

\(3x +2 + (-2) \equiv 3 + (—2) (mod\ 8)\)

\(\Rightarrow 3x \equiv 1 (mod\ 8)\)

By using multiplication property,

\(\Rightarrow 3*3x=1*3(mod\ 8)\)

\(Rightarrow\ 9x \equiv 3 (mod\ 8)\)

Since \(9 \equiv 1 (mod\ 8)\),

\(\Rightarrow x \equiv 3(mod\ 8)\)

Therefore, the system of congruences is

\(x \equiv 4 (mod\ 7)\)

\(x \equiv 3(mod\ 8)\)

Since 7 and 8 are relatively prime then \((7, 8) = 1\).

Then, by using theorem there exists an integer x that satisfies the system of congruences.

From the first congruence \(x = 4 + 7k\) for some integer k and substitute this expression for x into the second congruence.

\(4+ 7k \equiv 3 (mod\ 8)\)

By using addition property,

\(4+7k + (—4) \equiv 3+ (—4) (mod\ 8)\)

\(\Rightarrow 7k \equiv —1(mod\ 8)\)

Since \(— 1 \equiv 7(mod\ 8)\),

\(\Rightarrow 7k \equiv 7 (mod\ 8)\)

Since (7, 8) = I then by using cancellation law,

\(\Rightarrow k \equiv 1 (mod\ 8)\)

Thus, \(x = 4 + 7(1) = 11\) satisfies the system and \(x = 11 (mod\ 7 * 8)\ or\ x \equiv 11 (mod\ 56)\) gives all solutions to the given system of congruences.