**Diophantine equation**: Any linear equation in two variables having integral coefficient can be put in the form

ax + by = c ——————————–(i)

where a, b, c are given integers. We consider the problem of identifying all solutions of two equation in which x and y are integers. If a = b = c = 0 then every pair (x, y) of integers is a solution of (i), where if a = b = 0.

**Condition for solvability**: The Diophantine equation ax + by + c admits a solution if and only if d\c, where d = gcd(a, b). We know that there are integers r and s for which a = dr and b = ds. If a solution of ax + by = c exists , so that ax_{0} + by_{o} = c for suitable x_{0} and y_{o}, then

c = ax_{0} + by_{o} = dr x_{0} + ds_{0} = d(rx_{0} + sy_{0}), which simply says that d\c.

Conversely assume that d\c, say c = dt. Since d = gcd(a, b) there exist integers x_{0} and y_{0} satisfying d = ax_{0} + b + by_{o}.

When this relativity is multiplied by t, we get

c = dt = (ax_{0} + by_{0})t = a (tx_{0}) + b(ty_{0})

Hence the Diophantine equation ax + by = c has x = tx_{0} and y = ty_{0} as a particular solution.

**Theorem:** The linear Diophantine equation ax + by = c has a solution if and only if d\c, where d = gcd(a, b). If x_{0}, y_{0} is any particular solution of this equation, then all other solutions are given by

x = x_{0} + (b/d)t

y = y_{0} – (a/d)t

Where t is an arbitrary integer.

**Proof:** To established the second assertion of the theorem, let us suppose that a solution x_{0}, y_{0} of the given equation is known. If xʹ, yʹ is any other solution, then ax_{0} + by_{0} = c = axʹ + byʹ; which is equivalent to

a(xʹ – x_{0}) = b(y_{0} – yʹ)

Since d = gcd(a, b), there exist relatively prime integers r and s such that a = dr, b = ds. Substituting these values into the last written equation and cancelling the common factor d, we find that

r(xʹ – x_{0}) = s(y_{0} – yʹ)

This situation is now this: r\s(y_{0}-yʹ), with gcd(r, s) =1.

Using Euclid’s lemma, it must be the case that r\(y_{0}-yʹ); or, in other words, y_{0} – yʹ = rt for some integer t. Substituting, we obtain

xʹ – x_{0} = st

This leads us to the formulas

xʹ = x_{0} + st = x_{0} + (b/d)t

yʹ = y_{0} – rt = y_{0} – (a/d)t

It is easy to see that these values satisfying the Diophantine equation regardless of the choice of the integers; for

axʹ + byʹ = a[x_{0} + (b/d)t] + b[y_{0} – (a/d)t] = (ax_{0} + by_{0}) + (ab/d – ab/d) = c + t.0 = c

Thus there are an infinite number of solutions of the given equation, one for each value of t.