MathLabs

Problem 3

Let k≥14k\ge14 be an integer, and let pkp_k be the largest prime strictly less than kk. You may assume that pk≥3k/4p_k\ge3k/4. Let nn be composite. 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)!.
Step 2 of 5: Bound the factorial cutoff
Previous stepNext step
n>2pk≥3k/2  ⟹  k≤2n/3  ⟹  n−k≥n/3n>2p_k\ge3k/2\implies k\le2n/3\implies n-k\ge n/3
Detailed analysis

For n>2pkn>2p_k and pk≥3k/4p_k\ge3k/4, we have n>3k/2n>3k/2, hence k<2n/3k<2n/3 and n−k>n/3n-k>n/3. Also k≥14k\ge14 implies pk≥13p_k\ge13, so n>26n>26.