# 2010 USAMO #5:Prove that if $\frac{1}{p}-2S_q = \frac{m}{n}$ for integers $m$ and $n$, then $m - n$ is divisible by $p$.

Let $$q = \frac{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(q+1)(q+2)}$$

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

My Progress till now: $$2S_q = 2\sum_{x=1}^{\frac{q+1}{3}} \frac{1}{(3x-1)(3x)(3x+1)} = \sum_{x=1}^{\frac{p-1}{2}} \left[\frac{1}{3x(3x-1)}-\frac{1}{3x(3x+1)}\right]\\ =\sum_{x=1}^{\frac{p-1}{2}} \left[ \frac{1}{3x-1} - \frac{2}{3x} +\frac{1}{3x+1}\right]\\ =\sum_{x=1}^{\frac{p-1}{2}}\left[ \frac{1}{3x-1} + \frac{1}{3x} +\frac{1}{3x+1}\right] - \sum_{x=1}^{\frac{p-1}{2}} \frac{1}{x}$$

With the help of @user10354138 , I have got $$\frac{1}{p} - 2S_q = \frac{1}{p} + \frac{1}{1} - \sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k} = \frac{m}{n}$$

But then I am stuck.

Please give me some hints rather than a solution. Thanks in advance.

PS: I didn't post it in AOPS, because there we don't get any guidance.

• It would be nice if you join some chat rooms which are mainly developed for problem solving,this room can be helpful chat.stackexchange.com/rooms/77161/basic-mathematics,, this one down is a little higher level for a high schooler but anyway explore it,chat.stackexchange.com/rooms/36/mathematics Jul 28 '20 at 6:44
• I am sorry , I am new to MSE, what is a chat room ? Jul 28 '20 at 6:47
• People interact there, about any topic they find interesting, i am sorry i cannot introduce you to others there, i am currently suspended from chatting Jul 28 '20 at 6:49

(Original) Hint: You are almost there with the simplification. Note that you are summing over $$\frac1n$$ from $$n=2$$ to $$\frac{3p-1}2$$ in the first. So $$2S_q+1=\sum_{n=(p+1)/2}^{(3p-1)/2}\frac1n$$ If you tweak the RHS slightly, you would be summing over $$\frac1n$$ as $$n$$ runs through representative of each of the nonzero residue classes mod $$p$$. So ...

Addendum (2020-07-29): As discussed in the comments, \begin{align*} \frac1p-2S_q-1&=-\left(\sum_{n=(p+1)/2}^{p-1}\frac1n+\sum_{n=p+1}^{p+(p-1)/2}\frac1n\right)\\ &=-\sum_{i=1}^{(p-1)/2}\left(\frac1{p-i}+\frac1{p+i}\right) \end{align*} and now $$\frac1{p-i}+\frac1{p+i}=\frac{p}{(p-i)(p+i)}$$ so the numerators are divisible by $$p$$ and the denominators are not. So putting everything over a common denominator, we see $$\frac{m-n}{n}=-\sum_{i=1}^{(p-1)/2}\frac{p}{(p-i)(p+i)}=\frac{p\times \text{some integer}}{\text{some integer not divisible by }p}.$$ That is, every representation of $$\frac{m-n}{n}$$ must have more factors of $$p$$ in the numerator than in the denominator, hence $$m-n$$ is divisible by $$p$$.

• aren't we summing 1/n from n=2 to 3(p-1)/2 +1 ? Jul 27 '20 at 4:05
• Oops, yes it should be $(3p-1)/2$, corrected. Jul 27 '20 at 4:07
• So we have ,$\frac{1}{p} - 2S_q = \frac{1}{p} + \frac{1}{1} - \sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k} = \frac{m}{n}$ Jul 27 '20 at 4:11
• also can you explain this line , " you would be summing over 1/𝑛 as 𝑛 runs through representative of each of the nonzero residue classes mod 𝑝" Jul 27 '20 at 4:13
• As $k$ runs through $(p+1)/2$ to $(3p-1)/2$ it is $p$ consecutive numbers you are taking reciprocal of. If you cancel out the $1/p$ then those $k$s leave remainders $1,2,\dots,p-1$ when divided by $p$, in some order. Jul 27 '20 at 4:25

With the help of @user10354138 's hints, I think I got the solution.I will be grateful if someone proof reads it.

Note that $$2S_q = 2\sum_{x=1}^{\frac{q+1}{3}} \frac{1}{(3x-1)(3x)(3x+1)} = \sum_{x=1}^{\frac{p-1}{2}} \left[\frac{1}{3x(3x-1)}-\frac{1}{3x(3x+1)}\right]\\ =\sum_{x=1}^{\frac{p-1}{2}} \left[ \frac{1}{3x-1} - \frac{2}{3x} +\frac{1}{3x+1}\right]\\ =\sum_{x=1}^{\frac{p-1}{2}}\left[ \frac{1}{3x-1} + \frac{1}{3x} +\frac{1}{3x+1}\right] - \sum_{x=1}^{\frac{p-1}{2}} \frac{1}{x}$$ .

Proceeding further we get that,$$\frac{1}{p} - 2S_q = \frac{1}{p} + \frac{1}{1} - \sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k} = \frac{m}{n}$$

or we get that $$- 2S_q = \frac{1}{1} - \sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k} = \frac{m}{n}-\frac{1}{p}$$

Now, note that $$\sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k}\equiv \sum_{k=1}^{p-1}\frac1k \equiv \sum_{k=1}^{p-1}k \equiv 0$$ mod $$p$$

So we get that $$\frac{m}{n}\equiv 1$$ mod $$p$$ .

Hence we have $$1-\frac{m}{n}\equiv 0$$ mod p $$\implies m-n \equiv 0$$ mod $$p$$.

And we are done!

• How did you get $\sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k}\equiv \sum_{k=1}^{p-1}\frac1k$ mod p ? I understood the rest part though.. Jul 29 '20 at 6:24
• @Raheel , Note that $\sum_{k=\frac{p+1}{2}}^{\frac{3p-1}{2}}\frac{1}{k}$ is nothing but p consecutive integers in their multiplicative inverse modulo p . Jul 29 '20 at 6:54
• oh..I see, thanks Jul 29 '20 at 9:14
• You need to be careful about what you mean by taking a fraction in $\mathbb{Q}$ modulo $p$. Jul 29 '20 at 12:01