Maths Olympiad Prep

Library / /494 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

Example 4 (15th Asia Pacific Mathematical Olympiad) Let k,k14,pkk, k \geqslant 14, p_{k} be the largest prime less than kk. If pk3k4p_{k} \geqslant \frac{3 k}{4}, and nn is a composite number, prove:
(1) If n=2pkn=2 p_{k}, then nn does not divide (nk)(n-k) !.
(2) If n>2pkn>2 p_{k}, then nn divides (nk)(n-k) !.

Solution

Prove (1) When n=2pkn=2 p_{k},
Since k>pkk>p_{k}, then pk>2pkk=nkp_{k}>2 p_{k}-k=n-k, so, pk(nk)!p_{k} \nmid(n-k)!, hence n(nk)!n \nmid(n-k)!.
(2) When n>2pkn>2 p_{k},

Since nn is a composite number, let n=ab(2ab)n=a b(2 \leqslant a \leqslant b), if a3a \geqslant 3.
( i ) aba \neq b, then n>2pk3k2,bn3n>2 p_{k} \geqslant \frac{3 k}{2}, b \leqslant \frac{n}{3}.
Thus, kn3b>ak\frac{n}{3} \geqslant b>a.
So n(nk)!n \mid(n-k)!.
(ii) a=ba=b, then n=a2,nk>n3=a23n=a^{2}, n-k>\frac{n}{3}=\frac{a^{2}}{3},

Since k14k \geqslant 14, then pk13,n26,a6p_{k} \geqslant 13, n \geqslant 26, a \geqslant 6,
Thus a232a\frac{a^{2}}{3} \geqslant 2 a. Hence nk>2an-k>2 a. So, n(nk)!n \mid(n-k)!.
If a=2a=2, since n26n \geqslant 26, assume bb is not a prime, then b=b1b2(b1b2)b=b_{1} b_{2}\left(b_{1} \leqslant b_{2}\right), since b13b \geqslant 13, then b24b_{2} \geqslant 4, thus ab14a b_{1} \geqslant 4 falls into the case of a3a \geqslant 3,
Assume bb is a prime, then b=n2>pkb=\frac{n}{2}>p_{k},
Since pkp_{k} is the largest prime less than kk, then b>kb>k,
Thus nk=2bk>bn-k=2 b-k>b. So, n(nk)!n \mid(n-k)!.
In summary, when n>2pkn>2 p_{k}, n(nk)!n \mid(n-k)!.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.