4
$\begingroup$

Prove $\binom{2p+1}{p}\equiv2$ mod $p$ when $p$ is any prime.

I started by attempting to construct the congruence as follows:

Since $(2p+1)!=(2p+1)(2p)(2p-1)!$ and $p|2p$, then $(2p+1)!\equiv0$ mod $p$. Since $p|p!$, then $2p!(p+1)!\equiv0$ mod $p$. Therefore, $(2p+1)!\equiv2p!(p+1)!$ mod $p$.

However, I run into a problem here, because since $p!$ and $(p+1)!$ are not relatively prime to $p$, I cannot divide them to the left side to get the congruence I want.

I also attempted to write out $\binom{2p+1}{p}$ and see if I can get cancellation, but I run into a problem with figuring out how to get p! to divide into the remaining parts of $(2p+1)!$ after I divide out $(p+1)!$.

Any suggestions on what I should try next?

$\endgroup$
  • 1
    $\begingroup$ You should have a look at the Wikipedia page about Wolstenholme's theorem. $\endgroup$ – Jack D'Aurizio Mar 19 '17 at 15:08
  • 1
    $\begingroup$ Lucas' theorem gives this more or less immediately. $\endgroup$ – Jyrki Lahtonen Mar 19 '17 at 15:11
4
$\begingroup$

$$\binom{2p+1}{p} = \frac{(p+2)(p+3)\cdots(2p+1)}{1\cdot2\cdots p}$$

Separating out the multiples of $p$ in the numerator and the denominator, this equals $$\frac{2p}{p}\frac{(p+2)(p+3)\cdots(2p-1)(2p+1)}{1\cdot2\cdots(p-1)}$$

And mod $p$ this is just $$2 \frac{2\cdot3\cdots(p-1)\cdot1}{1\cdot2\cdots(p-1)} =2$$

$\endgroup$
1
$\begingroup$

Hint: $$(u+v)^p\equiv u^p+v^p\pmod p$$ for any $u,v$. So examine $(1+x)^{2p+1}$ by examining $((1+x)^{2})^p(1+x)$.

$\endgroup$
0
$\begingroup$

How about a combinatorial / group theoretic proof?

We can define an action of $\mathbb{Z}/p\mathbb{Z}$ on a $2p+1$ element set by cyclically permuting the first $p$ elements, cyclically permuting the second $p$ elements and fixing the last point. Explicitly if we take out $2p+1$ element set to be $\{1,2,\dots, 2p+1\}$ the generator $1 \in \mathbb{Z}/p\mathbb{Z}$ sends $p$ to $1$, $2p$ to $p+1$, fixes $2p+1$, and sends every other $a$ to $a+1$.

This action induces an action on $p$ element subsets of our $2p+1$ element set. This splits up our set of $p$ element subsets into orbits, all of which must be of size $p$ or of size $1$.

But now by how we constructed the action it's clear that the only fixed subsets by this action are the first $p$ elements and the next $p$ after that.

Hence the total number of $p$ element subsets is $p\cdot \{\text{number of orbits of size p}\} +2$

$\endgroup$

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.