10.3. Chinese Remainder Theorem (CRT)

Try these first

1. 1.

   What is a linear congruence? Provide an example.

   Hint

   Look for the standard form.

2. 2.

   How many solutions does the linear congruence 4x ≡ 8 (mod 12) have?

   Hint

   Consider all values that satisfy the equation.

3. 3.

   What is a linear congruence?

   Hint

   Think of modular arithmetic.

4. 4.

   True or False: The Chinese Remainder Theorem guarantees multiple solutions for all systems of linear congruences.

   • True
   • False

   Hint

   Recall the uniqueness condition.

5. 5.

   Find all integer solutions for the system: x ≡ 1 (mod 4), x ≡ 3 (mod 5), and x ≡ 2 (mod 7).

   Hint

   Start with calculating the larger modulus.

6. 6.

   Determine the implications of changing one modulus in a set of congruences. For instance, replace mod 5 with mod 6.

   Hint

   Evaluate how congruences relate to divisibility.