Maths Olympiad Prep

Library / /47 of 65

Number theory Difficulty 6.3 National Olympiad Prove it Bulgaria

Problem:

For any positive integer nn the sum 1+12++1n1+\frac{1}{2}+\cdots+\frac{1}{n} is written in the form pnqn\frac{p_{n}}{q_{n}}, where pnp_{n} and qnq_{n} are coprime numbers.

a) Prove that 33 does not divide p67p_{67}.

b) Find all nn, for which 33 divides pnp_{n}.

Solution

Solution:

a) Set Sn=1+12++1nS_{n}=1+\frac{1}{2}+\cdots+\frac{1}{n}. We have that S2=32S_{2}=\frac{3}{2}, S7=3121140S_{7}=\frac{3121}{140},
S22S7=18+122+110+120+111+119+114+116+113+117+19+112+115+118+121=30ab+51140=3cd \begin{aligned} S_{22}-S_{7}= & \frac{1}{8}+\frac{1}{22}+\frac{1}{10}+\frac{1}{20}+\frac{1}{11}+\frac{1}{19}+\frac{1}{14}+\frac{1}{16}+\frac{1}{13}+\frac{1}{17}+ \\ & \frac{1}{9}+\frac{1}{12}+\frac{1}{15}+\frac{1}{18}+\frac{1}{21}=\frac{30 a}{b}+\frac{51}{140}=\frac{3 c}{d} \end{aligned}
where (a,b)=(c,d)=1(a, b)=(c, d)=1. It is easy to see that ab(mod3)a \equiv b \pmod{3}. Hence 3c,d3 \nmid c, d, c≢d(mod3)c \not \equiv d \pmod{3}, p22=3p22p_{22}=3 p_{22}' and 3p223 \nmid p_{22}'. Similarly, we have that S67S22=90ef+cdS_{67}-S_{22}= \frac{90 e}{f}+\frac{c}{d}, where 3f3 \nmid f. It follows that 3p67,q673 \nmid p_{67}, q_{67}.

b) Set Sn=kn3mnlnS_{n}=\frac{k_{n}}{3^{m_{n}} l_{n}}, where 3kn,ln3 \nmid k_{n}, l_{n}. Then
S3n=Sn3+1+12+14+15++13n2+13n1=kn3mn+1ln+3anbn=knbn+3mn+2lnan3mn+1lnbn \begin{aligned} S_{3 n} & =\frac{S_{n}}{3}+1+\frac{1}{2}+\frac{1}{4}+\frac{1}{5}+\cdots+\frac{1}{3 n-2}+\frac{1}{3 n-1} \\ & =\frac{k_{n}}{3^{m_{n}+1} l_{n}}+3 \cdot \frac{a_{n}}{b_{n}}=\frac{k_{n} b_{n}+3^{m_{n}+2} l_{n} a_{n}}{3^{m_{n}+1} l_{n} b_{n}} \end{aligned}
where 3bn3 \nmid b_{n}. Therefore, if mn1m_{n} \geq -1, then m3n=mn+1m_{3 n}=m_{n}+1. Analogously, we have that m3n+2=mn+1m_{3 n+2}=m_{n}+1 for mn1m_{n} \geq -1 and m3n+1=mn+1m_{3 n+1}=m_{n}+1 for mn0m_{n} \geq 0. Since m1=0m_{1}=0, m2=m7=m22=1m_{2}=m_{7}=m_{22}=-1 and m67=0m_{67}=0, it is easy to see that the answer is n=2,7,22n=2,7,22.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.