10. Linear Congruence Equations and Chinese Remainder Theorem

Try these first

1. 1.

   What does the notation a ≡ b (mod N) mean?

   Hint

   Think about the definition of congruence.

2. 2.

   If x ≡ 3 (mod 5), what could be a value of x?

   Hint

   Find such numbers by adding multiples of 5.

3. 3.

   What is the condition for using the extended Euclidean algorithm?

   • GCD(a
   • N) = 1
   • GCD(a
   • N) > 1
   • a and N are both 0

   Hint

   What condition does the existence of an inverse require?

4. 4.

   True or False: The Chinese Remainder Theorem guarantees a unique solution for any set of congruences.

   • True
   • False

   Hint

   Think about the conditions of the theorems discussed.

5. 5.

   Using the Chinese Remainder Theorem, solve for x in the system: x ≡ 1 (mod 4), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

   Hint

   Determine the product of moduli and work through the steps of CRT.

6. 6.

   Show that x ≡ 5 (mod 15) has infinitely many solutions, and list at least three.

   Hint

   Use the general formula for solutions in linear congruences.