Maths Olympiad Prep

Library / /3 of 26

Number theory Difficulty 6.7 National Olympiad Prove it Asia Pacific Mathematics Olympiad (APMO)

Let k14k \geq 14 be an integer, and let pkp_{k} be the largest prime number which is strictly less than kk. You may assume that pk3k/4p_{k} \geq 3k/4. Let nn be a composite integer. Prove:

a. if n=2pkn = 2p_{k}, then nn does not divide (nk)!(n-k)!;

b. if n>2pkn > 2p_{k}, then nn divides (nk)!(n-k)!.

Solution

a.
Note that nk=2pkk<2pkpk=pkn-k = 2p_{k} - k < 2p_{k} - p_{k} = p_{k}, so pk(nk)!p_{k} \nmid (n-k)!, so 2pk(nk)!2p_{k} \nmid (n-k)!.

b.
Note that n>2pk3k/2n > 2p_{k} \geq 3k/2 implies k<2n/3k < 2n/3, so nk>n/3n-k > n/3. So if we can find integers a,b3a, b \geq 3 such that n=abn = ab and aba \neq b, then both aa and bb will appear separately in the product (nk)!=1×2××(nk)(n-k)! = 1 \times 2 \times \cdots \times (n-k), which means n(nk)!n \mid (n-k)!. Observe that k14k \geq 14 implies pk13p_{k} \geq 13, so that n>2pk26n > 2p_{k} \geq 26.

If n=2αn = 2^{\alpha} for some integer α5\alpha \geq 5, then take a=22a = 2^{2}, b=2α2b = 2^{\alpha-2}.

Otherwise, since n26>16n \geq 26 > 16, we can take aa to be an odd prime factor of nn and b=n/ab = n/a, unless b<3b < 3 or b=ab = a.

Case (i): b<3b < 3. Since nn is composite, this means b=2b = 2, so that 2a=n>2pk2a = n > 2p_{k}. As aa is a prime number and pkp_{k} is the largest prime number which is strictly less than kk, it follows that aka \geq k. From nk=2ak2aa=a>2n-k = 2a - k \geq 2a - a = a > 2 we see that n=2an = 2a divides into (nk)!(n-k)!.

Case (ii): b=ab = a. Then n=a2n = a^{2} and a>6a > 6 since n26n \geq 26. Thus nk>n/3=a2/3>2an-k > n/3 = a^{2}/3 > 2a, so that both aa and 2a2a appear among {1,2,,nk}\{1, 2, \ldots, n-k\}. Hence n=a2n = a^{2} divides into (nk)!(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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.