USAMO 2010.5
by v_Enhance, Nov 24, 2011, 7:29 PM
USAMO 2010 Problem 5 wrote:
Let
where
is an odd prime, and let
Prove that if
for integers
and
, then
is divisible by
.


![\[
S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)}
\]](http://latex.artofproblemsolving.com/c/0/b/c0bf0826fbe8897ebaf0d4b3c861120d502baefd.png)





Solution
Compute first
using partial fractions:
Now take everything modulo
, so that
, and compute
, as desired.

\[ \begin{align*} S_q &= \sum_{m=1}^{\frac{p-1}{2}} \frac{1}{(3m-1)(3m)(3m+1)} \\ &= \sum_{m=1}^{\frac{p-1}{2}} \frac{1}{2} \left( \frac{1}{3m-1} + \frac{1}{3m+1} - \frac{2}{3m} \right) \\ &= \frac12 \left( \sum_{k=2}^{q+2} \left( \frac1k \right)- 3 \sum_{m=1}^{\frac{p-1}{2}} \left( \frac{1}{3m} \right) \right) \\ &= \frac12 \left( \sum_{k=2}^{q+2} \left( \frac1k \right)- 3 \sum_{m=1}^{\frac{p-1}{2}} \left( \frac{1}{m} \right) \right) \end{align*} \]
Now take everything modulo


\[ \begin{align*} \frac{1}{p} - 2S_q &= \sum_{m=1}^{\frac{p-1}{2}} \left( \frac{1}{m} \right) - \sum_{k=2}^{p-1} \left( \frac{1}{k} \right) - \sum_{k=p+1}^{q+2} \left( \frac{1}{k} \right) \\ &\equiv \sum_{m=1}^{\frac{p-1}{2}} \left( \frac{1}{m} \right) - \sum_{k=2}^{p-1} \left( \frac{1}{k} \right) - \sum_{k=(p+1)-p}^{q+2-p} \left(\frac{1}{k} \right) \pmod{p} \\ &\equiv \sum_{m=1}^{\frac{p-1}{2}} \left( \frac{1}{m} \right) - \sum_{k=2}^{p-1} \left( \frac{1}{k} \right) - \sum_{k=1}^{\frac{p-1}{2}} \left(\frac{1}{k} \right) \pmod{p} \\ &= - \sum_{k=2}^{p-1} k^{-1} \pmod{p} \\ &\equiv -(-1) \pmod{p} \\ & \equiv 1 \pmod{p} \end{align*} \]So

well at least that's one more usamo problem solved...
This post has been edited 1 time. Last edited by v_Enhance, Nov 24, 2011, 7:29 PM