SILK ROAD MATHEMATICAL COMPETITION

We will use congruences modulo $p$ for fractions, writing $\frac{a}{b}\equiv x(\mathrm{mod}p)$ for $b\not\equiv 0(\mathrm{mod}p)$ if $bx\equiv a(\mathrm{mod}p)$. A sum of such fractions is congruent to $0(\mathrm{mod}p)$ if and only if $p$ divides the numerator of the (reduced) sum of respective usual fractions. We shall prove the statement through the following claims;

Claim 1. For a given integer $r$, the number of positive integers $n<p$ such that $1+\frac{1}{2}+\cdots +\frac{1}{n}\equiv r(\mathrm{mod}p)$ is not greater than $\frac{3}{2}{p}^{\frac{2}{3}}$. Let $n_1<n_2<\cdots <n_{s+1}$ be all such $n$. Every integer $k$ appears at most $k-1$ times among the differences $n_{i+1}-n_i$ (since $n_i$ should be a root of the congruence $$\frac{1}{x+1}+\cdots +\frac{1}{x+k}\equiv 0(\mathrm{mod}p)$$ having at most $k-1$ roots: its left-hand side becomes a polynomial of degree $k-1$ when multiplied by the denominator). Consider the largest $m$ such that $1+2+\cdots +(m-1)=\frac{m(m-1)}{2}\le s$. Then $s<\frac{m(m+1)}{2}$. On the other hand, $n_{s+1}-n_1$ is the sum of $s$ differences $n_{i+1}-n_i$, and $$p>n_{s+1}-n_1\ge 1\cdot 2+2\cdot 3+\cdots +(m-1)m=\frac{m^3-m}{3}.$$ If $m\le 3$, the number of $n_i$, that is, $s+1$, is not greater than $6=\frac{3}{2}\cdot 8^{2/3}<\frac{3}{2}{p}^{2/3}$. And, for $m>3$ we have $$s+1\le \frac{m(m+1)}{2}<\frac{3}{2}{\left(\frac{m^3-m}{3}\right)}^{2/3}<\frac{3}{2}{p}^{2/3}.$$ (The middle inequality $m(m+1)<3{\left(\frac{m^3-m}{3}\right)}^{2/3}$ follows from $m^3(m+1{)}^3<3(m^3-m{)}^2$, i.e., $m^2+m<3(m-1{)}^2$.)

Claim 2. The number of good $n$ less than $p^k$ is not greater than ${\left(\frac{3}{2}{p}^{\frac{2}{3}}\right)}^k$. This can be proved by induction on $k$. The base case $k=1$ is given by Claim 1 for $r=0$. Note that for a good $n=c+n^{\prime }p$, $0\le c<p$, the number $n^{\prime }=c_1+\cdots +c_{k-1}{p}^{k-2}$ is also good. Indeed, in the sum $1+\frac{1}{2}+\cdots +\frac{1}{n}$ all the terms with denominators divisible by $p$ make together $\frac{1}{p}(1+\frac{1}{2}+\cdots +\frac{1}{n^{\prime }})$, and since the remaining sum has no $p$ in the denominator, the irreducible form of $\frac{1}{p}(1+\frac{1}{2}+\cdots +\frac{1}{n^{\prime }})$, too, should not have $p$ in the denominator). The number of good $n^{\prime }$ does not exceed ${\left(\frac{3}{2}{p}^{\frac{2}{3}}\right)}^{k-1}$ by the induction hypothesis. For each good $n^{\prime }$ we set $-r\equiv 1+\frac{1}{2}+\cdots +\frac{1}{n-c_0}$ (mod $p$); the sum of $c$ last terms in the sum $1+\frac{1}{2}+\cdots +\frac{1}{n}$ should be $r$ (mod $p$). By Claim 1, there are at most $\frac{3}{2}{p}^{\frac{2}{3}}$ such $c$, which gives the desired bound. Turning to the main claim, we choose an integer $k$ such that $p^{k-1}<N\le p^k$. The number of good numbers not exceeding $N$ is not greater than the number of good numbers not exceeding $p^k$, and this in its turn does not exceed $${\left(\frac{3}{2}{p}^{\frac{2}{3}}\right)}^k<{\left(200^{\frac{1}{12}}{p}^{\frac{2}{3}}\right)}^k={\left(p^{\frac{1}{12}}{p}^{\frac{2}{3}}\right)}^k=p^{\frac{3}{4}k}=p^{\frac{3}{4}}(p^{k-1}{)}^{\frac{3}{4}}<p^{\frac{3}{4}}{N}^{\frac{3}{4}},$$ which proves the desired claim for $C=p^{\frac{3}{4}}$ (here we use the inequality ${\left(\frac{3}{2}\right)}^{12}<200$).