Baltic Way 2023 Shortlist

From the binomial formula, we have $$2^p=C_p^0+\cdots +C_p^p.$$ Since $C_p^0=C_p^p=1$, we also have $$2^p-2=C_p^1+\cdots +C_p^{p-1}.$$ For $1\le k\le p-1$, we will find the value of $C_p^k$ modulo $p^2$. We know that $$C_p^k=\frac{p!}{k!(p-k)!}=p\cdot \frac{(p-1)!}{k!(p-k)!}.$$ Write $x_k=\frac{(p-1)!}{k!(p-k)!}$. Note that $x_k$ is an integer, because $p{x}_k=\frac{p!}{k!(p-k)!}=C_p^k$ is clearly an integer, but $p{x}_k=C_p^k$ is divisible by $p$, as there is no factor of $p$ in the denominator. Since $$k!=k\cdot (k-1)\cdot \cdots \cdot 1\equiv (-1{)}^k(p-k)\cdot (p-k+1)\cdot \cdots \cdot (p-1)(\mathrm{mod}p),$$ one has $$-k{x}_k\equiv (p-k)x_k\equiv \frac{(p-k)(p-1)!}{(-1{)}^k(p-1)!(p-k)}\equiv (-1{)}^k(\mathrm{mod}p).$$ Therefore, $(-1{)}^{k+1}k{x}_k\equiv 1(\mathrm{mod}p)$, which yields $(-1{)}^{k+1}{x}_k\equiv a_k(\mathrm{mod}p)$ and $x_k\equiv (-1{)}^{k+1}{a}_k(\mathrm{mod}p)$. Adding together these congruences, for $k=1,\dots ,p-1$, we get $x_1+x_2+\cdots +x_{p-2}+x_{p-1}\equiv a_1-a_2-\cdots -a_{p-2}+a_{p-1}(\mathrm{mod}p)$. Therefore, $$\begin{array}{rl}{2}^p-2& =C_p^1+\cdots +C_p^{p-1}\equiv p(x_1+x_2+\cdots +x_{p-2}+x_{p-1})\\ & \equiv p(a_1-a_2+\cdots +a_{p-2}-a_{p-1})(\mathrm{mod}{p}^2),\end{array}$$ as desired.