66 CHAPTER 2 Discrete Mathematics
x = x 0 −b
dt, y=y 0 +a
dt, t∈Z (2.1)Finally, we see (by substituting into the equation) that the above ac-
tually is a solution; therefore we have determinedall solutions of the
given Diophantine equation. We summarize.
Theorem. Given the linear Diophantine equationax+by=cwhere
cis a multiple ofd= gcd(a,b), and given a particular solution(x 0 ,y 0 ),
the general solution is given by
x = x 0 −b
dt, y=y 0 +a
dt, t∈Z.Example. Consider the Diophantine equation 2x+ 3y= 48.
(i) Find all solutions of this equation.
(ii) Find allpositivesolutions, i.e., all solutions (x,y) withx, y >0.Solution. First of all, a particular solution can be found by simple
inspection: clearly (x,y) = (24,0) is a solution. Next, since 2 and 3 are
relatively prime we conclude from the above theorem that the general
solution is given by
x= 24− 3 t, y= 2t, t∈Z.Next, if we seek only positive solutions then clearlyt >0 and 24−t >0.
This reduces immediately to 0< t <24, which is equivalent with saying
that 1≤t≤23. That is, the positive solutions are described by writing
x= 24− 3 t, y= 2t, t∈Z, 1 ≤t≤ 23.Exercises
- Find all integer solutions of the Diophantine equation 4x+ 6y=
100. Also, find all positive solutions.