Questions: Multiplicative Inverses in Modular Arithmetic

Question 1

Does 4 have a multiplicative inverse modulo 6?

• A. Yes — it is 2, since 4 · 2 = 8 ≡ 2 (mod 6)
• B. Yes — it is 4, since 4 · 4 = 16 ≡ 4 (mod 6)
• C. No — because gcd(4, 6) = 2 ≠ 1, so no inverse exists
• D. Yes — every nonzero residue has an inverse in any modular system

Answer: (C)

A multiplicative inverse of a mod n exists if and only if gcd(a, n) = 1. Here gcd(4, 6) = 2, so no integer b can satisfy 4b ≡ 1 (mod 6). The intuition: 4b is always even, and 1 is odd, so 4b − 1 is always odd and can never be divisible by 6. Option D is the classic misconception — it confuses modular arithmetic with fields like the real numbers where every nonzero element has an inverse.

Question 2

The extended Euclidean algorithm yields 3 · 5 + 7 · (−2) = 1. Using this, what is the solution to 3x ≡ 5 (mod 7)?

• A. x ≡ 2 (mod 7)
• B. x ≡ 4 (mod 7)
• C. x ≡ 5 (mod 7)
• D. x ≡ 6 (mod 7)

Answer: (B)

From the equation 3 · 5 + 7 · (−2) = 1, taking both sides mod 7 gives 3 · 5 ≡ 1 (mod 7), so 3⁻¹ ≡ 5 (mod 7). To solve 3x ≡ 5 (mod 7), multiply both sides by 3⁻¹ = 5: x ≡ 5 · 5 = 25 ≡ 4 (mod 7). Verification: 3 · 4 = 12 = 7 + 5 ≡ 5 (mod 7). ✓ A common error is to use s and t from Bézout's identity without carefully identifying which coefficient goes with which modulus.

Question 3

Most nonzero integer has a multiplicative inverse modulo any positive integer n.

• T. True
• F. False

Answer: False

This is false. The inverse of a mod n exists if and only if gcd(a, n) = 1. For example, 6 has no inverse mod 9, because gcd(6, 9) = 3 ≠ 1. An inverse exists for every nonzero element only when n is prime — then gcd(a, n) = 1 for all 1 ≤ a < n, giving every nonzero residue an inverse. This is one of the properties that makes prime moduli special in cryptography.

Question 4

If gcd(a, n) = 1, the extended Euclidean algorithm guarantees that integers s and t exist with as + nt = 1, and s is the multiplicative inverse of a modulo n.

• T. True
• F. False

Answer: True

This is Bézout's identity: whenever gcd(a, n) = 1, the extended Euclidean algorithm finds s and t satisfying as + nt = 1. Taking this equation mod n eliminates the nt term (since nt ≡ 0 mod n), leaving as ≡ 1 (mod n). So s is exactly the multiplicative inverse of a modulo n. The extended Euclidean algorithm is both the existence proof and the computation method.

Question 5

Explain why gcd(a, n) = 1 is necessary for a multiplicative inverse of a to exist modulo n.

Model answer: If gcd(a, n) = d > 1, then d divides both a and n. For any integer b, d also divides a · b (since d | a). But d does not divide 1. So a · b ≡ 1 (mod n) would require d | (a · b − 1), meaning d divides 1, a contradiction. Therefore no b can satisfy a · b ≡ 1 (mod n) when d > 1. When gcd(a, n) = 1, Bézout's identity guarantees the existence of such a b.

The core issue is divisibility: if a and n share a common factor d > 1, then every multiple of a shares that factor, and so a · b − 1 can never be divisible by d (let alone by n). The condition gcd = 1 eliminates this obstruction, and Bézout's identity then constructively provides the inverse.