Show that ## {2n \choose n}\equiv 0\pmod {p} ##?

[Math100]

Homework Statement

If $p$ is a prime satisfying $n<p<2n$, show that ${2n \choose n}\equiv 0\pmod {p}$.

Relevant Equations

None.

Proof:

Let $n$ be a positive integer.
Then ${2n \choose n}= \frac{(2n)!}{(n!)(n!)}= \frac{n!(n+1)(n+2)\dotsb (2n)}{(n!)(n!)}= \frac{(n+1)(n+2)\dotsb (2n)}{n!}$.
This means $n!\mid [(n+1)(n+2)\dotsb (2n)]$.
Since $n<p<2n$, it follows that $p\mid [(n+1)(n+2)\dotsb (2n)]$.
Note that $gcd(p, n!)=1$ because $p$ is prime.
Thus $p\mid\frac{(n+1)(n+2)\dotsb (2n)}{n!}\implies\ p\mid{2n \choose n}\implies {2n \choose n}\equiv 0\pmod {p}$.
Therefore, if $p$ is a prime satisfying $n<p<2n$, then ${2n \choose n}\equiv 0\pmod {p}$.

 

[fresh_42]

Homework Statement:: If $p$ is a prime satisfying $n<p<2n$, show that ${2n \choose n}\equiv 0\pmod {p}$.
Relevant Equations:: None.

Proof:

Let $n$ be a positive integer.
Then ${2n \choose n}= \frac{(2n)!}{(n!)(n!)}= \frac{n!(n+1)(n+2)\dotsb (2n)}{(n!)(n!)}= \frac{(n+1)(n+2)\dotsb (2n)}{n!}$.
This means $n!\mid [(n+1)(n+2)\dotsb (2n)]$.
Since $n<p<2n$, it follows that $p\mid [(n+1)(n+2)\dotsb (2n)]$.
Note that $gcd(p, n!)=1$ because $p$ is prime.
Thus $p\mid\frac{(n+1)(n+2)\dotsb (2n)}{n!}\implies\ p\mid{2n \choose n}\implies {2n \choose n}\equiv 0\pmod {p}$.
Therefore, if $p$ is a prime satisfying $n<p<2n$, then ${2n \choose n}\equiv 0\pmod {p}$.

Correct. I only wonder what you needed

This means $n!\mid [(n+1)(n+2)\dotsb (2n)]$.

for. If you wanted to say that $\binom{2n}{n}$ is an integer, you could have just written it

Then $\mathbb{Z}\ni {2n \choose n}= \frac{(2n)!}{(n!)(n!)}= \frac{n!(n+1)(n+2)\dotsb (2n)}{(n!)(n!)}= \frac{(n+1)(n+2)\dotsb (2n)}{n!}$.

or

Then ${2n \choose n}= \frac{(2n)!}{(n!)(n!)}= \frac{n!(n+1)(n+2)\dotsb (2n)}{(n!)(n!)}= \frac{(n+1)(n+2)\dotsb (2n)}{n!} \in \mathbb{Z}$.

I do not see why it is important that $n!$ divides $(n+1)(n+2)\dotsb (2n).$

 

[Math100]

Correct. I only wonder what you needed

for. If you wanted to say that $\binom{2n}{n}$ is an integer, you have written

or

I do not see why it is important that $n!$ divides $(n+1)(n+2)\dotsb (2n).$

Yes, that was actually my intention. To indicate that ${2n \choose n}$ is an integer. I didn't know that we can actually express ${2n \choose n}\in\mathbb{Z}$.

 

[nuuskur]

Let $n$ be a positive integer.
Then ${2n \choose n}= \frac{(2n)!}{(n!)(n!)}= \frac{n!(n+1)(n+2)\dotsb (2n)}{(n!)(n!)}= \frac{(n+1)(n+2)\dotsb (2n)}{n!}$.
This means $n!\mid [(n+1)(n+2)\dotsb (2n)]$.

Why? If you know a priori that $\binom{2n}{n}$ is an integer, then the above is unnecessary. If you want prove that it's an integer, you should also say something like "product of $n$ consecutive terms is divisible by $n!$" (prove this separately).

Note that $gcd(p, n!)=1$ because $p$ is prime.
Thus $p\mid\frac{(n+1)(n+2)\dotsb (2n)}{n!}$.

Yes. In general, $a\mid c$ and $b\mid c$ does not imply $ab\mid c$. In this case, it works. Why?

 

[Delta2]

Homework Statement:: If $p$ is a prime satisfying $n<p<2n$, show that ${2n \choose n}\equiv 0\pmod {p}$.
Relevant Equations:: None.

Note that gcd(p,n!)=1 because p is prime.

you should add that the prime p is $p>n$ because without that you might had the case that $gcd(p,n!)=p$

 

[Delta2]

Yes. In general, a∣c and b∣c does not imply ab∣c. In this case, it works. Why?

This is covered by saying $gcd(p,n!)=1$ but yeah it might not be so straightforward implication.