Category: Number Theory

Problem

Determine all integers m ≥ 2 such that every n with m ≤ n ≤ m divides the binomial coefficient n m−2n . Solution. The integers in question are all prime numbers. First we check that all primes satisfy the condition, and even a stronger one. Namely, if p is a prime then every n with 1 ≤ n ≤ p divides n p−2n . This is true for p = 2 where n = 1 is the only possibility. For an odd prime p take n ∈ [1, p ] and consider the following identity of binomial coefficients: (p − 2n) · n p − 2n = n · n − 1 p − 2n − 1 . Since p ≥ 2n and p is odd, all factors are non-zero. If d = gcd(p − 2n,n) then d divides p, but d ≤ n < p and hence d = 1. It follows that p − 2n and n are relatively prime, and so the factor n in the right-hand side divides the binomial coefficient n p−2n . Next we show that no composite number m has the stated property. Consider two cases. • If m = 2k with k > 1, pick n = k. Then m ≤ n ≤ m but n m−2n = k = 1 is not divisible by k > 1. • If m is odd then there exist an odd prime p and an integer k ≥ 1 with m = p(2k + 1). Pick n = pk, then m ≤ n ≤ m by k ≥ 1. However n n m − 2n

(pk − 1)(pk − 2)···(pk − (p − 1)) p! is not an integer, because p divides the denominator but not the numerator.45