These are problems asking for integer solutions to an equation ax+by=c with integer coefficients.
Condition for Solutions to Exist
ax+by=c has an integer solution ⟺ GCD(a,b) | c (c is a multiple of GCD(a,b))
How to Find Solutions
①First find a particular solution (x₀,y₀) to ax+by=1 using the Euclidean algorithm
②General solution: x = x₀ + (b/d)t、y = y₀ − (a/d)t （d=GCD(a,b)、t is an integer）
Example ①
Find one integer solution to 3x + 7y = 1. Also write the general solution.
7 = 3×2 + 1 → 1 = 7 − 3×2 → x₀=−2、y₀=1 is a particular solution
General solution: x = −2 + 7t、y = 1 − 3t （t is any integer）
Find one integer solution to 3x + 7y = 1. Also write the general solution.
7 = 3×2 + 1 → 1 = 7 − 3×2 → x₀=−2、y₀=1 is a particular solution
General solution: x = −2 + 7t、y = 1 − 3t （t is any integer）
Example ②
Find the general integer solution to 4x + 6y = 14.
GCD(4,6)=2、14÷2=7 → dividing both sides by 2 gives 2x+3y=7
3=2×1+1 → 1=3−2×1 → 2×(−1)+3×1=1 → 2×(−7)+3×7=7
Particular solution: x₀=−7、y₀=7
General solution: x = −7 + 3t、y = 7 − 2t （t is an integer）
Find the general integer solution to 4x + 6y = 14.
GCD(4,6)=2、14÷2=7 → dividing both sides by 2 gives 2x+3y=7
3=2×1+1 → 1=3−2×1 → 2×(−1)+3×1=1 → 2×(−7)+3×7=7
Particular solution: x₀=−7、y₀=7
General solution: x = −7 + 3t、y = 7 − 2t （t is an integer）
Key Points
- First check whether GCD(a,b) divides c
- Trace the Euclidean algorithm backward to find a particular solution
- The difference between general solutions is always a multiple of (b/d, −a/d)
- If positive integer solutions or a range is specified, restrict the range of t
Practice Problems
- Find one integer solution to 5x + 3y = 1 and write the general solution.
- Find the general integer solution to 7x − 4y = 3.
- Find all pairs of positive integers x, y satisfying 3x + 5y = 11.
Solutions and Explanations
- 5×2+3×(−3)=1 → particular solution x₀=2, y₀=−3. General solution: x=2+3t, y=−3−5t
- 7×1−4×1=3 → particular solution x₀=1, y₀=1. General solution: x=1+4t, y=1+7t (note the sign: for −4y, verify y=1−(−7)t) → x=1+4t, y=1+7t
- General solution x=2+5t, y=1−3t (from the particular solution:x₀=2,y₀=1). x>0, y>0 → 2+5t>0 and 1−3t>0 → t>−2/5 and t<1/3 → t=0 → (x,y)=(2,1)