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

Question

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]

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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