Maths Olympiad Prep

Library / APMO /3 of 25

APMO

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

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

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

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

Solution

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

b.
Note that n>2pk≥3k/2n > 2p_{k} \geq 3k/2 implies k<2n/3k < 2n/3, so n−k>n/3n-k > n/3. So if we can find integers a,b≥3a, b \geq 3 such that n=abn = ab and a≠ba \neq b, then both aa and bb will appear separately in the product (n−k)!=1×2×⋯×(n−k)(n-k)! = 1 \times 2 \times \cdots \times (n-k), which means n∣(n−k)!n \mid (n-k)!. Observe that k≥14k \geq 14 implies pk≥13p_{k} \geq 13, so that n>2pk≥26n > 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 n≥26>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 a≥ka \geq k. From n−k=2a−k≥2a−a=a>2n-k = 2a - k \geq 2a - a = a > 2 we see that n=2an = 2a divides into (n−k)!(n-k)!.

Case (ii): b=ab = a. Then n=a2n = a^{2} and a>6a > 6 since n≥26n \geq 26. Thus n−k>n/3=a2/3>2an-k > n/3 = a^{2}/3 > 2a, so that both aa and 2a2a appear among {1,2,…,n−k}\{1, 2, \ldots, n-k\}. Hence n=a2n = a^{2} divides into (n−k)!(n-k)!.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.