Questions: The Euclidean Algorithm and Greatest Common Divisor

Question 1

Why does gcd(a, b) = gcd(b, a mod b)? What justifies this reduction step?

• A. Because dividing a by b produces the same quotient as dividing a mod b by b
• B. Because every common divisor of a and b also divides a mod b, and vice versa — so the set of common divisors is identical
• C. Because the Euclidean algorithm defines gcd this way, without deeper mathematical justification
• D. Because a mod b is always smaller than b, which guarantees the algorithm terminates

Answer: (B)

The key insight is that if d divides both a and b, then d divides a − qb = a mod b (since a mod b is a linear combination of a and b). Conversely, if d divides both b and a mod b, it divides a = qb + (a mod b). So the set of common divisors is identical for (a, b) and (b, a mod b), meaning their GCD must be the same. Option D is true but explains only termination, not correctness — the two are distinct questions.

Question 2

If gcd(a, n) = 3, does a have a multiplicative inverse modulo n?

• A. Yes — any nonzero number has a multiplicative inverse modulo any n
• B. No — a multiplicative inverse of a modulo n exists only when gcd(a, n) = 1
• C. Yes — because 3 divides both a and n, they share structure that enables an inverse
• D. No — but only because n must be composite in this case

Answer: (B)

A multiplicative inverse of a modulo n exists if and only if gcd(a, n) = 1. Bézout's identity gives ax + ny = gcd(a, n). For a modular inverse we need ax ≡ 1 (mod n), which requires gcd(a, n) = 1. If gcd(a, n) = 3, then ax + ny is always a multiple of 3 and can never equal 1 — no inverse exists. This is why RSA and other cryptographic systems require choosing values coprime to the modulus.

Question 3

The extended Euclidean algorithm computes not just gcd(a, b) but also integers x and y such that ax + by = gcd(a, b). Its primary practical application is computing multiplicative inverses modulo n.

• T. True
• F. False

Answer: True

Bézout's identity guarantees that ax + by = gcd(a, b). When gcd(a, n) = 1, this gives ax + ny = 1, so ax ≡ 1 (mod n) — meaning x is the multiplicative inverse of a modulo n. The extended Euclidean algorithm computes this inverse in O(log n) time. This is the core subroutine inside the Chinese Remainder Theorem and RSA, making the extended algorithm indispensable in number-theoretic cryptography.

Question 4

A naive algorithm for gcd(a, b) lists most divisors of both numbers and finds the largest shared one. The Euclidean algorithm is faster primarily because it checks fewer divisor pairs.

• T. True
• F. False

Answer: False

The Euclidean algorithm is faster because it achieves O(log(min(a, b))) time through repeated reduction — not by searching fewer divisors. Each step replaces the pair (a, b) with (b, a mod b), strictly shrinking the problem. In the worst case (consecutive Fibonacci numbers), the size roughly halves every two steps. For numbers with hundreds of digits, this is the difference between instant computation and impossibly slow enumeration. The algorithm avoids factoring entirely.

Question 5

Using the Euclidean algorithm, compute gcd(91, 35). Show your steps.

Model answer: gcd(91, 35): 91 = 2·35 + 21, so gcd(91, 35) = gcd(35, 21). 35 = 1·21 + 14, so gcd(35, 21) = gcd(21, 14). 21 = 1·14 + 7, so gcd(21, 14) = gcd(14, 7). 14 = 2·7 + 0, so gcd(14, 7) = gcd(7, 0) = 7. Answer: gcd(91, 35) = 7.

Each step applies gcd(a, b) → gcd(b, a mod b) until the remainder is zero. The last nonzero remainder is the GCD. Four steps suffice here because the numbers are small; for numbers with hundreds of digits the same structure applies, still completing in logarithmic time.