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