Questions: Linear Diophantine Equations

Question 1

Does the equation 6x + 10y = 9 have integer solutions?

• A. Yes — all linear equations in two variables have solutions
• B. No — gcd(6, 10) = 2, which does not divide 9, so no integer solutions exist
• C. Yes — setting y = 0 gives x = 3/2, which can be rounded to the nearest integer
• D. No — because both 6 and 10 are even, no combination can produce an odd number

Answer: (B)

The solvability criterion: ax + by = c has integer solutions if and only if gcd(a, b) divides c. Here gcd(6, 10) = 2, and 2 does not divide 9 (since 9 is odd). Therefore no integers x, y can satisfy this equation. Option A is the common misconception — integer solutions are far more restricted than real solutions. Option C correctly finds a real solution but forgets we need integers. Option D gets the right answer for the wrong reason — the issue is divisibility of c by the gcd, not parity of the coefficients per se.

Question 2

The equation 4x + 6y = 10 has a particular solution x₀ = 1, y₀ = 1. Which expression gives ALL integer solutions?

• A. x = 1 + 4n, y = 1 − 6n for any integer n
• B. x = 1 + 3n, y = 1 − 2n for any integer n
• C. x = 1 + 6n, y = 1 − 4n for any integer n
• D. x = 1 + 2n, y = 1 − 3n for any integer n

Answer: (B)

With a = 4, b = 6, d = gcd(4, 6) = 2, the general solution is x = x₀ + (b/d)n = 1 + 3n and y = y₀ − (a/d)n = 1 − 2n. The step sizes are b/d = 3 and a/d = 2 (the reduced coefficients), not b and a themselves. Option A uses the original coefficients. Option C swaps them. Verify: 4(1+3n) + 6(1−2n) = 4 + 12n + 6 − 12n = 10. ✓

Question 3

If gcd(a, b) = 1, then the equation ax + by = c has integer solutions for every integer c.

• T. True
• F. False

Answer: True

When gcd(a, b) = 1, the divisibility condition 'gcd(a,b) | c' becomes '1 | c,' which holds for every integer c. By Bézout's identity, 1 can be expressed as ax₀ + by₀ for some integers x₀, y₀; scaling by c gives a(cx₀) + b(cy₀) = c. Coprime coefficients guarantee solvability for any right-hand side — no divisibility restriction on c exists.

Question 4

A linear Diophantine equation ax + by = c either has exactly one integer solution or no integer solution.

• T. True
• F. False

Answer: False

This is the most common misconception. When a solution exists, there are always infinitely many, parameterized by all integers n: x = x₀ + (b/d)n, y = y₀ − (a/d)n. Each value of n gives a distinct integer solution. The equation either has zero solutions (when gcd(a,b) ∤ c) or infinitely many (when gcd(a,b) | c).

Question 5

Why does the gcd of a and b determine whether ax + by = c has integer solutions?

Model answer: The set of all integers representable as ax + by, where x and y range over all integers, is exactly the set of multiples of gcd(a, b). By Bézout's identity, gcd(a, b) itself can be written as an integer linear combination of a and b, and every multiple of gcd(a, b) can be reached by scaling that combination. So if c is a multiple of d = gcd(a, b), scale the Bézout representation to get a solution. If c is not a multiple of d, no combination of integer multiples of a and b can sum to c, because every such sum is a multiple of d.

The structural fact is that {ax + by : x, y ∈ ℤ} = dℤ (the set of multiples of d). The solvability condition gcd(a,b) | c simply says c must belong to this set.