Advanced High-School Mathematics

SECTION 2.1 Elementary Number Theory 65

2.1.2 The linear Diophantine equationax+by=c

Suppose thata, b, care integers and suppose that we wish to find all
possible solutions of thelinear Diophantine equationax+by=c.
First of all we need a condition on a, b, c in order to guarantee the
existence of a solution.

Theorem.The linear Diophantine equationax+by=chas a solution
if and onlygcd(a,b)|c.

Proof. Setd= gcd(a,b) and assume that c=kdfor some integerk.
Apply the Euclidean trick to find integers sand t with sa+tb = d;
multiply through byk and geta(sk) +b(tk) =kd=c. A solution is
therefore x= sk and y = tk. Conversely, assume thatax+by = c.
Then sinced|aandd|b, we see thatd|(ax+by), i.e.,d|c, proving the
theorem.

As the above indicates, applying the Euclidean algorithm will yield
a solution of the Diophantine equationax+by=c. We would like now
to show how to obtain thegeneral solutionof this equation, that is to
find a recipe for generating all possible solutions. Let’s start with a fixed
solution (x 0 ,y 0 ) and let (x,y) be another solution. This immediately
implies thatax 0 +by 0 =c, ax+by=cand soa(x 0 −x) =b(y−y 0 ).
Settingd= gcd(a,b) we have

a

d

(x 0 −x) =

b

d

(y−y 0 ).

Next, we note that since

a

d

and

b

d

are relatively prime, then by

Exercise 7 on page 61 we have that

a

d

dividesy−y 0 , sayy−y 0 =

a

d

tfor

some integert. But then
a
d

(x 0 −x) =

b

d

·

a

d

t, forcingx 0 −x=

b

d

t. In

other words, starting with a fixed solution (x 0 ,y 0 ) of the Diophantine
equationax+by=cwe know that any other solution (x,y) must have
the form