10
$\begingroup$

How does one prove that for a prime $p \geq 5$ the sum : $$\sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$$ is divisible by $p^{2}$.

Since each term of $\displaystyle \sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$ is divisible by $p$, only thing remains is to prove that the sum $$\sum\limits_{ 0 < k < \frac{2p}{3}} \frac{1}{p} { p \choose k}$$ is divisible by $p$.

How to evaluate this sum: $\displaystyle \frac{1}{p} { p \choose k} = \frac{(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdot 3 \cdots k}$

  • 2
    This is identical to a problem that appeared on the Putnam exam a couple decades ago.2010-09-03

2 Answers 2

7

Since we are working in the field $\mathbb{F}_p$ we can write

$$\frac{(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdots k}$$ as

$$\frac{(-1)(-2) \cdots (-(k-1))}{1 \cdot2 \cdots k}$$

= $$\frac{(-1)^{k-1}}{k}$$

Let $N = [\frac{2p}{3}]$ and $M = [\frac{N}{2}]$

Thus what we need is

$$ \sum_{k=1}^{N} \frac{(-1)^{k-1}}{k}$$ $$ = \sum_{k=1}^{N} \frac{1}{k} - 2 \sum_{k=1}^{M}\frac{1}{2k}$$ $$ =\sum_{k=M+1}^{N}\frac{1}{k}$$

Now $N+M+1 =p$ so we can rewrite as

$$\frac{1}{N} + \frac{1}{M+1} + \frac{1}{N-1} + \frac{1}{M+2} + \cdots = $$

$$\frac{p}{N(M+1)} + \frac{p}{(N-1)(M+2)} + \cdots $$

which is $0$.

There are $N-M$ terms, which is even, so each term gets paired off.

  • 0
    Staggering proof! One question: What made you to think of an $N$ and $M$ like that.2010-09-03
  • 4
    2p/3 is in the question you gave, and when you have alternating sums, it's natural to consider it as sum it all, and minus twice the negative terms.2010-09-03
  • 0
    @Chandru: Leaving the - signs wasn't going anywhere. Trying to get rid of them, you come up with the N and M. So yeah, what Soarer said. +1 to Soarer's comment.2010-09-03
3

From your last equation one gets $$\frac1p{p\choose k}\equiv(-1)^k\frac 1k\pmod p.$$ So the problem is equivalent to $$\sum_{0 < k < 2p/3}(-1)^k\frac1k\equiv0\pmod{p}.$$

The case $p=1979$ was set as the first problem at the 1979 IMO. The method used for this extends to all primes, and no doubt you can find solutions for the IMO problem out on the interweb.