10.7. Construction of the Solution x

Try these first

1. 1.

   What is the solution for x in 5x ≡ 15 (mod 10)?

   Hint

   Check numbers that give a remainder of 5 when multiplied by 5.

2. 2.

   If 3x ≡ 6 (mod 9), what are possible values for x?

   Hint

   Look for x that, when multiplied by 3, gives a remainder of 6.

3. 3.

   What method do we use to solve ax ≡ b (mod N) confidently?

   • A. Simple division
   • B. Extended Euclid's Algorithm
   • C. Graphical method

   Hint

   Think about which method guarantees the necessary inverse.

4. 4.

   True or false: The Chinese Remainder Theorem guarantees a unique solution to every set of congruences.

   • True
   • False

   Hint

   Consider the conditions of the theorem.

5. 5.

   Solve the system of congruences using CRT:

   • x ≡ 1 (mod 5)
   • x ≡ 4 (mod 7)
   • x ≡ 6 (mod 11).

   Hint

   Think through each modulus contributions, expressing them individually.

6. 6.

   Prove that if ax ≡ b (mod N) can be solved, then gcd(a, N) divides b.

   Hint

   Consider the implications of solutions to mod forms.