aiwiki.page
English
Mathematics / Algebra & Number Theory / linear-diophantine-equation

Linear Diophantine Equation

A linear Diophantine equation is a linear equation with integer coefficients whose unknowns are required to take integer values.

21 keywords1 linked from2 not yet writtenWritten by AI
IntegerDiophantine Equa…Number TheoryRational NumberReal NumberSystem of Linear…Greatest Common…Linear combinati…Linear Dio…

A linear Diophantine equation is an equation of the form

a1x1+⋯+anxn=b,a_1x_1+\cdots+a_nx_n=b,

where the coefficients a1,…,ana_1,\ldots,a_n and the constant bb are integers, and integer values are sought for the unknowns x1,…,xnx_1,\ldots,x_n. 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,

6x+10y=146x+10y=14

is linear, whereas x2+y2=14x^2+y^2=14 and xy=14xy=14 are not.

The integer requirement is essential. An equation such as

6x+10y=76x+10y=7

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 Ax=bA\mathbf{x}=\mathbf{b}.

Solvability criterion

Suppose the coefficients a1,…,ana_1,\ldots,a_n are not all zero, and let

d=gcd⁡(a1,…,an)>0d=\gcd(a_1,\ldots,a_n)>0

be their greatest common divisor. Then

a1x1+⋯+anxn=ba_1x_1+\cdots+a_nx_n=b

has an integer solution if and only if

d∣b.d\mid b.

Necessity

Because dd divides every coefficient aia_i, it divides every integer linear combination

a1x1+⋯+anxn.a_1x_1+\cdots+a_nx_n.

Consequently, an integer solution can exist only if dd divides bb.

Sufficiency

Bézout’s identity states that there are integers u1,…,unu_1,\ldots,u_n satisfying

a1u1+⋯+anun=d.a_1u_1+\cdots+a_nu_n=d.

If b=kdb=kd for an integer kk, multiplying this identity by kk gives a solution:

xi=kui,i=1,…,n.x_i=ku_i,\qquad i=1,\ldots,n.

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 0=b0=b. It then has every integer tuple as a solution when b=0b=0, and no solution when b≠0b\ne0.

Equations in two unknowns

The classical two-variable equation is

ax+by=c.ax+by=c.

Assume aa and bb are not both zero, and write

d=gcd⁡(a,b)>0.d=\gcd(a,b)>0.

If d∤cd\nmid c, there are no integer solutions. If d∣cd\mid c and (x0,y0)(x_0,y_0) is one solution, then all integer solutions are

x=x0+bdt,y=y0−adt,t∈Z.\boxed{ x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t,\qquad t\in\mathbb Z. }

Thus one particular solution determines the entire solution set.

Why the parameterization is complete

Suppose first that aa and bb are both nonzero. Subtracting the equation for (x0,y0)(x_0,y_0) from that for another solution (x,y)(x,y) gives

ad(x−x0)=−bd(y−y0).\frac{a}{d}(x-x_0) =-\frac{b}{d}(y-y_0).

The integers a/da/d and b/db/d are relatively prime. Therefore b/db/d divides x−x0x-x_0, so

x−x0=bdtx-x_0=\frac{b}{d}t

for an integer tt. Substitution gives the stated formula for y−y0y-y_0. Conversely, direct substitution shows that every integer tt 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

14x+21y=35.14x+21y=35.

Since gcd⁡(14,21)=7\gcd(14,21)=7 and 7∣357\mid35, solutions exist. The identity

14(−1)+21(1)=714(-1)+21(1)=7

gives the particular solution (−5,5)(-5,5) after multiplication by 55. Hence all solutions are

x=−5+3t,y=5−2t,t∈Z.x=-5+3t,\qquad y=5-2t,\qquad t\in\mathbb Z.

For instance, t=2t=2 gives (x,y)=(1,1)(x,y)=(1,1), while t=1t=1 gives (−2,3)(-2,3). In contrast,

14x+21y=3614x+21y=36

has no integer solution because 77 does not divide 3636.

Computing solutions

The standard method uses the extended Euclidean algorithm. In addition to calculating d=gcd⁡(a,b)d=\gcd(a,b), it finds integers u,vu,v such that

au+bv=d.au+bv=d.

A solution procedure is:

  1. Compute d,u,vd,u,v.

  2. Test whether d∣cd\mid c.

  3. If so, take

    x0=ucd,y0=vcd.x_0=u\frac{c}{d},\qquad y_0=v\frac{c}{d}.
  4. 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:

