Advanced book on Mathematics Olympiad

Number Theory 713

and the problem is solved.

795.Consider first the casea=0. Sinceby=malways has solutions, it follows that
b=±1. From this we deduce thaty=±m. The second equation becomes a linear
equation inx,cx=n∓dm, which is supposed always to have an integer solution. This
impliesc=±1, and hencead−bc=bc=±1. The same argument applies if any of
b, c,ordis 0.
If none of them is zero, set =ab−cd. Again we distinguish two cases. If =0,
thenac=db=λ. Thenm=ax+by=λ(cx+dy)=λn, which restricts the range of
mandn. Hence =0.
Solving the system using Cramer’s rule, we obtain

x=

dm−bn

,y=

an−cm

.

These numbers are integers for anymandn. In particular, for(m, n)=( 1 , 0 ),x 1 = d,
y 1 =− c, and for(m, n)=( 0 , 1 ),x 2 =− b,y 2 = a. The number

x 1 y 2 −x 2 y 1 =

ad−bc

    2

=

1

is therefore an integer. Since is an integer, this can happen only if =±1, and the
problem is solved.

Remark.A linear mapT :R^2 →R^2 is called orientation preserving if its determinant
is positive, and orientation reversing otherwise. As a consequence of what we just
proved, we obtain that SL( 2 ,Z)consists of precisely those orientation-preserving linear
transformations of the plane that mapZ^2 onto itself.

796.Because gcd(a, b)=1, the equationau−bv=1 has infinitely many positive
solutions(u, v). Let(t, z)be a solution. Consider now the system in(x, y),

{

ax−yz−c= 0 ,

bx−yt+d= 0.

The determinant of its coefficient matrix is−1, so the system admits integer solutions.
Solving, we obtain

(

x

y

)

=

(

t−z

b−a

)(

c

−d

)

=

(

tc+zd

bc+ad

)

.

So each positive solution(t, z)to the equationau−bv=1 yields a positive solution
(tc+zd, bc+ad,z,t)to the original system of equations. This solves the problem.