Maths Olympiad Prep

Library / /210 of 397

Number theory Difficulty 5.9 AIME, harder Prove it Taiwan

Suppose that pp is an odd prime, p7p \ge 7 and q=3p72q = \frac{3p-7}{2}.
Define the series
Sq=1234+1567++1(q+1)(q+2)(q+3) S_q = \frac{1}{2 \cdot 3 \cdot 4} + \frac{1}{5 \cdot 6 \cdot 7} + \cdots + \frac{1}{(q+1)(q+2)(q+3)}
Express 1+2Sq1p1 + 2S_q - \frac{1}{p} as a rational number mn\frac{m}{n} with (m,n)=1(m, n) = 1.
Prove that mm is a multiple of pp.

Solution

We need the partial fraction decomposition
2(k+1)(k+2)(k+3)=1k+12k+2+1k+3 \frac{2}{(k+1)(k+2)(k+3)} = \frac{1}{k+1} - \frac{2}{k+2} + \frac{1}{k+3}
Sum over q=1,4,7,q = 1,4,7, \dots, we get
2Sq=(1223+14)+(1526+17)++(1q+12q+2+1q+3)=12+13+14+15+16+17++1q+1+1q+2+1q+3(11+12++1q+2) \begin{aligned} 2S_q &= \left(\frac{1}{2} - \frac{2}{3} + \frac{1}{4}\right) + \left(\frac{1}{5} - \frac{2}{6} + \frac{1}{7}\right) + \cdots + \left(\frac{1}{q+1} - \frac{2}{q+2} + \frac{1}{q+3}\right) \\ &= \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \cdots + \frac{1}{q+1} + \frac{1}{q+2} + \frac{1}{q+3} \\ &\quad - \left(\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{q+2}\right) \end{aligned}
Also we have
1p+1+1p+2++1q+311+12++1(qp)+3(modp) \frac{1}{p+1} + \frac{1}{p+2} + \cdots + \frac{1}{q+3} \equiv \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{(q-p)+3} \pmod{p}
Note that
qp+3=q+23    q=3p72 q - p + 3 = \frac{q + 2}{3} \iff q = \frac{3p - 7}{2}
In the final, we have
1+2Sq1p1+12++1p1(modp)0(modp) \begin{aligned} 1 + 2S_q - \frac{1}{p} &\equiv 1 + \frac{1}{2} + \cdots + \frac{1}{p-1} \pmod{p} \\ &\equiv 0 \pmod{p} \end{aligned}

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 translated into English from en; metadata (topic, difficulty) added by this project.