Linear Diophantine equations are among the most fundamental equations studied in elementary number theory. Their standard two-variable form is ax + by = c, where a, b, and c are fixed integers and x and y are unknown integers. The central solvability condition is gcd(a, b) | c. If the greatest common divisor of the coefficients does not divide the constant term, no integer solution exists. If it does divide the constant term, infinitely many integer solutions exist, provided a and b are not both zero. The extended Euclidean algorithm can be used to find one particular solution. Once a particular solution (x₀, y₀) is known, all integer solutions can be expressed using a parameter t. If d = gcd(a, b), the general solution is x = x₀ + (b/d)t and y = y₀ − (a/d)t, where t is any integer. This formula describes every integer solution without requiring individual trial-and-error calculations.
Linear Diophantine Equations
A linear Diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers and the unknowns x and y must also be integers. It has an integer solution if and only if the greatest common divisor of a and b divides c.
ax + by = c has integer solutions ⇔ gcd(a, b) | c
Explanation
Variables
A
The integer coefficient of x.
B
The integer coefficient of y.
C
The integer constant on the right-hand side.
X, y
The unknown integer variables.
D
The greatest common divisor gcd(a, b).
T
An arbitrary integer parameter used to describe all solutions.
X₀, y₀
One particular integer solution.
Example or application
Problem
Solve 6x + 9y = 30 in integers.
Solution
First, gcd(6, 9) = 3, and 3 divides 30, so integer solutions exist. Divide the equation by 3 to obtain 2x + 3y = 10. One particular solution is x₀ = 2 and y₀ = 2, because 2(2) + 3(2) = 10. Since the reduced coefficients are 2 and 3, all solutions are x = 2 + 3t and y = 2 − 2t, where t is any integer.
Answer
x = 2 + 3t, y = 2 − 2t, where t ∈ ℤ.
Text
The greatest common divisor determines whether a linear Diophantine equation is solvable. When a solution exists, the extended Euclidean algorithm provides a systematic way to find one solution, and a parameter formula generates all the remaining integer solutions.
Key Points
The standard form is ax + by = c.
All coefficients and unknowns are integers.
An integer solution exists if and only if gcd(a, b) divides c.
If the solvability condition fails, no integer solution exists.
If a and b are not both zero and a solution exists, there are infinitely many integer solutions.
The extended Euclidean algorithm can produce a particular solution.
A parameter formula describes all integer solutions.
Properties
If d = gcd(a, b), then d divides every integer combination ax + by.
When d divides c, dividing the equation by d produces an equivalent equation with relatively prime coefficients.
For a reduced equation with relatively prime coefficients, all solutions differ by integer multiples of the coefficient pair.
The general solution contains one free integer parameter.
Additional restrictions, such as x > 0 and y > 0, may reduce the infinite solution set to a finite one.
Methods
| Name | Description |
|---|---|
Greatest Common Divisor Test | Calculate gcd(a, b) and check whether it divides c. This determines whether integer solutions are possible. |
Extended Euclidean Algorithm | Find integers u and v satisfying au + bv = gcd(a, b), then multiply by c divided by the greatest common divisor. |
General Solution Formula | Use a particular solution and an integer parameter to generate every integer solution. |
Applications
Solving whole-number allocation problems.
Representing a target quantity as a combination of fixed integer quantities.
Studying divisibility and linear combinations of integers.
Solving problems involving coin denominations and exact totals.
Understanding the mathematical basis of modular equations.
Learning Outcomes
Recognize a linear Diophantine equation.
Apply the greatest common divisor solvability condition.
Find a particular integer solution using the extended Euclidean algorithm.
Write the general solution of a two-variable linear Diophantine equation.
Apply additional restrictions to identify valid solutions.
Practice Questions
Determine whether 8x + 12y = 18 has integer solutions.
Solve 5x + 7y = 1 in integers.
Find all integer solutions of 4x + 6y = 14.
Use the extended Euclidean algorithm to solve 15x + 21y = 12.
Explain why gcd(a, b) must divide c for ax + by = c to have an integer solution.
How do positive-integer restrictions affect the general solution?
Related Concepts
Greatest Common Divisor
Extended Euclidean Algorithm
Bézout's Identity
Linear Congruences
Integer Solutions and Constraints
Common Mistakes
Checking whether a or b individually divides c instead of checking gcd(a, b).
Using the Euclidean algorithm without finding the corresponding coefficients.
Forgetting to multiply a particular solution by c divided by the greatest common divisor.
Giving only one solution instead of the general solution.
Using a real parameter instead of restricting the parameter to integers.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- David M. Burton, Elementary Number Theory
- Kenneth H. Rosen, Elementary Number Theory and Its Applications
- Titu Andreescu and Dorin Andrica, An Introduction to Diophantine Equations
Suggest a correction or source · More in Arithmetic & Number Theory