Advanced book on Mathematics Olympiad

5.3 Diophantine Equations 271

Proof.For the equation to have solutions it is clearly necessary thatcbe divisible by
gcd(a, b). Dividing through by gcd(a, b)we can assume thataandbare coprime.
To show that the equation has solutions, we first examine the casec=1. The method
of solving this equation is a consequence of Euclid’s algorithm for finding the greatest
common divisor. This algorithm consists of a successive series of divisions

a=q 1 b+r 1 ,

b=q 2 r 1 +r 2 ,

r 1 =q 3 r 2 +r 3 ,

···

rn− 2 =qnrn− 1 +rn,

wherernis the greatest common divisor ofaandb, which in our case is 1. If we work
backward, we obtain

1 =rn− 1 (−qn)−(−rn− 2 )=rn− 2 ( 1 −qn− 1 )−rn− 3 qn= ··· =ax 0 −by 0

for whatever numbersx 0 andy 0 arise at the last stage. This yields a particular solution
(x 0 ,y 0 ).
For a generalc, just multiply this solution byc.If(x 1 ,y 1 )is another solution, then
by subtractingax 0 −by 0 =cfromax 1 −by 1 =c, we obtaina(x 1 −x 0 )−b(y 1 −y 0 )=0,
hencex 1 −x 0 =gcd(a,b)b t, andy 1 −y 0 =gcda(a,b)tfor some integer numbert. This shows

that the general solution is of the form(x 0 +gcd(a,b)b t,y 0 +gcda(a,b)t),tan integer. The
theorem is proved. 

The algorithm for finding a particular solution can be better visualized if we use the
continued fraction expansion

a

b

=−a 1 +

1

−a 2 +

1

−a 3 +···+

1

−an− 1 +

1

−an

.

In this, if we delete −^1 an, we obtain a simpler fraction, and this fraction is nothing
butyx^00.
The equalityax−by=1 shows that the matrix with integer entries
(
ay
bx

)