678 Number Theory
710.Assume that the property does not hold, and fixa. Only finitely many numbers of
the formf(a+k)can be less thana, so we can choosersuch thatf(a+nr) > f (a)
for alln. By our assumptionf(a+ 2 m+^1 r)<f(a+ 2 mr)for allm, for otherwiseaand
d= 2 mrwould satisfy the desired property. We have constructed an infinite descending
sequence of positive integers, a contradiction. Hence the conclusion.
(British Mathematical Olympiad, 2003)
711.We will apply Fermat’s infinite descent method to the prime factors ofn.
Letp 1 be a prime divisor ofn, andqthe smallest positive integer for whichp 1 divides
2 q−1. From Fermat’s little theorem it follows thatp 1 also divides 2p^1 −^1 −1. Hence
q≤p 1 − 1 <p 1.
Let us prove thatqdividesn. If not, letn=kq+r, where 0<r<q. Then
2 n− 1 = 2 kq· 2 r− 1 =( 2 q)k· 2 r− 1 =( 2 q− 1 + 1 )k· 2 r− 1=∑kj= 1(
k
j)
( 2 q− 1 )j· 2 r− 1 ≡ 2 r− 1 (modp 1 ).It follows thatp 1 divides 2r−1, contradicting the minimality ofq. Henceqdividesn,
and 1<q<p 1. Letp 2 be a prime divisor ofq. Thenp 2 is also a divisor ofn, and
p 2 <p 1. Repeating the argument, we construct an infinite sequence of prime divisors
ofn,p 1 >p 2 >···,which is impossible. Hence the conclusion.
(1st W.L. Putnam Mathematical Competition, 1939)
712.The divisibility condition can be written as
k(ab+a+b)=a^2 +b^2 + 1 ,wherekis a positive integer. The small values ofkare easy to solve. For example,k= 1
yieldsab+a+b=a^2 +b^2 +1, which is equivalent to(a−b)^2 +(a− 1 )^2 +(b− 1 )^2 =0,
whose only solution isa=b=1. Also, fork=2 we have 2ab+ 2 a+ 2 b=a^2 +b^2 +1.
This can be rewritten either as 4a=(b−a− 1 )^2 or as 4b=(b−a+ 1 )^2 , showing that both
aandbare perfect squares. Assuming thata≤b, we see that(b−a− 1 )−(b−a+ 1 )=2,
and henceaandbare consecutive squares. We obtain as an infinite family of solutions
the pairs of consecutive perfect squares.
Now let us examine the casek≥3. This is where we apply Fermat’s infinite descent
method. Again we assume thata≤b. A standard approach is to interpret the divisibility
condition as a quadratic equation inb:
b^2 −k(a+ 1 )b+(a^2 −ka+ 1 )= 0.Because one of the roots, namelyb, is an integer, the other root must be an integer, too
(the sum of the roots isk(a+ 1 )). Thus we may substitute the pair(a, b)by the smaller
pair(r, a), provided that 0<r<a.