Advanced book on Mathematics Olympiad

692 Number Theory

741.Note that ifdis a divisor ofn, then so isnd. So the sumsis given by

s=

∑k−^1

i= 1

didi+ 1 =n^2

∑k−^1

i= 1

1

didi+ 1

≤n^2

∑k−^1

i= 1

(

1

di

−

1

di+ 1

)

<

n^2

d 1

=n^2.

For the second part, note also thatd 2 =p,dk− 1 =pn, wherepis the least prime
divisor ofn.Ifn=p, thenk=2, ands=p, which dividesn^2 .Ifnis composite, then
k>2, andS>dk− 1 dk=n
2
p. If such answere a divisor ofn

(^2) , thenn^2
s would also be a
divisor ofn^2. But 1<n
2
s <p, which is impossible, becausepis the least prime divisor
ofn^2. Hence the given sum is a divisor ofn^2 if and only ifnis a prime.
(43rd International Mathematical Olympiad, 2002, proposed by M. Manea (Roma-
nia))
742.We look instead at composite odd positive numbers. Each such number can be
written as( 2 a+ 3 )( 2 b+ 3 ), foraandbnonnegative integers. In fact,nis composite if
and only if it can be written this way. We only need to write this product as a difference
of two squares. And indeed,
( 2 a+ 3 )( 2 b+ 3 )=(a+b+ 3 )^2 −(a−b)^2.
Thus we can choosef(a,b)=(a+b+ 3 )^2 andg(a, b)=(a−b)^2.
(Nea Marin) ̆
743.Arguing by contradiction, assume that there is somek,0≤k≤n−2, such that
k^2 +k+nis not prime. Choosesto be the smallest number with this property, and let
pbe the smallest prime divisor ofs^2 +s+n. First, let us notice thatpis rather small,
in the sense thatp≤ 2 s. For ifp≥ 2 s+1, then
s^2 +s+n≥p^2 ≥( 2 s+ 1 )^2 =s^2 +s+ 3 s^2 + 3 s+ 1 ≥s^2 +s+n+ 3 s+ 1

s^2 +s+n,
which is becauses>
√n
3. This is clearly impossible, which proves our claim.
It follows that eitherp=s−korp=s+k+1 for some 0≤k≤s−1. But then
for thisk,
s^2 +s+n−k^2 −k−n=(s−k)(s+k+ 1 ).
Becausepdividess^2 +s+nand the product(s−k)(s+k+ 1 ), it must also divide
k^2 +k+n. Now, this number cannot be equal top, becauses−k<n−k<k^2 +k+n
ands+k+ 1 <n− 1 +k+ 1 <k^2 +k+n. It follows that the numberk^2 +k+nis
composite, contradicting the minimality ofs. Hence the conclusion.
Remark.Euler noticed that 41 has the property thatk^2 +k+41 is a prime number for
all 0≤k≤39. Yet 40^2 + 40 + 41 = 412 is not prime!