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 3 of 5: Treat powers of two
Previous stepNext step
n=2t (t≥5):n=4⋅2t−2,4,2t−2<n/3n=2^t\ (t\ge5):\qquad n=4\cdot2^{t-2},\qquad 4,2^{t-2}<n/3
Detailed analysis

If n=2tn=2^t, then n>26n>26 forces t≥5t\ge5. The two distinct factors 44 and 2t−22^{t-2} have product nn, and both are at most n/3n/3 (including the smallest case n=32n=32). They therefore occur separately in (n−k)!(n-k)!, so nn divides that factorial.