Sideway
output.to from Sideway
Algebra



Classical Diophantine Equation


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

Add and subtract (ab/d)/t

⇒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

 


©sideway
close

References

  1. B. Joseph, 1978, University Mathematics: A Textbook for Students of Science & Engineering, Blackie & Son Limited, HongKong
  2. Wheatstone, C., 1854, On the Formation of Powers from Arithmetical Progressions, Proceedings of The Royal Society of London, Vol 7, p145-151,, London
  3. Stroud, K.A., 2001, Engineering Mathematics, Industrial Press, Inc, NY
  4. Coolidge, J.L., 1949, The Story of The Binomial Theorem, The American Mathematical Monthly, Vol 56, No.3, Mar, pp147-157
close

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

IMAGE

Home (5)

Business

Management

HBR (3)

Information

Recreation

Hobbies (7)

Culture

Chinese (1097)

English (336)

Reference (66)

Computer

Hardware (149)

Software

Application (187)

Digitization (24)

Numeric (19)

Programming

Web (602)new

CSS (SC)

ASP.NET (SC)new

HTML

Knowledge Base

Common Color (SC)

Html Entity (Unicode) (SC)

Html 401 Special (SC)

OS (373)new

MS Windows

Windows10 (SC)

.NET Framework (SC)new

DeskTop (6)

Knowledge

Mathematics

Formulas (8)

Number Theory (206)

Algebra (20)

Trigonometry (18)

Geometry (18)

Calculus (67)

Complex Analysis (21)

Engineering

Tables (8)

Mechanical

Mechanics (1)

Rigid Bodies

Statics (92)

Dynamics (37)

Fluid (5)

Fluid Kinematics (5)

Control

Process Control (1)

Acoustics (19)

FiniteElement (2)

Biology (1)

Geography (1)

Latest Updated Links

Copyright © 2000-2019 Sideway . All rights reserved Disclaimers last modified on 10 Feb 2019