10.10. Summary of Today's Lecture

Try these first

1. 1.

   What is the solution for the linear congruence 4x ≡ 2 (mod 6)?

   Hint

   Use the concept of divisibility in modular arithmetic.

2. 2.

   How do you express solutions for 3x ≡ 1 (mod 8)?

   Hint

   Find an integer such that `3 * ? ≡ 1 (mod 8)`.

3. 3.

   What is the general solution format for 6x ≡ 4 (mod 10)?

   • x = 4 + 10k
   • x = 5 + 10k
   • x = 3 + 10k

   Hint

   Think about how the solution can be expressed with `k` integer.

4. 4.

   True or False: The Extended Euclidean Algorithm can be applied if gcd(a, N) is greater than 1.

   • True
   • False

   Hint

   Recall the conditions for the applicability of this algorithm.

5. 5.

   Solve the following system using the Chinese Remainder Theorem: x ≡ 4 (mod 5), x ≡ 1 (mod 3), x ≡ 2 (mod 7). Provide full steps in your reasoning.

   Hint

   Start by calculating the product of moduli.

6. 6.

   Employ the Extended Euclidean Algorithm to find the multiplicative inverse of 7 mod 26. Show your steps.

   Hint

   Remember the last non-zero remainder should give you the gcd proof.