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 4 of 5: Use two factors at least three
Previous stepNext step
n=ab,a,b≥3,a,b≤n/3n=ab,\qquad a,b\ge3,\qquad a,b\le n/3
Detailed analysis

Otherwise choose an odd prime factor aa of nn and set b=n/ab=n/a. If b≥3b\ge3 and b≠ab\ne a, then a,b≥3a,b\ge3 and each is at most n/3n/3 (choose the labels so a≤ba\le b). Thus both occur among 1,…,n−k1,\ldots,n-k, and their separate product gives n∣(n−k)!n\mid(n-k)!.