Sideway from Sideway

Diophantine EquationClassical Diophantine EquationResource

Linear Diophantine Equation

Draft for Information Only


Classical Linear Diophantine Equation
 Linear Diophantine Equation
 Linear Bivariate Diophantine Equation
 Theorem A
  Proof of A.1
   Euclidean Algorithm
   Extended Euclidean Algorithm
    For example
  Proof of A.2
  Proof of A.3
 Theorem B
  Proof of B

Classical Linear Diophantine Equation

Source: An Introduction to Diophantine Equations - A Problem-Based Approach

Linear Diophantine Equation

A linear Diophantine equation is a first-degree equation of the form
where a₁, a₂, …, aₙ, c are fixed integers
in which n≥1 and coefficients a₁, a₂, …, aₙ are all different from zero.

Linear Bivariate Diophantine Equation

A linear bivariate Diophantine equation is a first-degree equation with two variables of the form
where a, b, c are fixed integers
in which coefficients a, b are all different from zero.

Theorem A

Let a, b, c be integers, a and b nonzero. Consider the linear Diophantine equation.

  1. The equation is solvable in integers if and only if d=gcd(a,b) divides c.
  2. If (x,y)=(x₀,y₀) is a particular solution to the equation, then every integer solution is of the form
    x=x₀+(b/d)t, y=y₀-(a/d)t where t is an integer.
  3. If c=gcd(a,b) and |a| or |b| is different from 1, then a particular solution (x,y)=(x₀,y₀) to (x₀+(b/d)t, y₀-(a/d)t) can be found such that |x₀|<|b| and |y₀|<|a|.

Proof of A.1

For ax+by=c
Since d=gcd(a,b), d divide a and b.

If d does not divide c then the equation is not solvable in integers since c/d is alway not an integer.

If d divides c then the equation is solvable in integers since c/d is alway an integer.

After dividing both sides of the equation by d/c,
the equation can then be solved by extended Euclidean algorithm.

Suppose u and v are two integers for which u>v and gcd(u,v)=d. From Euclidean algorithm, assume u=vq+r for integers u, v, q, and r.
If v|u, then gcd(u,v)=d=v and r=0.
If v∤u, then gcd(u,v)=d and r≠0.
In other words, r is always divided by d.

Euclidean Algorithm

Through Euclidean algorithm, a larger integer, u can be broken down into two parts, with one part is the multiple, q of the smaller integer, v and the other part is the remainder, r. Since the remainder is always less than the smaller integer and be divided by d also. Therefore the gcd of two integers, u and v can be determined by repeating the mechanism of Euclidean algorithm with v and r systematically until the remainder equals to 0.

  • u=vq₀+r₀; 0≤r₀<v
  • v=r₀q₁+r₁; 0≤r₁<r₀
  • r₀=r₁q₂+r₂; 0≤r₂<r₁
  • r₁=r₂q₃+r₃; 0≤r₃<r₂
  • rₙ₋₄=rₙ₋₃qₙ₋₂+rₙ₋₂; 0≤rₙ₋₂<rₙ₋₃
  • rₙ₋₃=rₙ₋₂qₙ₋₁+rₙ₋₁; 0≤rₙ₋₁<rₙ₋₂
  • rₙ₋₂=rₙ₋₁qₙ+rₙ where rₙ=0

The mechanism of Euclidean algorithm eventually terminates, since the remainders get smaller and smaller and end at zero. that is

 Since rₙ=0, rₙ₋₁ divides rₙ₋₂ , therefore Euclidean algorithm also assure that

Extended Euclidean Algorithm

