Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition) - Q9
Background
All theorems, corollaries, and definitions listed in the book's order:
I will only use theorems or facts that are proved before this question. So you will not see that I quote theorems or facts from the later chapters.
Question
If $p$ is a prime satisfying $n < p < 2n$, show that $${2n \choose n} \equiv 0 \pmod p$$
Solution
First, we have ${2n \choose n} = \frac{(2n)!}{n!n!} = \frac{(2n)(2n - 1) \cdots (n + 1)}{n!}$.
We know ${2n \choose n} \in \mathbb{Z}^{+}$, so $n! \mid (2n)(2n - 1) \cdots (n + 1)$. Because $n < p < 2n$, so $p \mid (2n)(2n - 1) \cdots (n + 1)$ as well.
Since $n < p$, we have $gcd(n!, p ) = 1$. Because $p$ does not divide any factor in $n!$.
From here, we have 3 methods to continue. They are similar, but they are different ways of thinking.
First Method:
We conclude $p \mid \frac{(2n)(2n - 1) \cdots (n + 1)}{n!}$ directly from above. Thus, $p \mid {2n \choose n}$ which means ${2n \choose n} \equiv 0 \pmod p$.
(Why?
The logic is a bit implicit here. Because $gcd(n!, p ) = 1$, so $n!$ does not contain $p$ as a factor. The numerator $(2n)(2n - 1) \cdots (n + 1)$ contains $p$ as a factor. After $(2n)(2n - 1) \cdots (n + 1)$ is divided by $n!$, the result will still contain the factor $p$. So, $\frac{(2n)(2n - 1) \cdots (n + 1)}{n!} = mp$ for some integer $m$.
)
Second Method (Use Euclid's Lemma):
(This is how I solved it at the beginning.)
We have $n! \mid (2n)(2n - 1) \cdots (p+ 1)(p)(p - 1) \cdots (n + 1)$.
Because $gcd(n!, p ) = 1$, by Euclid's Lemma, $n! \mid (2n)(2n - 1) \cdots (p+ 1)(p - 1) \cdots (n + 1)$.
It means that $\frac{(2n)(2n - 1) \cdots (p+ 1)(p - 1) \cdots (n + 1)}{n!} = m$ for some integer $m$. So, ${2n \choose n} = mp$. Thus, $p \mid {2n \choose n}$ which means ${2n \choose n} \equiv 0 \pmod p$.
Third Method (Use Euclid's Lemma):
As $p \mid (2n)(2n - 1) \cdots (n + 1)$, we have $p \mid \frac{(2n)(2n - 1) \cdots (n + 1)}{n!}n! = {2n \choose n}n!$.
By Euclid's Lemma, $p \mid {2n \choose n}$. Thus, $p \mid {2n \choose n}$ which means ${2n \choose n} \equiv 0 \pmod p$.
Conclusion
I think the second method is the easiest to come up with. The first method is the shortest, while the third method is a good technique which you can apply on other questions.
Read More: All My Solutions for This Book