Questions: Bézout's Identity

Question 1

For which value of c does the equation 6x + 10y = c have integer solutions?

• A. c = 3
• B. c = 4
• C. c = 5
• D. c = 7

Answer: (B)

By Bézout's identity, ax + by = c has integer solutions if and only if gcd(a, b) divides c. Here gcd(6, 10) = 2. The only value among the options divisible by 2 is c = 4. For c = 3, 5, or 7, the equation has no integer solutions because 2 does not divide any of them. One explicit solution for c = 4: 6(4) + 10(−2) = 24 − 20 = 4, so x = 4, y = −2 works.

Question 2

The extended Euclidean algorithm gives gcd(35, 15) = 5 with Bézout coefficients x = 1, y = −2: 1·35 + (−2)·15 = 5. Which of the following is another valid pair of Bézout coefficients for the same gcd?

• A. (x = 4, y = −9)
• B. (x = 1, y = 2)
• C. (x = −1, y = 3)
• D. (x = 2, y = −4)

Answer: (A)

The general solution to 35x + 15y = 5 is x = 1 + (15/5)t = 1 + 3t, y = −2 − (35/5)t = −2 − 7t for any integer t. Setting t = 1 gives x = 4, y = −9. Check: 4·35 + (−9)·15 = 140 − 135 = 5 ✓. Option B: 35 + 30 = 65 ≠ 5. Option C: −35 + 45 = 10 ≠ 5. Option D: 70 − 60 = 10 ≠ 5.

Question 3

If gcd(a, b) = 1, then there exist integers x, y such that ax + by = 1, which means a has a multiplicative inverse modulo b.

• T. True
• F. False

Answer: True

When gcd(a, b) = 1, Bézout's identity guarantees ax + by = 1 for some integers x, y. Reducing modulo b: ax ≡ 1 (mod b), so x is the multiplicative inverse of a modulo b. This is exactly why modular inverses exist when and only when gcd(a, b) = 1 — and it underlies RSA encryption, the Chinese Remainder Theorem, and many other constructions.

Question 4

The integers x and y in Bézout's identity ax + by = gcd(a, b) are unique.

• T. True
• F. False

Answer: False

There are infinitely many pairs (x, y). If (x₀, y₀) is one solution, then (x₀ + (b/d)t, y₀ − (a/d)t) is also a solution for any integer t, where d = gcd(a, b). For example, both (1, −2) and (4, −9) satisfy 35x + 15y = 5. Uniqueness is a common misconception, perhaps because the extended Euclidean algorithm produces a specific pair — but that pair is just one representative from an infinite family.

Question 5

Why does Bézout's identity guarantee that ax + by = c has integer solutions if and only if gcd(a, b) divides c? Explain the 'if' direction.

Model answer: Bézout's identity gives integers x₀, y₀ with ax₀ + by₀ = gcd(a, b). If gcd(a, b) divides c, write c = gcd(a, b) · k for some integer k. Then a(x₀k) + b(y₀k) = gcd(a, b) · k = c, so (x₀k, y₀k) is an integer solution. The 'only if' direction is simpler: any integer linear combination ax + by is divisible by gcd(a, b), so if c is not divisible by gcd(a, b), no solution exists.

This characterization is fundamental because it turns a divisibility question into a linear algebra question. The set {ax + by : x, y ∈ ℤ} is exactly the set of multiples of gcd(a, b) — this is the ideal-theoretic statement that the ideal generated by a and b in ℤ equals the ideal generated by gcd(a, b). Bézout's identity is precisely what shows gcd(a, b) is achievable as a linear combination, making this ideal equality possible.