Advanced book on Mathematics Olympiad

Number Theory 683

As before, we deduce that 2 m+^1 b= 2 m+^1 b+ba. Again this is an impossibility. Hence
the only possibility is that 2 m+^1 a= 2 m+^1 aand by a similar argument 2 m+^1 b=
2 m+^1 b. This completes the induction.
From 2 ma= 2 maand 2 mb= 2 mbwe deduce that the fractional parts ofa
andbare less than 21 m. Takingm→∞, we conclude thataandbare integers.
(short list of the 39th International Mathematical Olympiad, 1998)
720.Ignoring the “brackets’’ we have

p

q

+

2 p

q

+···+

(q− 1 )p

q

=

(q− 1 )p

2

.

The difference betweenkp/qandkp/qisr/q, whereris the remainder obtained on

dividingkpbyq. Sincepandqare coprime,p, 2 p,...,(q− 1 )pform a complete set

of residues moduloq. So fork= 1 , 2 ,...,q−1, the numbersk/p−kp/qare a

permutation of 1, 2 ,...,q−1. Therefore,

∑q−^1

k= 1

⌊

kp

q

⌋

=

q∑− 1

k= 1

kp

q

−

∑q−^1

k= 1

k

q

=

(q− 1 )p

2

−

q− 1

2

=

(p− 1 )(q− 1 )

2

,

and the reciprocity law follows.

721.The function

f(x)=nx−

x

1

−

 2 x

2

−

 3 x

3

−···−

nx

n

satisfiesf(x)=f(x+ 1 )for allxandf( 0 )=0. Moreover, the function is constant

on subintervals of[ 0 , 1 )that do not contain numbers of the formp/q,2≤q≤nand

1 ≤p≤q−1. Thus it suffices to verify the inequality forx=p/q, wherepandqare

coprime positive integers, 2≤q≤n,1≤p≤q−1. Subtracting the inequality from

x=

x

1

+

2 x

2

+···+

nx

n

,

we obtain the equivalent inequality for the fractional part{·}({x}=x−x),

{nx}≤

{x}

1

+

{ 2 x}

2

+

{ 3 x}

3

+···+

{nx}

n

,

which we prove for the particular values ofxmentioned above. Ifrkis the remainder

obtained on dividingkpbyq, then{kx}=rqk, and so the inequality can be written as

rn

q

≤

r 1 /q

1

+

r 2 /q

2

+

r 3 /q

3

+···+

rn/q

n

,