1
$\begingroup$

Let a prime $p$ such that $1 \leq n <p<2n$. Prove that:

$$\binom{2n}{n} \equiv 0 \pmod{p}$$

Can I do it like that?

$$\binom{2n}{n}=\frac{(2n)!}{n!n!}=\frac{(n+1)(n+2) \cdots (2n-1)2n}{1 \cdot 2 \cdots n}\overset{ \text{As } 1 \leq n <p<2n }{=} \frac{(n+1)(n+2) \cdots p \cdots (2n-1)2n}{1 \cdot 2 \cdots n} \equiv 0 \pmod p$$

$\endgroup$
7
  • 2
    $\begingroup$ You should use a couple of words. But mostly yes. $\endgroup$
    – Daniel Fischer
    Commented Jun 21, 2014 at 12:33
  • $\begingroup$ What could I write for example? $\endgroup$
    – evinda
    Commented Jun 21, 2014 at 12:35
  • $\begingroup$ you need to get rid of the denominator $\endgroup$
    – Adam
    Commented Jun 21, 2014 at 12:37
  • $\begingroup$ But..it is not equal to something from the numerator..I got rid from the first $n!$,isn't it right?? $\endgroup$
    – evinda
    Commented Jun 21, 2014 at 12:38
  • 1
    $\begingroup$ @DanielFischer I think one needs more than that, being prime is also important. Note that $6$ divides the numerator of $4=\frac{12}{3}$ and it doesn't divide the denominator.... $\endgroup$
    – N. S.
    Commented Jun 21, 2014 at 12:42

2 Answers 2

Reset to default
4
$\begingroup$

In my opinion, the last line needs a justification, note that the fact that $p$ is a prime is the key here.

Note that when you say $$ \frac{(n+1)(n+2) \cdots p \cdots (2n-1)2n}{1 \cdot 2 \cdots n} \equiv 0 \pmod p \,,$$ you say that $\frac{(n+1)(n+2) \cdots (p-1)(p+1) \cdots (2n-1)2n}{1 \cdot 2 \cdots n}$ is integer, but why is that the case?

The argument is very simple: $$\binom{2n}{n} n! =(n+1)(n+2) \cdots p \cdots (2n-1)2n$$

Therefore $p$ divides $\binom{2n}{n} n!$. As $p$ is prime, we get $p| \binom{2n}{n}$ or $p|n!$. But $p|n!$ is not possible, as again primality would imply that it divides one of $1,2,3,...,n$.

$\endgroup$
6
  • $\begingroup$ I understood the argument!!! But,could you explain me why: $$\frac{(n+1)(n+1) \cdots (p-1)(p+1) \cdots (2n-1)2n}{1 \cdot 2 \cdots n}$$ is not an integer?? $\endgroup$
    – evinda
    Commented Jun 21, 2014 at 13:00
  • $\begingroup$ @evinda It is an integer, but it is not OBVIOUS that it is an integer. In other words, can you explain why IS an integer?? Note that explaining why is an integer is exactly the justification of this last step. $\endgroup$
    – N. S.
    Commented Jun 21, 2014 at 13:05
  • $\begingroup$ @evinda And just to clarify something, it is an integer when $p$ is prime, but if $n< p< 2n$ is not prime sometimes $\frac{(n+1)(n+1) \cdots (p-1)(p+1) \cdots (2n-1)2n}{1 \cdot 2 \cdots n}$ is not an integer. For example, it is not an integer when $n=4, p=6$.... And this makes the justification needed, at least in my opinion. $\endgroup$
    – N. S.
    Commented Jun 21, 2014 at 13:08
  • $\begingroup$ But how can I show that it is an integer,when $p$ is a prime? And could you explain me further why it is not an integer,when $p$ is not a prime? $\endgroup$
    – evinda
    Commented Jun 21, 2014 at 13:10
  • $\begingroup$ @evinda Check my answer, since $\frac{(n+1)(n+1) \cdots (p-1)(p+1) \cdots (2n-1)2n}{1 \cdot 2 \cdots n} =\frac{\binom{2n}{n}}{p}$, the moment I proved that $p | \binom{2n}{n}$ I implicitly proved that this is an integer. But this is not needed, $p | \binom{2n}{n}$ means $\binom{2n}{n} \equiv 0 \pmod{p}$... As for non-primes, this is not needed, but if you want to see it for curiosity, calculate that fraction with $n=4, p=6$.... $\endgroup$
    – N. S.
    Commented Jun 21, 2014 at 13:18
0
$\begingroup$

Lucas' theorem solved this immediately: $$\binom{n}{i} \equiv \binom{2n-p}{n}\binom{1}{0} \equiv 0 \pmod{p},$$ because $2n-p<n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .