k > 14 is an integer and p is the largest prime smaller than k. k is chosen so that p ≥ 3k/4. Prove that 2p does not divide (2p - k)!, but that n does divide (n - k)! for composite n > 2p.
Solution
Since k > p, we have p > 2p-k and hence p does not divide any of 1, 2, 3, ... , 2p-k. But p is prime, so it does not divide (2p - k)! So 2p does not either.
Now consider composite n > 2p. Note that k > 14, so p ≥ 13, so n > 26. Take q to be the largest prime divisor of n and put n = qr. We now have three cases.
(1) q > r ≥ 3. Then n > 2p ≥ 3k/2, so 2n/3 > k. Hence n-k > n-2n/3 = n/3 ≥ n/r = q > r. So q and r are distinct integers < n-k. Hence n = qr divides (n-k)!.
(2) r = 2. Then n = 2q > 2p. But p is the largest prime < k. Hence q ≥ k, so n-k ≥ n-q = q. Obviously q > 2 (since n > 26), so q and 2 are distinct integers < n-k. Hence n = 2q divides (n-k)! .
(3) The final case is n = q2. We show that 2q ≤ n-k. Suppose not. Then 2q ≥ n-k+1 ≥ (2p+1)-k+1 ≥ 3k/2 + 1 - k + 1 = k/2 + 2. So q ≥ k/4 + 1. Also since 2q ≥ n-k+1, we have k ≥ n-2q+1 = (q-1)2 ≥ k2/16. If k > 16, this is a contradiction. If k = 15 or 16, then p = 13 and k ≥ (q-1)2 gives q ≤ 5, so n = q2 ≤ 25. But n > 2p = 26. Contradiction. So we have established that 2q ≤ n-k. But that means that q and 2q are distinct integers ≤ n-k and so their product 2n divides (n-k)!.
Thanks to Gerhard Woeginger for this.
© John Scholes
jscholes@kalva.demon.co.uk
27 Oct 2003
Last corrected/updated 27 Oct 03