The gcd(u,v) can then be determined through extended Euclidean algorithm as an integer combination of a and b. That is gcd(u,v)=ux+vy=d in which d is one of the remainders from Euclidean Algorithm. Rearranging equations from Euclidean Algorithm

  • r₀=u-vq₀⇒x₀=1, y₀=-q₀
  • r₁=v-r₀q₁=-r₀q₁+v=-(u-vq₀)q₁+v=-uq₁+vq₀q₁+v=-uq₁+v(1+q₀q₁)⇒x₁=-q₁, y₁=(1+q₀q₁)
  • r₂=r₀-r₁q₂=(u-vq₀)-(-uq₁+v(1+q₀q₁))q₂=u(1+q₁q₂)-v(q₀+(1+q₀q₁)q₂)⇒x₂=1+q₁q₂, y₂=-(q₀+(1+q₀q₁)q₂)
  • r₃=r₁-r₂q₃=(-uq₁+v(1+q₀q₁))-(u(1+q₁q₂)-v(q₀-(1+q₀q₁)q₂))q₃=-u(q₁-(1+q₁q₂))+v((1+q₀q₁)-(q₀-(1+q₀q₁)q₂))q₃) ⇒x₃=-(q₁+(1+q₁q₂)), y₃=((1+q₀q₁)-(q₀-(1+q₀q₁)q₂))q₃)
  • rₙ₋₁=rₙ₋₃-rₙ₋₂qₙ₋₁=gcd(u,v)
  • rₙ=rₙ₋₂-rₙ₋₁qₙ=0

Define the integers xₖ and yₖ recurively by

  • xₖ=xₖ₋₂-xₖ₋₁qₖ where x₋₂=1; x₋₁=0
  • yₖ=yₖ₋₂-yₖ₋₁qₖ where y₋₂=0; y₋₁=1

Therefore the variables xₖ and yₖ can be determined in terms of qₖ

  • x₀=x₋₂-x₋₁q₀=(1)-(0)q₀=1;  y₀=y₋₂-y₋₁q₀=(0)-(1)q₀=-q₀
  • x₁=x₋₁-x₀q₁=(0)-(1)q₁=-q₁;  y₁=y₋₁-y₀q₁=(1)-(-q₀)q₁=1+q₀q₁
  • x₂=x₀-x₁q₂=(1)-(-q₁)q₂=1+q₁q₂;  y₂=y₀-y₁q₂=(-q₀)-(1+q₀q₁)q₂=-q₀-(1+q₀q₁)q₂
  • x₃=x₁-x₂q₃=(-q₁)-(1+q₁q₂)q₃;  y₃=y₁-y₂q₃=(1+q₀q₁)-(q₀-(1+q₀q₁)q₂)q₃

The variables xₖ and yₖ are always opposite in sign and changed alternately. The remainder rₖ can therefore be calculated from the equation rₖ=uxₖ+vyₖ accordingly. That is

  • r₀=ux₀+vy₀
  • rₙ₋₁=uxₙ₋₁+vyₙ₋₁=gcd(u,v)
  • rₙ=uxₙ+vyₙ=0⇒u/v=-yₙ/xₙ

Assume u=(u/gcd(u,v)) and v=(v/gcd(u,v)). Then

  • r₀=(u/gcd(u,v))x₀+(v/gcd(u,v))y₀
  • rₙ₋₁=(u/gcd(u,v))xₙ₋₁+(v/gcd(u,v))yₙ₋₁=1
  • rₙ=(u/gcd(u,v))xₙ+(v/gcd(u,v))yₙ=0⇒(u/gcd(u,v))/(v/gcd(u,v))=-yₙ/xₙ

Therefore |xₙ|=v/gcd(u,v) and |yₙ|=u/gcd(u,v). In other words, |xₙ₋₁|<v and  |yₙ₋₁|<u are always true unless n=0 and q₀=1, that is unless u=v=1

  • u=vq₀+r₀⇒r₀=u-vq₀⇒x₀=1, y₀=-q₀

For example



Euclidean algorithm

  • u=vq₀+r₀; 0≤r₀<v⇒364=110*3+34⇒q₀=3, r₀=34
  • v=r₀q₁+r₁; 0≤r₁<r₀⇒110=34*3+8⇒q₁=3, r₁=8
  • r₀=r₁q₂+r₂; 0≤r₂<r₁⇒34=8*4+2⇒q₂=4, r₂=2
  • r₁=r₂q₃+r₃; 0≤r₃<r₂⇒8=2*4+0⇒q₃=4, r₃=0

