Maths Olympiad Prep

Track / Stage 5 / 30 of 400 #630 of 1964

Problem 630

AIME late
Number theory Difficulty 5.0 Prove it Singapore Mathematical Olympiad (SMO) · Singapore

Let pp be an odd prime. Prove that
1p−2+2p−2+3p−2+⋯+(p−12)p−2≡2−2pp(modp). 1^{p-2} + 2^{p-2} + 3^{p-2} + \dots + \left(\frac{p-1}{2}\right)^{p-2} \equiv \frac{2-2^p}{p} \pmod{p}.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

First, for each i=1,2,…,p−12i = 1, 2, \dots, \frac{p-1}{2},
2ip(p2i)=(p−1)(p−2)⋯(p−(2i−1))(2i−1)!≡(−1)(−2)⋯(−(2i−1))(2i−1)!≡−1(modp). \frac{2i}{p} \binom{p}{2i} = \frac{(p-1)(p-2)\cdots(p-(2i-1))}{(2i-1)!} \equiv \frac{(-1)(-2)\cdots(-(2i-1))}{(2i-1)!} \equiv -1 \pmod{p}.
Hence
∑i=1(p−1)/2ip−2≡−∑i=1(p−1)/2ip−22ip(p2i)≡−2p∑i=1(p−1)/2ip−1(p2i)≡−2p∑i=1(p−1)/2(p2i)(modp)(by Fermat’s Little Theorem.) \begin{aligned} \sum_{i=1}^{(p-1)/2} i^{p-2} &\equiv - \sum_{i=1}^{(p-1)/2} i^{p-2} \frac{2i}{p} \binom{p}{2i} \\ &\equiv -\frac{2}{p} \sum_{i=1}^{(p-1)/2} i^{p-1} \binom{p}{2i} \\ &\equiv -\frac{2}{p} \sum_{i=1}^{(p-1)/2} \binom{p}{2i} \pmod{p} \quad \text{(by Fermat's Little Theorem.)} \end{aligned}
The last summation counts the even-sized nonempty subsets of a pp-element set, of which there are 2p−1−12^{p-1} - 1.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.