lineardiophantineequations

Linear Diophantine Equations

There exist solutions for x and y to the equation:

ax + by = c

if and only if d|c, where d=hcf (a,b)

Proof:

LEMMA 1

ax + by = hcf (a,b) always has solution for x and y

Proof:

Consider the set S of all positive linear combinations of a and b

S must contain (since clearly not empty) a smallest element, d = ax + by

a=qd + r [Lemma 2][0<=r<d]

r=a - qd

=a - q(ax + by)

=a(1 - qx) + b(-qy)

Therefore r=0 (else d is not the smallest element in S)

a=qd, or d|a

Similarly, d|b, so d is a common factor of a and b

But, if c is an arbitrary common factor of a and b, c|(ax + by) => c|d => d=hcf (a,b)

LEMMA 2

Given integers a and b [b>0], a=qb + r [0<=r<b]

Conversely:

If a=dr and b=ds [d=hcf (a,b)]

c=ax + by=drx + dsy=d(rx + sy) => d|c