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 $l$th 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).


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$.

  • $\begingroup$ Thanks, but can you describe why a_j + k is greater than n? $\endgroup$ – ecg Sep 30 '17 at 9:42
  • $\begingroup$ $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. $\endgroup$ – Berni Waterman Sep 30 '17 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.