Maths Olympiad Prep

Library / /3 of 4

Number theory Difficulty 6.9 National olympiad Prove it Silk Road Mathematics Competition

Let p>200p > 200 be a prime number. We call a positive integer nn good if pp divides the numerator of the irreducible fraction anbn=1+12++1n\frac{a_n}{b_n} = 1 + \frac{1}{2} + \cdots + \frac{1}{n}. Prove that for all large enough NN the number of good numbers not exceeding NN is not greater than CN34C N^{\frac{3}{4}}, where CC is a constant; possibly depends on pp.

Solution

We will use congruences modulo pp for fractions, writing abx(modp)\frac{a}{b} \equiv x \pmod{p} for b≢0(modp)b \not\equiv 0 \pmod{p} if bxa(modp)b x \equiv a \pmod{p}. A sum of such fractions is congruent to 0(modp)0 \pmod{p} if and only if pp 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 rr, the number of positive integers n<pn < p such that 1+12++1nr(modp)1 + \frac{1}{2} + \cdots + \frac{1}{n} \equiv r \pmod{p} is not greater than 32p23\frac{3}{2} p^{\frac{2}{3}}.
Let n1<n2<<ns+1n_1 < n_2 < \cdots < n_{s+1} be all such nn. Every integer kk appears at most k1k-1 times among the differences ni+1nin_{i+1} - n_i (since nin_i should be a root of the congruence
1x+1++1x+k0(modp) \frac{1}{x+1} + \cdots + \frac{1}{x+k} \equiv 0 \pmod{p}
having at most k1k-1 roots: its left-hand side becomes a polynomial of degree k1k-1 when multiplied by the denominator).
Consider the largest mm such that 1+2++(m1)=m(m1)2s1+2+\cdots+(m-1) = \frac{m(m-1)}{2} \le s. Then s<m(m+1)2s < \frac{m(m+1)}{2}. On the other hand, ns+1n1n_{s+1}-n_1 is the sum of ss differences ni+1nin_{i+1}-n_i, and
p>ns+1n112+23++(m1)m=m3m3. p > n_{s+1} - n_1 \ge 1 \cdot 2 + 2 \cdot 3 + \cdots + (m-1)m = \frac{m^3 - m}{3}.
If m3m \le 3, the number of nin_i, that is, s+1s+1, is not greater than 6=3282/3<32p2/36 = \frac{3}{2} \cdot 8^{2/3} < \frac{3}{2} p^{2/3}. And, for m>3m > 3 we have
s+1m(m+1)2<32(m3m3)2/3<32p2/3. 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(m3m3)2/3m(m+1) < 3 \left(\frac{m^3-m}{3}\right)^{2/3} follows from m3(m+1)3<3(m3m)2m^3(m+1)^3 < 3(m^3-m)^2, i.e., m2+m<3(m1)2m^2+m < 3(m-1)^2.)

Claim 2. The number of good nn less than pkp^k is not greater than (32p23)k\left(\frac{3}{2} p^{\frac{2}{3}}\right)^k.
This can be proved by induction on kk. The base case k=1k=1 is given by Claim 1 for r=0r=0. Note that for a good n=c+npn = c + n' p, 0c<p0 \le c < p, the number n=c1++ck1pk2n' = c_1 + \cdots + c_{k-1} p^{k-2} is also good. Indeed, in the sum 1+12++1n1 + \frac{1}{2} + \cdots + \frac{1}{n} all the terms with denominators divisible by pp make together 1p(1+12++1n)\frac{1}{p}(1 + \frac{1}{2} + \cdots + \frac{1}{n'}), and since the remaining sum has no pp in the denominator, the irreducible form of 1p(1+12++1n)\frac{1}{p}(1 + \frac{1}{2} + \cdots + \frac{1}{n'}), too, should not have pp in the denominator).
The number of good nn' does not exceed (32p23)k1\left(\frac{3}{2} p^{\frac{2}{3}}\right)^{k-1} by the induction hypothesis. For each good nn' we set r1+12++1nc0-r \equiv 1 + \frac{1}{2} + \cdots + \frac{1}{n-c_0} (mod pp); the sum of cc last terms in the sum 1+12++1n1 + \frac{1}{2} + \cdots + \frac{1}{n} should be rr (mod pp). By Claim 1, there are at most 32p23\frac{3}{2} p^{\frac{2}{3}} such cc, which gives the desired bound.
Turning to the main claim, we choose an integer kk such that pk1<Npkp^{k-1} < N \le p^k. The number of good numbers not exceeding NN is not greater than the number of good numbers not exceeding pkp^k, and this in its turn does not exceed
(32p23)k<(200112p23)k=(p112p23)k=p34k=p34(pk1)34<p34N34, \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=p34C = p^{\frac{3}{4}} (here we use the inequality (32)12<200\left(\frac{3}{2}\right)^{12} < 200).

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 and solution reproduced as published; topic and difficulty added by this site.