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 ax0 + byo = c for suitable x0 and yo, then
c = ax0 + byo = dr x0 + ds0 = d(rx0 + sy0), which simply says that d\c.
Conversely assume that d\c, say c = dt. Since d = gcd(a, b) there exist integers x0 and y0 satisfying d = ax0 + b + byo.
When this relativity is multiplied by t, we get
c = dt = (ax0 + by0)t = a (tx0) + b(ty0)
Hence the Diophantine equation ax + by = c has x = tx0 and y = ty0 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 x0, y0 is any particular solution of this equation, then all other solutions are given by
x = x0 + (b/d)t
y = y0 – (a/d)t
Where t is an arbitrary integer.
Proof: To established the second assertion of the theorem, let us suppose that a solution x0, y0 of the given equation is known. If xʹ, yʹ is any other solution, then ax0 + by0 = c = axʹ + byʹ; which is equivalent to
a(xʹ – x0) = b(y0 – 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ʹ – x0) = s(y0 – yʹ)
This situation is now this: r\s(y0-yʹ), with gcd(r, s) =1.
Using Euclid’s lemma, it must be the case that r\(y0-yʹ); or, in other words, y0 – yʹ = rt for some integer t. Substituting, we obtain
xʹ – x0 = st
This leads us to the formulas
xʹ = x0 + st = x0 + (b/d)t
yʹ = y0 – rt = y0 – (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[x0 + (b/d)t] + b[y0 – (a/d)t] = (ax0 + by0) + (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.