Maths Olympiad Prep

Library / /359 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

Let k14k\ge 14 be an integer, and let pkp_k be the largest prime number which is strictly less than kk. You may assume that pk3k4p_k\ge \tfrac{3k}{4}. Let nn be a composite integer. Prove that [list=a] [*] if n=2pkn=2p_k, then nn does not divide (nk)!(n-k)!, [*] if n>2pkn>2p_k, then nn divides (nk)!(n-k)!. [/list]

Solution

To solve this problem, we need to prove two statements about the composite integer n n in relation to the factorial (nk)! (n-k)! .

### Part (a): If n=2pk n = 2p_k , then n n does not divide (nk)! (n-k)!

1. **Identify n n and pk p_k **:
Given n=2pk n = 2p_k , where pk p_k is the largest prime number strictly less than k k .

2. Factorial and divisibility:
We need to show that n=2pk n = 2p_k does not divide (nk)! (n-k)! .

3. Range of factorial:
Consider the factorial (nk)! (n-k)! . Since n=2pk n = 2p_k , we have:
nk=2pkk n - k = 2p_k - k
The factorial (2pkk)! (2p_k - k)! includes all integers from 1 to 2pkk 2p_k - k .

4. **Prime pk p_k in the factorial**:
Since pk p_k is the largest prime less than k k , and pk3k4 p_k \ge \frac{3k}{4} , it follows that:
2pkk2(3k4)k=3k2k=k2 2p_k - k \le 2 \left(\frac{3k}{4}\right) - k = \frac{3k}{2} - k = \frac{k}{2}
Therefore, 2pkkk2 2p_k - k \le \frac{k}{2} .

5. **Divisibility by 2pk 2p_k **:
Since 2pkkk2 2p_k - k \le \frac{k}{2} , the factorial (2pkk)! (2p_k - k)! does not include the prime pk p_k or the number 2pk 2p_k . Hence, 2pk 2p_k cannot divide (2pkk)! (2p_k - k)! .

Thus, n=2pk n = 2p_k does not divide (nk)! (n-k)! .

### Part (b): If n>2pk n > 2p_k , then n n divides (nk)! (n-k)!

1. **Identify n n and pk p_k **:
Given n>2pk n > 2p_k , where pk p_k is the largest prime number strictly less than k k .

2. Factorial and divisibility:
We need to show that n n divides (nk)! (n-k)! .

3. Range of factorial:
Consider the factorial (nk)! (n-k)! . Since n>2pk n > 2p_k , we have:
nk>2pkk n - k > 2p_k - k
The factorial (nk)! (n-k)! includes all integers from 1 to nk n-k .

4. **Inclusion of pk p_k and 2pk 2p_k **:
Since n>2pk n > 2p_k , the range nk n - k is greater than 2pkk 2p_k - k . Therefore, the factorial (nk)! (n-k)! includes both pk p_k and 2pk 2p_k .

5. **Divisibility by n n **:
Since n n is a composite number greater than 2pk 2p_k , and (nk)! (n-k)! includes all factors of n n , it follows that n n divides (nk)! (n-k)! .

Thus, n>2pk n > 2p_k divides (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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.