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

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]

• Well, an obvious first step is to try to prove that it is divisible by $p$.
– lulu
Dec 12 '19 at 15:37
• $\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$) Dec 13 '19 at 14:02

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

• 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...." Dec 13 '19 at 12:04
• @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}$.
– robjohn
Dec 13 '19 at 12:53
• 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}$ ? Dec 13 '19 at 13:12
• 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.... Dec 13 '19 at 19:03

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

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

$$\newcommand{\qmod}{\quad\left(\mathrm{mod}\ #1\right)} \newcommand{\rmod}{\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$$

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