Link:http://output.to/sideway/default.asp?qno=190300007

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