Advanced book on Mathematics Olympiad

694 Number Theory

∑

k≥ 1

k

(⌊

n

pk

⌋

−

⌊

n

pk+^1

⌋)

=

∑

k≥ 1

(k−(k− 1 ))

⌊

n

pk

⌋

=

∑

k≥ 1

⌊

n

pk

⌋

.

By Polignac’s formula this is the exponent ofpinn!and we are done.
(64th W.L. Putnam Mathematical Competition, 2003)

747.First solution: We will show that for any prime numberpthe power to which it
appears in the numerator is greater than or equal to the power to which it appears in the
denominator, which solves the problem.
Assume thatpappears to the powerαinnand to the powerβinm,α≥β≥0.
Then among the inequalities
⌊
n
pk

⌋

≥

⌊

m

pk

⌋

+

⌊

n−m

pk

⌋

,k= 1 , 2 ,...,

those withβ<k≤αare strict. Using this fact when applying Polignac’s formula ton!,
m!, and(n−m)!, we deduce that the power ofpin

(n

m

)

is at leastα−β. Of course, the
power ofpin gcd(m, n)isβ. Hencepappears to a nonnegative power in

gcd(m, n)

n

(

n

m

)

,

and we are done.

Second solution: A solution that does not involve prime numbers is also possible. Since
gcd(m, n)is an integer linear combination ofmandn, it follows that

gcd(m, n)

n

(

n

m

)

is an integer linear combination of the integers

m

n

(

n

m

)

=

(

n− 1

m− 1

)

and

n

n

(

n

m

)

=

(

n

m

)

,

and hence is itself an integer.
(61st W.L. Putnam Mathematical Competition, 2000)

748.Letpbe a prime divisor ofk. Thenp≤n,sopis also a divisor ofn!. Denote the
powers ofpinkbyαand inn!byβ. The problem amounts to showing thatα≤βfor
all prime divisorspofk.
By Polignac’s formula, the power ofpinn!is

β=

∑∞

i= 1

⌊

n

pi

⌋

.