4
$\begingroup$

Prove that, if $p$ is an odd prime number, then ${f(p)}=\binom{2p-1}{p-1}-1$ is divisible by $p^2$.


This is a question that was asked to me in a Permutations and Combinations test. I don't know how to solve it.I have heard that a combinatorial argument can be used to prove this. I would appreciate such an argument as well.

[Bill D: to aid search: this is attributed to Babbage. A stronger version is Wolstenholme's theorem]

$\endgroup$
2
  • 1
    $\begingroup$ Well, an obvious first step is to try to prove that it is divisible by $p$. $\endgroup$
    – lulu
    Dec 12 '19 at 15:37
  • $\begingroup$ $\dbinom{2p-1}{p-1}=\dfrac{(p+1)(p+2)\cdots(p+p-1)}{(p-1)!}=\dfrac{Np^2+ap}{(p-1)!}+1\Rightarrow END$ (because it is known that $a$ is divisible by $p$) $\endgroup$
    – Piquito
    Dec 13 '19 at 14:02
4
$\begingroup$

Note that $$\binom{2p}{p}=\frac{2p}{p}\binom{2p-1}{p-1}=2\binom{2p-1}{p-1}$$

Thus it suffices to show that $$\binom{2p}{p} \equiv 2 \pmod{p^2}$$

This can be proven combinatorically like in the first answer to this question

$\endgroup$
4
  • $\begingroup$ I'm really not that well versed with number theory so it would be a great help if you could explain the step where you directly said "Thus it suffices to show that...." $\endgroup$
    – Aditya
    Dec 13 '19 at 12:04
  • $\begingroup$ @Aditya: the original question is to show that $\binom{2p-1}{p-1}\equiv1\pmod{p^2}$, which is the same as $\binom{2p}{p}=2\binom{2p-1}{p-1}\equiv2\pmod{p^2}$. $\endgroup$
    – robjohn
    Dec 13 '19 at 12:53
  • $\begingroup$ Yes, I get it. But how does $\binom{2p}{p}$=$\frac{2p}{p}\binom{2p-1}{p-1}$ imply that $p^2$ divides $\binom{2p-1}{p-1}$ ? $\endgroup$
    – Aditya
    Dec 13 '19 at 13:12
  • $\begingroup$ I didn't say that $p^2$ divides $\binom{2p-1}{p-1}$. I am saying that $p^2 | \binom{2p}{p}-2$ by the link posted. Now, you have $$\binom{2p}{p}-2=2 \left( \binom{2p-1}{p-1}-1 \right)$$ is divisible by $p^2$, and since $p$ is odd.... $\endgroup$
    – N. S.
    Dec 13 '19 at 19:03
2
$\begingroup$

Enough to show that $2\cdot(\, \binom{2p-1}{p-1}-1) $ is divisible by $p^2$, or, equivalently, $\binom{2p}{p}-2 $ is. Recall that we have $\binom{2p}{p}=\sum_{k+l=p} \binom{p}{k}\binom{p}{l}$, so $$\binom{2p}{p}-2=\sum_{k=1}^{p-1} \binom{p}{k}\binom{p}{p-k}$$ and each term is a product of two factors divisible by $p$. We are done.

$\bf{Added:}$ With the same method we can see easily that $$\binom{ap}{bp}-\binom{a}{b} $$ is divisible by $p^2$. This follows from the equality $$\binom{ap}{bp}=\sum_{k_1+\cdots k_a=bp} \prod_{i=1}^a \binom{p}{k_i}$$ On RHS, there are $\binom{a}{b}$ terms equal to $1$. Every other term contains at least two factors divisible by $p$.

$\endgroup$
1
  • $\begingroup$ (+1) Nice use of Vandermonde! This method can also be used to get the result in my answer. $\endgroup$
    – robjohn
    Dec 14 '19 at 13:02
2
$\begingroup$

$\newcommand{\qmod}[1]{\quad\left(\mathrm{mod}\ #1\right)} \newcommand{\rmod}[1]{\left(\mathrm{mod}\ #1\right)}$ The Binomial Theorem shows that $$ \frac{(x+p)^k-x^k}p\equiv kx^{k-1}\pmod{p}\tag1 $$ and, when $p$ is a prime, Fermat's Little Theorem shows that $$ \prod_{k=1}^{p-1}(x-k)=x^{p-1}+(p-1)!+p\sum_{k=1}^{p-2}a_kx^k\tag2 $$ Applying $(1)$ to $(2)$ says $$ \begin{align} \prod_{k=1}^{p-1}(x+p-k)-\prod_{k=1}^{p-1}(x-k) &\equiv (x+p)^{p-1}-x^{p-1}&\rmod{p^2}\\ &\equiv p(p-1)x^{p-2}&\rmod{p^2}\tag3 \end{align} $$ Setting $x=np$ in $(3)$, for $p\ge3$, gives $$ \prod_{k=1}^{p-1}((n+1)p-k)\equiv\prod_{k=1}^{p-1}(np-k)\qmod{p^2}\tag4 $$ which, by induction, shows that $$ \prod_{k=1}^{p-1}(np-k)\equiv(p-1)!\qmod{p^2}\tag5 $$ which says that $$ \binom{np-1}{p-1}\equiv1\qmod{p^2}\tag6 $$

$\endgroup$
1
$\begingroup$

Following comment of @Piquito, we write, $$\binom{2p-1}{p-1} = \frac{(2p-1)!}{p!(p-1)!}$$ $$ = \frac{(p+1)(p+2)\cdots(p+p-2)(p+p-1)}{(p-1)!}$$ Now, multiply out the product in numerator, first multiplying all the second terms, we get $1\times2\times3\times\cdots\times(p-2)\times(p-1)=(p-1)!$

Now, terms containing $p$ are $p(2\times3\times\cdots\times(p-2)\times(p-1)), p(1\times3\times\cdots\times(p-2)\times(p-1)), p(1\times2\times4\times\cdots\times(p-2)\times(p-1)),...$

Sum of all terms containing a single $p$ is therefore, $$p\sum_{i=1}^{p-1}\frac{(p-1)!}{i}$$ which is divisible by $p^2$ (follows from Claim) and all the remaining terms are divisible by $p^2$. Hence, required number is $$\binom{2p-1}{p-1}-1=\frac{Np^2+(p-1)!}{(p-1)!}-1$$ for some natural number $N$, which is divisible by $p^2$, as desired.

Claim: $p\Big|\sum_{i=1}^{p-1}\frac{(p-1)!}{i}$

Proof: Let $1\leq i\leq p-1$ and let $j$ be its multiplicative inverse in $\mathbb Z_p$. Then, $$\frac{(p-1)!}{i}\equiv -j\pmod p$$

Now, since $\mathbb Z_p$ is a field, the list of multiplicative inverses of elements in $\mathbb Z_p\setminus 0$ is $\mathbb Z_p\setminus 0$. Therefore, $$\sum_{i=1}^{p-1}\frac{(p-1)!}{i}\equiv \sum_{j=1}^{p-1}-j\pmod p$$ $$\equiv -\frac{p(p-1)}{2}\pmod p$$ $$\equiv 0\pmod p$$

Hence proved

$\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.