Peter wrote: Let $ p > 3$ is a prime number and $ k = \lfloor\frac {2p}{3}\rfloor$. Prove that \[ {p \choose 1} + {p \choose 2} + \cdots + {p \choose k} \] is divisible by $ p^{2}$. I will assume paragraphs 1. and 2. of http://www.mathlinks.ro/Forum/viewtopic.php?t=150391 (or http://www.problem-solving.be/pen/viewtopic.php?t=25 ) post #4 as known. We have to prove that $ p^{2}\mid\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}$. In http://www.mathlinks.ro/Forum/viewtopic.php?t=150400 (or http://www.problem-solving.be/pen/viewtopic.php?t=34 ) post #2, Theorem 1, I showed that $ v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\right)\geq 1$. This rewrites as $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {\left( - 1\right)^{i - 1}}{i}\equiv 0\mod p$, where we are working with fractions modulo $ p$ (what is allowed in our case because the denominators are integers $ i$ satisfying $ 1\leq i\leq\left\lfloor 2p/3\right\rfloor$, and these integers are not divisible by $ p$). In other words, $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\left( - 1\right)^{i - 1}\equiv 0\mod p$. Now we prove a simple lemma: Lemma 1. If $ p$ is a prime and $ i$ is an integer satisfying $ 0\leq i\leq p - 1$, then $ \binom{p - 1}{i}\equiv\left( - 1\right)^{i}\mod p$. Proof of Lemma 1. We have $ \binom{p - 1}{i} = \frac {\left(p - 1\right)\cdot\left(p - 2\right)\cdot ...\cdot\left(p - i\right)}{i!}$, and thus $ i!\cdot\binom{p - 1}{i} = \left(p - 1\right)\cdot\left(p - 2\right)\cdot ...\cdot\left(p - i\right)\equiv\left( - 1\right)\cdot\left( - 2\right)\cdot ...\cdot\left( - i\right)$ $ = \left( - 1\right)^{i}\cdot\left(1\cdot 2\cdot ...\cdot i\right) = \left( - 1\right)^{i}\cdot i!\mod p$. Now, $ i!$ is coprime with $ p$ (since $ i! = 1\cdot 2\cdot ...\cdot i$, and all the numbers $ 1$, $ 2$, ..., $ i$ are coprime with $ p$ since $ p$ is a prime and $ i < p$); hence, we can divide this congruence by $ i!$, and obtain $ \binom{p - 1}{i}\equiv\left( - 1\right)^{i}\mod p$. Lemma 1 is proven. Now, for every integer $ i$ satisfying $ 1\leq i\leq\left\lfloor 2p/3\right\rfloor$, Lemma 1 yields $ \binom{p - 1}{i - 1}\equiv\left( - 1\right)^{i - 1}\mod p$, so that $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\left( - 1\right)^{i - 1}\equiv 0\mod p$ becomes $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\equiv 0\mod p$. In other words, $ v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\right)\geq 1$. Together with $ v_{p}\left(p\right) = 1$, this yields $ v_{p}\left(p\cdot\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\right) = v_{p}\left(p\right) + v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\right)\geq 1 + 1 = 2$. But $ p\cdot\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1} = p\cdot\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\cdot\frac {\left(p - 1\right)!}{\left(i - 1\right)!\cdot\left(\left(p - 1\right) - \left(i - 1\right)\right)!}$ $ = \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {p\cdot\left(p - 1\right)!}{\left(i\cdot\left(i - 1\right)!\right)\cdot\left(\left(p - 1\right) - \left(i - 1\right)\right)!} = \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {p!}{i!\cdot\left(p - i\right)!} = \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}$. Hence, we get $ v_{p}\left(\sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}\right)\geq 2$. Since $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}$ is an integer, this means $ p^{2}\mid \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}$, qed. Note that this problem also appeared as question 2 in the 11th Annual Vojtech Jarnik International Mathematical Competition 2001, Category I. See also http://www.mathlinks.ro/Forum/viewtopic.php?t=151379 . Darij

Where's the lemma no 2? , Mr darij grinberg?

We haven't any exact and simple solutions, example: the Darij's solution! I think that this isn't a hard problem and we can solve it more simply and purer! I cann't understand the termes, example: "p-ardic"... Help me, please!

ricardokaka wrote: I think that this isn't a hard problem and we can solve it more simply and purer! Then post your solution, please! I also believe p-adic numbers can be avoided.

Sorry, but p-adic numbers were never used in any of the proofs (even not in the linked ones).

