Advanced book on Mathematics Olympiad

Number Theory 695

Of course, the sum terminates at themth term, wheremis defined bypm≤n<pm+^1.

Writeγ=α 2 , so thatαequals either 2γor 2γ+1. From the hypothesis,

n^2 ≥ 4 k≥ 4 pα,

and hencen≥ 2 pα/^2 ≥ 2 pγ. Sincen<pm+^1 , this leads topm+^1 −γ>2. It means that

ifp=2, thenγ<m, and ifp≥3, thenγ≤m.

Ifp=2, we will show thatβ≥m+γ, from which it will follow thatβ≥ 2 γ+ 1 ≥α.

The coefficient of 2 inn!is

⌊n

2

⌋

+

⌊n

22

⌋

+···+

⌊n

2 m

⌋

.

All terms in this sum are greater than or equal to 1. Moreover, we have seen thatn≥ 2 · 2 γ,
so the first term is greater than or equal to 2γ, and so this sum is greater than or equal to
2 γ+m−1. It is immediate that this is greater than or equal toγ+mfor anyγ≥1.
Ifp≥3, we need to show that
⌊
n
p

⌋

+

⌊

n

p^2

⌋

+···+

⌊

n

pm

⌋

≥m+γ+ 1.

This timem≥γ, and som+γ+ 1 ≥γ+γ+ 1 ≥α. Again, sincen≥ 2 pγ, the

first term of the left-hand side is greater than or equal to 2pγ−^1. So the inequality can be

reduced to 2pγ−^1 +m− 1 ≥m+γ+1, or 2pγ−^1 ≥γ+2. This again holds true for

anyp≥3 andγ≥2. Forγ=1, ifα=2, then we have 2pγ−^1 +m− 1 ≥m+γ≥α.

Ifα=3, thenn^2 ≥ 2 p^3 impliesn≥ 2 

√

pp≥ 3 p, and hence the first term in the sum

is greater than or equal to 3, so again it is greater than or equal toα.

We have thus showed that any prime appears to a larger power inn!than ink, which

means thatkdividesn!.

(Austrian–Polish Mathematics Competition, 1986)

749.Define

E(a, b)=a^3 b−ab^3 =ab(a−b)(a+b).

Since ifaandbare both odd, thena+bis even, it follows thatE(a, b)is always even.

Hence we only have to prove that among any three integers we can find two,aandb,

withE(a, b)divisible by 5. If one of the numbers is a multiple of 5, the property is true.

If not, consider the pairs{ 1 , 4 }and{ 2 , 3 }of residue classes modulo 5. By the pigeonhole

principle, the residues of two of the given numbers belong to the same pair. These will

beaandb.Ifa≡b(mod 5), thena−bis divisible by 5, and so isE(a, b). If not, then

by the way we defined our pairs,a+bis divisible by 5, and so againE(a, b)is divisible

by 5. The problem is solved.

(Romanian Team Selection Test for the International Mathematical Olympiad, 1980,

proposed by I. Tomescu)