Advanced book on Mathematics Olympiad

5.3 Diophantine Equations 273

795.Leta, b, c, dbe integers with the property that for any two integersmandnthere
exist integersxandysatisfying the system
ax+by=m,
cx+dy=n.
Prove thatad−bc=±1.

796.Leta, b, c, dbe positive integers with gcd(a, b)=1. Prove that the system of
equations
{
ax−yz−c= 0 ,
bx−yt+d= 0

has infinitely many solutions in positive integers(x,y,z,t).
We now ask for the nonnegative solutions to the equationax+by=c, wherea, b, c
are positive numbers. This is a particular case, solved by Sylvester, of the Frobenius
coin problem: what is the largest amount of money that cannot be paid using coins worth
a 1 ,a 2 ,...,ancents? Here is the answer.

Sylvester’s theorem.Letaandbbe coprime positive integers. Thenab−a−bis the
largest positive integercfor which the equation

ax+by=c

is not solvable in nonnegative integers.

Proof.LetN>ab−a−b. The integer solutions to the equationax+by=Nare of the
form(x, y)=(x 0 +bt, y 0 −at), withtan integer. Choosetsuch that 0≤y 0 −at≤a−1.
Then

(x 0 +bt)a=N−(y 0 −at)b > ab−a−b−(a− 1 )b=−a,

which implies thatx 0 +bt >−1, and sox 0 +bt≥0. Hence in this case the equation
ax+by=Nadmits nonnegative integer solutions.
On the other hand, if there existedx, y≥0 such that
ax+by=ab−a−b,

then we would haveab=a(x+ 1 )+b(y+ 1 ). Sinceaandbare coprime, this would
imply thatadividesy+1 andbdividesx+1. But theny+ 1 ≥aandx+ 1 ≥b, which
would then lead to the contradiction

ab=a(x+ 1 )+b(y+ 1 )≥ 2 ab.

This proves the theorem.