Maths Olympiad Prep

Library / /2 of 14

Number theory Difficulty 5.0 AIME, harder Prove it Singapore

Let pp be an odd prime. Prove that
1p2+2p2+3p2++(p12)p222pp(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}.

Solution

First, for each i=1,2,,p12i = 1, 2, \dots, \frac{p-1}{2},
2ip(p2i)=(p1)(p2)(p(2i1))(2i1)!(1)(2)((2i1))(2i1)!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(p1)/2ip2i=1(p1)/2ip22ip(p2i)2pi=1(p1)/2ip1(p2i)2pi=1(p1)/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 2p112^{p-1} - 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.