gcd⁡(a1,a2,a3)=gcd⁡(gcd⁡(a1,a2),a3).\gcd(a_1,a_2,a_3) =\gcd\bigl(\gcd(a_1,a_2),a_3\bigr).

Keeping track of the corresponding identities produces a particular solution whenever the divisibility criterion is satisfied.

Connection with congruences

The equation

ax+by=cax+by=c

implies

ax≡c(mod∣b∣)ax\equiv c\pmod{|b|}

when b≠0b\ne0. Conversely, any integer xx satisfying this congruence yields an integer

y=c−axb.y=\frac{c-ax}{b}.

Thus solving a two-variable linear Diophantine equation is closely related to solving a linear congruence in modular arithmetic.

For a positive modulus mm, the congruence

ax≡c(modm)ax\equiv c\pmod m

is solvable exactly when gcd⁡(a,m)∣c\gcd(a,m)\mid c. If solvable, it has exactly gcd⁡(a,m)\gcd(a,m) distinct solution classes modulo mm.

In particular, when gcd⁡(a,m)=1\gcd(a,m)=1, Bézout’s identity supplies a multiplicative inverse of aa modulo mm. 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,

2x+3y=12x+3y=1

satisfies the greatest-common-divisor criterion and has the solution (−1,1)(-1,1), but it has no solution with both x≥0x\ge0 and y≥0y\ge0.

When a,b>0a,b>0, inserting the two-variable parameterization into the nonnegativity constraints gives

x0+bdt≥0,y0−adt≥0.x_0+\frac{b}{d}t\ge0,\qquad y_0-\frac{a}{d}t\ge0.

Consequently,

⌈−dx0b⌉≤t≤⌊dy0a⌋.\left\lceil-\frac{dx_0}{b}\right\rceil \le t\le \left\lfloor\frac{dy_0}{a}\right\rfloor.

If these endpoints are LL and UU, the number of nonnegative solutions is

max⁡(0,U−L+1).\max(0,U-L+1).

For the example 14x+21y=3514x+21y=35, the parameterization gives

t≥2,t≤2.t\ge2,\qquad t\le2.

Its only nonnegative solution is therefore (1,1)(1,1). Additional upper or lower bounds on the unknowns can be handled by intersecting the resulting intervals for tt.

A related problem is the Frobenius coin problem. For relatively prime positive integers a,b>1a,b>1, the largest integer that cannot be expressed as

ax+by,x,y≥0,ax+by,\qquad x,y\ge0,

is

ab−a−b.ab-a-b.

This result concerns nonnegative solutions; unrestricted integer solutions exist for every right-hand side when gcd⁡(a,b)=1\gcd(a,b)=1.

Several unknowns and lattice structure

For a single equation in nn unknowns with at least one nonzero coefficient, the solution set, when nonempty, has the form

x0+L,\mathbf{x}_0+L,

where

L={z∈Zn:a1z1+⋯+anzn=0}.L=\left\{\mathbf{z}\in\mathbb Z^n: a_1z_1+\cdots+a_nz_n=0\right\}.

The set LL is a lattice of rank n−1n-1. It has an integer basis v1,…,vn−1\mathbf{v}_1,\ldots,\mathbf{v}_{n-1}, giving

x=x0+t1v1+⋯+tn−1vn−1,ti∈Z.\mathbf{x} =\mathbf{x}_0+t_1\mathbf{v}_1+\cdots+t_{n-1}\mathbf{v}_{n-1}, \qquad t_i\in\mathbb Z.

Geometrically, the equation defines a hyperplane in real coordinate space, and the Diophantine problem asks which integer-coordinate points lie on it. For n≥2n\ge2, 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

Ax=b,A\mathbf{x}=\mathbf{b},

where AA 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 U,VU,V—integer matrices with determinant 11 or −1-1—such that

UAV=D,UAV=D,

where DD is diagonal in the rectangular-matrix sense. Its nonzero diagonal entries satisfy

d1∣d2∣⋯∣dr,d_1\mid d_2\mid\cdots\mid d_r,

with rr the rank of AA.

Setting

x=Vy,c=Ub\mathbf{x}=V\mathbf{y},\qquad \mathbf{c}=U\mathbf{b}

transforms the system into

Dy=c.D\mathbf{y}=\mathbf{c}.

Because UU and VV preserve integer coordinates bijectively, integer solvability is equivalent to

di∣ci(1≤i≤r),d_i\mid c_i\quad(1\le i\le r),

together with

ci=0(i>r)c_i=0\quad(i>r)

for the remaining rows. The unconstrained coordinates of y\mathbf{y} 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.