1st Course for high Diploma, Number Theory Lecture 4: The Diophantine Equation ax + by = c

3.1 The Diophantine Equation
The simplest type of Diophantine equation that we shall consider is the linear Diophantine equation in two unknowns:

ax+by =c
where a, b, c given integers and a, b are not both zero. A solution of this equation is a pair of integers x0, y0 that, when substituted into the equation, satisfy it; that is, we ask that ax0 +by0 =c.

A given linear Diophantine equation can have a number of solutions, as is the case with 3x +6y =18, where


3·4+6·1=18
3(?6)+6·6=18
3·10+6(?2)=18

By contrast, there is no solution to the equation 2x +10y =17. The left-hand side is an even integer whatever the choice of x and y, whereas the right-hand side is not.

The condition for solvability is easy to state: the linear 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 +by0 =c for suitable x0 and y0, then

c =ax0 +by0 =drx0 +dsy0 =d(rx0 +sy0)


which simply says that d|c. Conversely, assume that d|c, say c =dt. Using Theorem (), integers x0 and y0 can be found satisfying d =ax0 +by0. When

this relation 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. This proves in the next theorem.

Theorem 3.1.1. 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 and y = x0 –(a/d)t

where t is an arbitrary integer.

Proof. To establish 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 ).

By the corollary [If a|c and b|c, with gcd(a,b)=1, then ab|c.], there exist relatively prime integers r and s such that a =dr, b =ds.

Substituting these values into the last-written equation and canceling the common factor d, we ?nd that
r(x ? x0)=s(y0 – y ). (*)

The 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 Eq. (**) in Eq. (*), we obtain x ?x0 =st.

This leads us to the formulas

x = x0 +st = x0 +(b/d)t and y = y0 ?rt= y0 –(a/d)t.

It is easy to see that these values satisfy the Diophantine equation, regardless of the choice of the integer t; for

ax +by = a(x0 +(b/d)t)+b(y0 –(a/d)t
= (ax0 +by0)+(ab/ d – ab/ d)t
= c + 0·t =c.