Advanced book on Mathematics Olympiad

5.2 Arithmetic 259

Example.Letp>3 be a prime number, and let

r

ps

= 1 +

1

2

+

1

3

+···+

1

p

,

the sum of the firstpterms of the harmonic series. Prove thatp^3 dividesr−s.

Solution.The sum of the firstpterms of the harmonic series can be written as

p!

1

+

p!

2

+···+

p!

p

p!

.

Because the denominator isp!and the numerator is not divisible byp, any common
prime divisor of the numerator and the denominator is less thanp. Thus it suffices to
prove the property forr=p 1 !+p 2 !+···+pp!ands=(p− 1 )!. Note that

r−s=p

(

(p− 1 )!

1

+

(p− 1 )!

2

+···+

(p− 1 )!

p− 1

)

.

We are left with showing that

(p− 1 )!

1

+

(p− 1 )!

2

+···+

(p− 1 )!

p− 1

is divisible byp^2. This sum is equal to
p− 21
∑

k= 1

(k+p−k)

(p− 1 )!

k(p−k)

=p

p− 21

∑

k= 1

(p− 1 )!

k(p−k)

.

So let us show that
p− 21
∑

k= 1

(p− 1 )!

k(p−k)

is an integer divisible byp. Note that ifk−^1 denotes the inverse ofkmodulop, then
p−k−^1 is the inverse ofp−kmodulop. Hence the residue classes of[k(p−k)]−^1
represent just a permutation of the residue classes ofk(p−k),k= 1 , 2 ,...,p− 21. Using
this fact, we have
p− 21
∑

k= 1

(p− 1 )!

k(p−k)

≡(p− 1 )!

p− 21

∑

k= 1

[k(p−k)]−^1 ≡(p− 1 )!

p− 21

∑

k= 1

k(p−k)

≡−(p− 1 )!

p− 21

∑

k= 1

k^2 =−(p− 1 )!

p− 1

2 ·

p+ 1

2 ·p

6

≡ 0 (modp).

This completes the proof.