A linear Diophantine equation is an equation of the form
where the coefficients and the constant are integers, and integer values are sought for the unknowns . It is a degree-one case of a Diophantine equation and a basic subject of number theory. Unlike a linear equation over the real or rational numbers, its solvability depends on divisibility. A single nontrivial linear Diophantine equation has an integer solution exactly when the greatest common divisor of its coefficients divides its constant term.
Definition and scope
The word linear means that each unknown occurs only to the first power, with no products between unknowns. For example,
is linear, whereas and are not.
The integer requirement is essential. An equation such as
has solutions over the rational numbers and the real numbers, but none over the integers: its left-hand side is always even.
Unless additional restrictions are stated, negative values and zero are allowed. Problems requiring nonnegative integer solutions, positive integer solutions, or solutions within specified bounds are more restrictive and need separate analysis.
A collection of linear Diophantine equations forms an integer system of linear equations, commonly written .
Solvability criterion
Suppose the coefficients are not all zero, and let
be their greatest common divisor. Then
has an integer solution if and only if
Necessity
Because divides every coefficient , it divides every integer linear combination
Consequently, an integer solution can exist only if divides .
Sufficiency
Bézout’s identity states that there are integers satisfying
If for an integer , multiplying this identity by gives a solution:
Equivalently, the integers representable by integer linear combinations of the coefficients are precisely the multiples of their greatest common divisor.
If all coefficients are zero, the equation reduces to . It then has every integer tuple as a solution when , and no solution when .
Equations in two unknowns
The classical two-variable equation is
Assume and are not both zero, and write
If , there are no integer solutions. If and is one solution, then all integer solutions are
Thus one particular solution determines the entire solution set.
Why the parameterization is complete
Suppose first that and are both nonzero. Subtracting the equation for from that for another solution gives
The integers and are relatively prime. Therefore divides , so
for an integer . Substitution gives the stated formula for . Conversely, direct substitution shows that every integer produces a solution.
If one coefficient is zero, the same parameterization remains valid: the unknown with nonzero coefficient is fixed, while the other is an arbitrary integer.
Example
Consider
Since and , solutions exist. The identity
gives the particular solution after multiplication by . Hence all solutions are
For instance, gives , while gives . In contrast,
has no integer solution because does not divide .
Computing solutions
The standard method uses the extended Euclidean algorithm. In addition to calculating , it finds integers such that
A solution procedure is:
Compute .
Test whether .
If so, take
Introduce an arbitrary integer parameter using the general solution formula.
The Euclidean algorithm uses a number of division steps logarithmic in the magnitude of the smaller nonzero input. Full bit complexity also depends on the cost of arithmetic on the integers involved.
For more than two coefficients, the algorithm can be applied repeatedly:
Keeping track of the corresponding identities produces a particular solution whenever the divisibility criterion is satisfied.
Connection with congruences
The equation
implies
when . Conversely, any integer satisfying this congruence yields an integer
Thus solving a two-variable linear Diophantine equation is closely related to solving a linear congruence in modular arithmetic.
For a positive modulus , the congruence
is solvable exactly when . If solvable, it has exactly distinct solution classes modulo .
In particular, when , Bézout’s identity supplies a multiplicative inverse of modulo . This connection also underlies constructive methods for the Chinese remainder theorem.
Nonnegative and bounded solutions
Integer solvability does not guarantee nonnegative integer solvability. For example,
satisfies the greatest-common-divisor criterion and has the solution , but it has no solution with both and .
When , inserting the two-variable parameterization into the nonnegativity constraints gives
Consequently,
If these endpoints are and , the number of nonnegative solutions is
For the example , the parameterization gives
Its only nonnegative solution is therefore . Additional upper or lower bounds on the unknowns can be handled by intersecting the resulting intervals for .
A related problem is the Frobenius coin problem. For relatively prime positive integers , the largest integer that cannot be expressed as
is
This result concerns nonnegative solutions; unrestricted integer solutions exist for every right-hand side when .
Several unknowns and lattice structure
For a single equation in unknowns with at least one nonzero coefficient, the solution set, when nonempty, has the form
where
The set is a lattice of rank . It has an integer basis , giving
Geometrically, the equation defines a hyperplane in real coordinate space, and the Diophantine problem asks which integer-coordinate points lie on it. For , every solvable nontrivial equation has infinitely many unrestricted integer solutions. Nonnegativity or boundedness constraints may reduce this set to finitely many points or eliminate it entirely.
The integer lattice basis is not interchangeable with an arbitrary rational basis of the real homogeneous solution space. Simply clearing denominators in a rational basis can produce vectors that generate only a proper sublattice of the integer solutions.
Systems and Smith normal form
For a system
where is an integer matrix, ordinary Gaussian elimination determines rational consistency but does not by itself characterize integer solvability.
A systematic integer method uses Smith normal form. There are unimodular integer matrices —integer matrices with determinant or —such that
where is diagonal in the rectangular-matrix sense. Its nonzero diagonal entries satisfy
with the rank of .
Setting
transforms the system into
Because and preserve integer coordinates bijectively, integer solvability is equivalent to
together with
for the remaining rows. The unconstrained coordinates of parameterize all solutions. For a single equation, the sole nonzero Smith invariant is the greatest common divisor of its coefficients.
Applications and computational limits
Linear Diophantine equations model exact balance conditions involving indivisible quantities: numbers of items in packages, denominations in payment problems, integer counts in resource allocation, and periodicity constraints.
They also form the equality constraints of many integer programming problems. Without inequalities or sign restrictions, solvability and parameterization admit systematic methods based on greatest common divisors and integer matrix reduction. Adding nonnegativity, capacity limits, or an optimization objective changes the problem substantially. Although the two-variable case remains directly manageable through its integer parameter, general integer programming can be computationally difficult.
The important distinction is between finding integer solutions to linear equalities and finding solutions that also belong to a prescribed feasible set. The greatest-common-divisor criterion completely resolves the former for one equation, but not the latter.