Let $p\ge5$ be a prime. Show that \[\sum_{k=0}^{(p-1)/2}\binom{p}{k}3^k\equiv 2^p - 1\pmod{p^2}.\] Victor Wang.
Problem
Source: ELMO Shortlist 2011, N2
Tags: modular arithmetic, number theory proposed, number theory
qwerty414
03.07.2012 08:33
Expanding $(3+1)^p = (3-1)^{2p}$ works.
Anyone into filling details? I want to work on other problems too. Pretty interesting, this ELMO
math154
04.07.2012 08:20
qwerty414 wrote:
Expanding $(3+1)^p = (3-1)^{2p}$ works.
That seems like an interesting idea, but I don't see how to use it. Could you elaborate?
math154
17.07.2012 18:54
It's been a while, and this is a silly problem (see my comments on ISL 2011 N7), so I guess I'll post my intended solution.
The key idea is that for $1\le k\le (p-1)/2$, we have
\begin{align*}
\binom{p}{k}\equiv\frac{p}{k}\binom{p-1}{k-1}
&\equiv\frac{p}{k}(-1)^{k-1} \\
&\equiv2(-1)^k\frac{p}{2k}(-1)^{2k-1}\equiv2(-1)^k\binom{p}{2k}\pmod{p^2}.
\end{align*}Hence we just need to show
\[\sum_{k=0}^{(p-1)/2}2\binom{p}{2k}(-3)^k\equiv 2^p\pmod{p^2}.\]But in fact
\[\sum_{k=0}^{(p-1)/2}2\binom{p}{2k}(-3)^k=(1+\sqrt{-3})^p+(1-\sqrt{-3})^p=2^p\]from the identity $\omega^{2p}+\omega^p+1=0$ (where $\omega=e^{2\pi i/3}$), so we're done.
Of course, we can find similar identities using a roots of unity filter when $(p-1)/2$ is replaced by $(p-1)/r$, where $r$ is any number dividing $p-1$.
However, I would still like to see if anyone can complete qwerty414's idea.