724 Number Theory
For arbitraryq, from what we have proved so far it follows thataq≡± 1 (mod 2t−m).
Becauseφ( 2 t−m)= 2 t−m−^1 , by Euler’s theorema^2
t−m− 1
≡ 1 (mod 2t−m). Sinceqis odd,
we can find a positive integercsuch thatcq≡ 1 (mod 2t−m−^1 ). Thena ≡acq ≡
(± 1 )c≡± 1 (mod 2t−m), and the lemma is proved.
Let us return to the problem. Letx = 2 mq, wherem≥1 andqis odd. Because
(v+ 1 )x−vy=1, clearlyy≥x. We have shown thatv+1 dividesy,soy≥v+1. Let
us prove thaty≥ 2 m+1. Indeed, ifm≤2 this holds sincey≥v+ 1 ≥ 5 ≥ 2 m+1;
otherwise,y≥x= 2 mq≥ 2 m≥ 2 m+1.
Looking at the equation modulo 2y, we have(v+ 1 )^2
mq
≡ 1 (mod 2y), because 2y
dividesvy. By the lemma this implies thatv+ 1 ≡± 1 (mod 2y−m). Butv+ 1 ≡
1 (mod 2y−m)would imply that 2m+^1 dividesv, which is impossible sincevdividesx.
Therefore,v+ 1 ≡− 1 (mod 2y−m)andv≡− 2 (mod 2y−m). In particular,v≥ 2 y−m−2,
soy≥ 2 y−m−1. But sincey≥ 2 m+1 andy≥5, it follows that 2y−m− 1 >y,a
contradiction. This shows that there are no other solutions.
Second solution: Begin as before until we reduce to the caseu=v+1 andv≥3. Then
we use the following lemma.
Lemma.Supposeps ≥ 3 is a prime power,r ≥ 1 ,anda ≡ 1 (modps),but not
modps+^1 .Ifak≡ 1 (modpr+s),thenprdividesk.
Proof.Writea= 1 +cps+dps+^1 , where 1≤c≤p−1. Then we computeak≡
1 +kcps(modps+^1 ), and
ap= 1 +cps+^1 +dps+^2 +(
p
2)
p^2 s(c+dp)+(
p
3)
p^3 s(c+dp)^3 +···.Since eithers ≥ 2orpis odd,ps+^2 divides
(p
2)
p^2 s; hence the fourth term is zero
modps+^2. Sinces+ 2 ≤ 3 s, the latter terms are also zero modps+^2 ; henceap ≡
1 (modps+^1 ), but not modps+^2.
We now proceed by induction onr. Sincer ≥1, the first equation above shows
thatpdividesk, which is the base case. For the inductive step, we note that the second
calculation above lets us apply the previous case to(ap)k/p.
To use this lemma, letps≥3 be the highest power of the primepthat dividesv.
Thenu=v+ 1 ≡ 1 (modps), but not modps+^1 , andux=vy+ 1 ≡ 1 (modpsy).
Hence by the lemma,ps(y−^1 )dividesx, and in particular,x ≥ps(y−^1 )≥ 3 y−^1. Thus
eitherx>yory=1.
Similarly, letqt ≥ 3 be the highest power of the primeqthat dividesu. Then
(−v) = 1 −u ≡ 1 (modqt), but not modqt+^1. Since(−v)y ≡ 1 (modqt) and
(−v)y=(− 1 )y−(− 1 )yux≡(− 1 )y(modqt), we see thatyis even. Hence(−v)y=
1 −ux≡ 1 (modqtx). Thus by the lemma,qt(x−^1 )dividesy, and in particular,y≥
qt(x−^1 )≥ 3 x−^1 , so eithery>xorx=1.