Questions: Modular Arithmetic and Congruences

Question 1

You want the multiplicative inverse of 3 modulo 7 — a number x such that 3x ≡ 1 (mod 7). What is x?

• A. 2
• B. 3
• C. 5
• D. 6

Answer: (C)

3 × 5 = 15 = 2(7) + 1, so 15 ≡ 1 (mod 7), confirming x = 5. The inverse exists because gcd(3,7) = 1. You can verify the other options: 3×2 = 6 ≢ 1, 3×3 = 9 ≡ 2, 3×6 = 18 ≡ 4. Only 5 works.

Question 2

Since 4 ≡ 10 (mod 6) is true, dividing both sides by 2 gives the valid congruence 2 ≡ 5 (mod 6).

• T. True
• F. False

Answer: False

4 ≡ 10 (mod 6) is correct (both have remainder 4). But 2 ≢ 5 (mod 6) — their remainders differ. Division in modular arithmetic requires that gcd(divisor, modulus) = 1 for the modulus to stay the same; gcd(2,6) = 2 ≠ 1, so you cannot cancel 2 freely. This is one of the most common errors in modular arithmetic.

Question 3

Why does a multiplicative inverse of a modulo n exist if and only if gcd(a, n) = 1?

Model answer: We need ax ≡ 1 (mod n), i.e., n | (ax − 1), i.e., ax − ny = 1 for some integer y. By Bezout's theorem, integers x and y satisfying ax + ny = 1 exist exactly when gcd(a, n) = 1. If gcd(a, n) > 1, no such x exists because gcd(a,n) divides ax − ny but cannot divide 1.

Bezout's identity is the key: gcd(a,n) = 1 guarantees a linear combination ax + ny = 1 exists, which is precisely the condition that x is a modular inverse. The extended Euclidean algorithm finds this x efficiently.