output.to from Sideway
Algebra

Diophantine EquationClassical Diophantine EquationResource

Linear Diophantine Equation

Draft for Information Only

# Content

```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
a₁x₁+a₂x₂+…+aₙxₙ=c
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
ax+by=c
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.
ax+by=c

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.
⇒(ax+by)/d=c/d⇒(a/d)x+(b/d)y=c/d

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,
⇒(ax+by)/(c/d)=c/(c/d)⇒a(dx/c)+b(dy/c)=d⇒a(x/c)+b(y/c)=1
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.
⇒u/d=(vq+r)/d⇒u/d=(v/d)q+r/d⇒gcd(u,v)=gcd(v,r)=d
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
v>r₀>r₁>r₂>r₃>…>rₙ₋₄>rₙ₋₃>rₙ₋₂>rₙ₋₁>rₙ=0

Since rₙ=0, rₙ₋₁ divides rₙ₋₂ , therefore Euclidean algorithm also assure that
d=gcd(u,v)=gcd(v,r₀)=gcd(r₀,r₁)=gcd(r₁,r₂)=…=gcd(rₙ₋₄,rₙ₋₃)=gcd(rₙ₋₃,rₙ₋₂)=gcd(rₙ₋₂,rₙ₋₁)=rₙ₋₁

#### 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

364x+110y=46

gcd(182*2,55*2)=gcd(364,110)=2

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)

364(13)+110(-43)=2
⇒364(13)(23)+110(-43)(23)=2(23)
⇒364(299)+110(-989)=46
⇒108836-108790=46

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

(x,y)=(299,-989)
⇒(x,y)=(299+110t/2,-989-364t/2)=(299+55t,-989-182t)

### 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

⇒f(x₀,y₀)=ax₀+(ab/d)/t-(ab/d)/t+by₀=c

⇒f(x₀,y₀)=a(x₀+(b/d)/t)+b(y₀-(ab/d)/t)=c

### 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|.

1=|x₀|<|x₁|<|x₂|<|x₃|<…<|xₙ₋₂|<|xₙ₋₁|<|xₙ|=|v/gcd(u,v)|
|q₀|=|y₀|<|y₁|<|y₂|<|y₃|<…<|yₙ₋₂|<|yₙ₋₁|<|yₙ|=|u/gcd(u,v)|

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.

Besides,since

• 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.
a₁x₁+a₂x₂+…+aₙxₙ=c
⇒(a₁x₁+a₂x₂+…+aₙxₙ)/d=c/d
⇒(a₁/d)x₁+(a₂/d)x₂+…+(aₙ/d)xₙ=c/d

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

References

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

Management

HBR 3

Information

Recreation

Culture

Chinese 1097

English 337

Computer

Hardware 149

Software

Application 196

Numeric 19

Programming

Web 622

HTML 65

CSS 58

ASP.NET 62

OS 389

Knowledge

Mathematics

Algebra 21

Geometry 18

Calculus 67

Engineering

Mechanical

Rigid Bodies

Statics 92

Dynamics 37

Control

Physics

Electric 23