Advanced book on Mathematics Olympiad

Number Theory 723

820.First solution: The solutions are

(v+ 1 ,v, 1 , 1 ),for allv; ( 2 , 1 , 1 ,y),for ally; ( 2 , 3 , 2 , 1 ), ( 3 , 2 , 2 , 3 ).

To show that these are the only solutions, we consider first the simpler casev =

u+1. Thenux−(u+ 1 )y =1. Considering this equation modulou, we obtain

− 1 ≡ux−(u+ 1 )y = 1 (modu).Sou =1 or 2. The caseu =1 is clearly

impossible, since thenvy=0, so we haveu=2,v=3. We are left with the simpler

equation 2x− 3 y =1. Modulo 3 it follows thatx is even,x = 2 x′. The equality

22 x

′

− 1 =( 2 x

′

− 1 )( 2 x

′

+ 1 )= 3 ycan hold only ifx′=1 (the only consecutive powers

of 3 that differ by 2 are 1 and 3). Sox=2,y=1, and we obtain the solution( 2 , 3 , 2 , 1 ).

Now suppose thatu=v+1. Ifv=1, thenu=2,x=1, andyis arbitrary. So we

have found the solution( 2 , 1 , 2 ,y).Ifv=2, the equation reduces to 3x− 2 y=1. If

y≥2, then modulo 4 we obtain thatxis even,x= 2 x′, and so 3^2 x

′

− 1 =( 3 x

′

− 1 )( 3 x

′

+

1 )= 2 y. Two consecutive powers of 2 differ by 2 if they are 2 and 4. We find that either

x=y=1orx= 2 ,y=3. This gives the solutions( 2 , 1 , 1 , 1 )and( 3 , 2 , 2 , 3 ).

So let us assumev ≥3. The casey =1 gives the solutions(v+ 1 ,v, 1 , 1 ).If

y>1, thenv^2 dividesvy,so1≡(v+ 1 )x≡ 0 +

(x

1

)

v+ 1 (modv^2 ), and therefore

vdividesx. Considering the equation modulov+1, we obtain 1≡(v+ 1 )x−vy≡

−(− 1 )y(mod(v+ 1 )). Sincev+ 1 >2, 1 ≡− 1 (mod(v+ 1 )),soymust be odd. Now

ifx=1, thenvy=v,sov=1, giving again the family of solutions(v+ 1 ,v, 1 , 1 ).So

assumex>1. Then(v+ 1 )^2 divides(v+ 1 )x,so

1 ≡(v+ 1 )x−vy≡−(v+ 1 − 1 )y

≡ 0 −

(

y

1

)

(v+ 1 )(− 1 )y−^1 −(− 1 )y

≡−y(v+ 1 )+ 1 (mod(v+ 1 )^2 ).

Hencev+1 dividesy. Sinceyis odd,v+1 is odd andvis even. Sincevdividesx,

xis also even. Becausevis even andv≥3, it follows thatv≥4. We will need the

following result.

Lemma.Ifaandqare odd, if 1 ≤m<t, and ifa^2

mq

≡ 1 (mod 2t), thena ≡

± 1 (mod 2t−m).

Proof.First, let us prove the property forq =1. We will do it by induction onm.
Form=1 we havea^2 =(a− 1 )(a+ 1 ), so one of the factors is divisible by 2t−^1.
Assume that the property is true form−1 and let us prove it form. Factoring, we obtain
(a^2
m− 1

• 1 )(a^2
  m− 1
  − 1 ). Form≥2, the first factor is 2 modulo 4, hencea^2
  m− 1
  is 1
  modulo 2t−^1. From the induction hypothesis it follows thata≡± 1 (mod 2t−m)(note
  thatt−m=(t− 1 )−(m− 1 )).