16 Binomial coefficients are (almost)never powers Proof.Note first that we may assume n 2k because of ()=() Suppose the theorem is false,and that (=m.The proof,by contra- diction,proceeds in the following four steps. (1)By Sylvester's theorem,there is a prime factor p of ()greater thank. hence pe divides n(n-1)...(n-k +1).Clearly,only one of the factors n-i can be a multiple of any such p >k,and we conclude pn-i,and therefore n≥p>k4≥k2 (2)Consider any factor n-j of the numerator and write it in the form n-j=ajm,where aj is not divisible by any nontrivial e-th power.We note by (1)that aj has only prime divisors less than or equal to k.We want to show next that ai aj for ij.Assume to the contrary that ai =aj for some i<j.Then mi>mj+1 and k>(n-i)-(m-j)=a(m-m)≥a(m+1)-m) >alm51≥am/2≥n-k+1)e ≥（受+1）1/2>n2/2, which contradicts n >k2 from above. (3)Next we prove that the ai's are the integers 1,2,...,k in some order. (According to Erdos,this is the crux of the proof.)Since we already know that they are all distinct,it suffices to prove that aoa1·ak-1 divides k!. Substituting n-j=ajm into the equation()=m,we obtain aoa1…ak-1(mom…mk-1)'=klm. Cancelling the common factors of mo...mk1 and m yields a0a1…ak-1u2=kue with gcd(u,v)=1.It remains to show that v 1.If not,then v con- tains a prime divisor p.Since gcd(u,v)=1,p must be a prime divisor of aoa1...ak1 and hence is less than or equal to k.By the theorem of Legendre (see page 8)we know that contains p to the power We now estimate the exponent of p in n(n-1)...(n-k+1).Let i be a positive integer,and let bi<b2<...<bs be the multiples of p'among n,n-1,...,n-k 1.Then bs =61+(s-1)p'and hence (s-1)p2=bs-b1≤n-(n-k+1)=k-1, which implies s≤+1≤制+116 Binomial coefficients are (almost) never powers Proof. Note first that we may assume n ≥ 2k because of n k  = n n−k  . Suppose the theorem is false, and that n k  = m. The proof, by contra￾diction, proceeds in the following four steps. (1) By Sylvester’s theorem, there is a prime factor p of n k  greater than k, hence p divides n(n − 1)···(n − k + 1). Clearly, only one of the factors n − i can be a multiple of any such p>k, and we conclude p | n − i, and therefore n ≥ p > k ≥ k2. (2) Consider any factor n − j of the numerator and write it in the form n − j = ajm j , where aj is not divisible by any nontrivial -th power. We note by (1) that aj has only prime divisors less than or equal to k. We want to show next that ai = aj for i = j. Assume to the contrary that ai = aj for some i<j. Then mi ≥ mj + 1 and k > (n − i) − (n − j) = aj (m i − m j ) ≥ aj ((mj + 1) − m j ) > aj m−1 j ≥ (ajm j ) 1/2 ≥ (n − k + 1)1/2 ≥ ( n 2 + 1)1/2 > n1/2, which contradicts n>k2 from above. (3) Next we prove that the ai’s are the integers 1, 2,...,k in some order. (According to Erdos, this is the crux of the proof.) Since we already know ˝ that they are all distinct, it suffices to prove that a0a1 ··· ak−1 divides k!. Substituting n − j = ajm j into the equation n k  = m, we obtain a0a1 ··· ak−1(m0m1 ··· mk−1)  = k!m . Cancelling the common factors of m0 ··· mk−1 and m yields a0a1 ··· ak−1u = k!v with gcd(u, v)=1. It remains to show that v = 1. If not, then v con￾tains a prime divisor p. Since gcd(u, v)=1, p must be a prime divisor of a0a1 ··· ak−1 and hence is less than or equal to k. By the theorem of Legendre (see page 8) we know that k! contains p to the power i≥1 k pi . We now estimate the exponent of p in n(n − 1)···(n − k + 1). Let i be a positive integer, and let b1 < b2 < ··· < bs be the multiples of pi among n, n − 1,...,n − k + 1. Then bs = b1 + (s − 1)pi and hence (s − 1)pi = bs − b1 ≤ n − (n − k + 1) = k − 1, which implies s ≤ k − 1 pi  + 1 ≤  k pi  + 1.