Extended Euclidean algorithm

The variables xₖ and yₖ

  • x₀=1;  y₀=-q₀=-3
  • x₁=-q₁=-3;  y₁=1+q₀q₁=1+3(3)=10
  • x₂=1+q₁q₂=1+3(4)=13;  y₂=-q₀-(1+q₀q₁)q₂=-3-(1+3(3))4=-43
  • x₃=-q₁-(1+q₁q₂)q₃=-3-(1+3(4))4=-55;  y₃=(1+q₀q₁)-(q₀-(1+q₀q₁)q₂)q₃=(1+3(3))-(-3-(1+3(3))4)4=182

The equation of gcd(u,v)

  • r₀=ux₀+vy₀=364(1)+110(-3)=364-330=34
  • r₁=ux₁+vy₁=364(-3)+110(10)=-1092+1100=8
  • r₂=ux₂+vy₂=364(13)+110(-43)=4732-4730=2
  • r₃=ux₃+vy₃=364(-55)+110(182)=20020-20020=0

The solutions from equation of gcd(u,v)


Therefore solution to equation 364x+110y=46 is


Proof of A.2

Suppose f(x,y)=ax+by=c and gcd(a,b)=d

Since f(x,y)=c=ax+by⇒f(x₀,y₀)=ax₀+by₀=c

Add and subtract (ab/d)/t



Proof of A.3

If c=gcd(a,b) and |a| or |b| is different from 1, then a particular solution (x,y)=(x₀,y₀) to (x₀+(b/d)t, y₀-(a/d)t) can be found such that |x₀|<|b| and |y₀|<|a|.

From proof 1, the range of variables xₖ and yₖ are bounded such that, in general, |x₀|<|b| and |y₀|<|a|.


Since c=gcd(a,b)>0,

If rk:n=0=0, then either a|b or b|a.

If rk:n>0=0, then gcd(a,b)=c exists.


  • u=vq₀+r₀⇒r₀=u-vq₀⇒x₀=1, y₀=-q₀

 unless n=0 and q₀=1, that is unless u=v=1

Theorem B

The equation a₁x₁+a₂x₂+…+aₙxₙ=c where a₁, a₂, …, aₙ, c are fixed integers is solvable if and only if gcd(a₁, a₂, …, aₙ)|c

In case of solvability, one can choose n-1 solutions such that each solution is an integer linear combination of those n-1 solutions.

Proof of B

Let d= gcd(a₁, a₂, …, aₙ). If c is not divisible by d, then a₁x₁+a₂x₂+…+aₙxₙ=c is not solvable. Since the left hand side of equation is divisble by d, while the right hand side is not.



ID: 190300007 Last Updated: 7/3/2019 Revision: 0 Ref:



  1. B. Joseph, 1978, University Mathematics: A Textbook for Students of Science &amp; Engineering
  2. Wheatstone, C., 1854, On the Formation of Powers from Arithmetical Progressions
  3. Stroud, K.A., 2001, Engineering Mathematics
  4. Coolidge, J.L., 1949, The Story of The Binomial Theorem

Home 5






Hobbies 7


Chinese 1097

English 337

Reference 67


Hardware 149


Application 196

Digitization 25

Numeric 19


Web 622


CSS 58


OS 389

DeskTop 7



Formulas 8

Algebra 21

Number Theory 206

Trigonometry 18

Geometry 18

Calculus 67

Complex Analysis 21


Tables 8


Mechanics 1

Rigid Bodies

Statics 92

Dynamics 37

Fluid 5

Fluid Kinematics 5


Process Control 1

Acoustics 19

FiniteElement 2


Electric 23

Biology 1

Geography 1

Copyright © 2000-2020 Sideway . All rights reserved Disclaimers last modified on 06 September 2019