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:

Theorems and Corollaries in Elementary Number Theory

All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 4)

RanblogRan

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

Related Pages

< Chapter 4.2, Q8 Chapter 4.2, Q10 >