# HELP! Proofs from the Book: Binomial coefficients are almost never powers

this is Paul Erdos's proof provided by the book:

Theorem: let $l$ $\geq$ $2$ and $4$ $\leq$ $k$ $\leq$ $n$ $-$ $4$, then the equation ${n\choose k}$ = $m^{l}$ does not have an integer solution.

(Part 1)

"...we may assume $n$ $\geq$ $2k$ because of ${n\choose k}$ = ${n\choose n - k}$. Assume the theorem is false. By Sylvester's theorem, there is a prime factor $p$ of ${n\choose k}$ greater than $k$, hence $p^{l}$ divides $n$$(n-1)$$(n-2)$ ... $(n-k+1)$. Clearly, only one of the factors $n-i$ can be a multiple of any such $p>k$."

(Part 2)

"Consider any factor $n-j$ of the numerator and write it in the form $a_j$$m_j^{l}, where a_j is not divisible by any non-trivial lth power. We note by part 1 that a_j only has prime divisors less or equal to k." It says that there is one of the factors a_j that can be multiple of p>k. But why not any a_j from any factor n$$(n-1)$ ... $(n-k+1)$ can have a prime divisor $p>k$?

Thanks for your help.

One more non-maths question (if you have time): I've been reading Proofs from the Book and it is quite daunting. For example, I can "technically" understand and follow a half of a proof, but when I get stuck like the question above, it really drags me down. For those who read this book, did you find it very readable? It is an excellent book, no doubt, but I often feel really stupid while I read it (although I am economics major).

## 1 Answer

Note that $n - (n-k+1) = k-1$. Thus, if there exists a natural number $m$ and some factor $a_j$ such that $a_j = mp$ for $p > k$, then we have $(m+1)p > a_j + k > n > (n-k+1) > a_j - k > (m-1)p$.

• Thanks, but can you describe why a_j + k is greater than n? – ecg Sep 30 '17 at 9:42
• $a_j$ is an integer between $n$ and $n-k+1$. Therefore $a_j \geq n-k+1$ and thus $a_j + k \geq n-k+1+k = n+1 > n$. Also, please upvote and mark my answer if this has indeed answered your question. – Berni Waterman Sep 30 '17 at 9:55