2010 USAMO Problems/Problem 5

Problem

Let $q = \dfrac{3p-5}{2}$ where $p$ is an odd prime, and let

$S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q\cdot (q+1) \cdot (q+2)}.$

Prove that if $\dfrac{1}{p}-2S_q = \dfrac{m}{n}$ for integers $m$ and $n$ , then $m-n$ is divisible by $p$ .

Solution

Since $p$ is an odd prime, $p = 2r + 1$ , for a suitable positive integer $r$ , and consequently $q = 3r - 1$ .

The partial-fraction decomposition of the general term of $S_q$ is:

$\begin{align*} \frac{1}{(3k-1)3k(3k+1)} &= \frac{1}{2}\left(\frac{1}{3k-1} - \frac{2}{3k} + \frac{1}{3k+1}\right) \\ &= \frac{1}{2}\left(\frac{1}{3k-1} + \frac{1}{3k} - \frac{1}{k} + \frac{1}{3k+1}\right) \\ &= \frac{1}{2}\left[\left(\frac{1}{3k-1} + \frac{1}{3k} + \frac{1}{3k+1}\right) - \frac{1}{k}\right], \end{align*}$

therefore

$\begin{align*} \frac{1}{p} - 2S_q &= \frac{1}{2r+1} - \left(\sum_{k=1}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\ &= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\ &= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right) \\ &= 1 - \sum_{k=1}^{r}\left(\frac{1}{(2r+1) - k} + \frac{1}{(2r+1) + k}\right) \\ &= 1 - \sum_{k=1}^{r}\frac{2p}{(p - k)(p + k)} \\ &= 1 - \frac{a}{b} = \frac{b - a}{b} \end{align*}$

with $a$ and $b$ positive relatively-prime integers.

Since $r < p$ and $p$ is a prime, in the final sum all the denominators are relatively prime to $p$ , but all the numerators are divisible by $p$ , and therefore the numerator $a$ of the reduced fraction $\frac{a}{b}$ will be divisible by $p$ . Since the sought difference $m - n = (b-a) - b = -a$ , we conclude that $p$ divides $m-n$ as required.

Alternative Calculation

We can obtain the result in a slightly different way:

$\begin{align*} \frac{1}{p} - 2S_q &= \frac{1}{2r+1} - \left(\sum_{k=1}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\ &= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\ &= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right) \end{align*}$

In the above sum the fractions represent every non-zero remainder $\mod p$ . Multiplying all the denominators yields a number $N$ that is $-1 \pmod p$ . The numerator $\mod p$ is $N$ times the sum of the reciprocals $\mod p$ of each non-zero remainder, and since this sum is $0$ , the numerator is $0 \pmod p$ . The rest of the argument is as before.

Page

Toolbox

Search

2010 USAMO Problems/Problem 5

Problem

Solution

Alternative Calculation