darij grinberg wrote: Now, for every integer $ i$ satisfying $ 1\leq i\leq\left\lfloor 2p/3\right\rfloor$, Lemma 1 yields $ \binom{p - 1}{i - 1}\equiv\left( - 1\right)^{i - 1}\mod p$, so that $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\left( - 1\right)^{i - 1}\equiv 0\mod p$ becomes $ \sum_{i = 1}^{\left\lfloor 2p/3\right\rfloor}\frac {1}{i}\binom{p - 1}{i - 1}\equiv 0\mod p$. In other words, Darij I don't see prove. I give full solution at least 2 times. Let $ S(a,b)=\sum_{a<i<b}\frac 1i \mod p$. Then $ \sum_{0<i<2p/3}\frac{(-1)^{i-1}}{i}=\sum_{0<i<2p/3, i-odd}\frac 1i -\frac 12 S(0,\frac p3) =-\sum_{p/3<i<p, p-even}\frac 1i-\frac 12 S(0,\frac p3)=-\frac 12 (S(\frac p6 ,\frac p2 )+S(0,\frac p3 )).$ Let $ S_i=S(\frac{ip}{6},\frac{(i+1)p}{6})\mod p,i=0,1,2,3,4,5$. Obviosly $ S_i+S_{5-i}=0$. Consider $ T_a=\frac{a^{p-1}-1}{p}\sum_{x=1}^{p-1}x^{p-1}=\frac 1p \sum_{x=1}^{p-1}(ax)^{p-1}-x^{p-1}=\sum_{j=1}^{p-1}j(p-1)\sum_{jp/a<x<(j+1)p/a}(ax-p[ax/p])^{p-2} \mod p=\sum_{j=1}^{a-1}\frac{-j}{a} \sum_{jp/a<x<(j+1)p/a}\frac 1x \mod p.$ It give $ \sum_{i=0}^{[(a-2)/2]}(a-1-2i)S_{i,a}=aT_a\mod p$, were $ S_{i,a}=\sum_{ip/a<x<(i+1)p/a}\frac 1x \mod p$. Because $ T_6=T_2+T_3$, we get $ 5S_0+3S_1+S_2-3(S_0+S_1+S_2)-2(2S_0+2S_1)=6T_6-3*(2T_2)-2*(3T_3)=0\mod p.$ It give $ 0=S_0+2S_1+S_2=S(\frac p6,\frac p2 )+S(0,\frac p3 )\mod p$

I have derived a shorter solution here, wonder if it's valid. Solution: Re-write it as $p(\frac{(p-1)!}{1!(p-1)!}+\frac{(p-1)!}{2!(p-2)!}+...+\frac{(p-1)!}{k!(p-k!)})$ , factoring out $p$, and taking modulo $p$ gives, \[\ \equiv 1!-\frac{1!}{2!}+\frac{2!}{3!}+...+(-1)^{k-1}\frac{(k-1)!}{k!} \] Simplifying, the above expression is equivalent to, \[\ 1+\frac{1}{2}+...+\frac{1}{k}-2(1+...+\frac{1}{\lfloor \frac{k}{2} \rfloor}) = \frac{1}{\lfloor \frac{k}{2} \rfloor +1 } +...+ \frac{1}{k} \] Now we consider the cases when $p=6n+1,6n-1$. case 1: $p=6n+1$ We have, $k=4n$, the expression becomes, \[\ \frac{1}{2n+1} +...+ \frac{1}{4n} \equiv 0 \pmod {p} \] Since we can pair opposite reciprocals, such that their numerator is $6n+1$. i.e $(4n)+(1+2n)=6n+1$. And note that there are exactly, $(4n)-(2n+1)+1=2n$ terms, which is an even number. Hence, the pairing is possible. case 2: $p=6n-1$, we have $k=4n-1$, the expression becomes, \[\ \frac{1}{2n} +...+ \frac{1}{4n-1} \equiv 0 \pmod {p} \] which can be solved in the exact same way as case 1. $\Box$ EDIT: edited some typos :p

$\dbinom{p}{r}\equiv p\times\frac{(-1)^{k-1}}{k} \mod p^2 \implies$ now we should check two cases $p=6n+1$ and $p=6n+5$ case 1: let $p=6n+1\implies \sum_{i=1}^{\lfloor\frac{2p}{3}\rfloor} \dbinom{p}{i} \div p \equiv \frac{1}{1}-\frac{1}{2}+...-\frac{1}{4n} \equiv$ $\frac{1}{1}+\frac{1}{2}+...+\frac{1}{4n} - 2(\frac{1}{2}+\frac{1}{4}+...+\frac{1}{4n})$ $\equiv \frac{1}{2n+1}+...+\frac{1}{4n} \mod p$ which is obvious as we take pairs $\frac{1}{2n+1+i}, \frac{1}{4n-i}$ case 2: let $p=6n+5 \implies \sum_{i=1}^{\lfloor\frac{2p}{3}\rfloor} \dbinom{p}{i} \div p \equiv \frac{1}{1}-\frac{1}{2}+...-\frac{1}{4n+2}+\frac{1}{4n+3} \equiv$ $\frac{1}{1}+\frac{1}{2}+...+\frac{1}{4n+2}+\frac{1}{4n+3} -2(\frac{1}{2}+\frac{1}{4}+...+\frac{1}{4n+2}) \equiv \frac{1}{2n+2}+...+\frac{1}{4n+3} \mod p$ which again obvious by taking pairs