Kvant Math Problem 997
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m43s
Source on kvant.digital
Problem
Prove that the sum of all numbers of the form $\dfrac1{mn}$, where $m$ and $n$ are natural numbers, $1\le m\lt n\lt1986$, is not an integer.
D. A. Mitkin
Exploration
Let
$$S=\sum_{1\le m<n<1986}\frac1{mn}.$$
A direct evaluation is unnecessary; the task is only to prove that $S$ is not an integer.
It is useful to rewrite the sum. Since
$$\left(\sum_{k=1}^{1985}\frac1k\right)^2 = \sum_{k=1}^{1985}\frac1{k^2} + 2\sum_{1\le m<n<1985}\frac1{mn},$$
we have
$$S=\frac12\left(H_{1985}^2-\sum_{k=1}^{1985}\frac1{k^2}\right),$$
where $H_{1985}$ is the harmonic sum. This identity does not immediately reveal integrality.
A more promising approach is to examine the denominator structure. Let $p$ be a prime with
$$993<p<1986.$$
There are many such primes. For such a prime, every multiple of $p$ below $1986$ is just $p$ itself. Hence in the whole sum, the only terms whose denominators are divisible by $p$ are
$$\frac1{pk},\qquad 1\le k<p.$$
If all these terms are added together, we obtain
$$\frac1p\sum_{k=1}^{p-1}\frac1k.$$
The crucial question is whether this contribution is nonzero modulo $p$ after all fractions are expressed with denominators not divisible by $p$.
For a prime $p$,
$$\sum_{k=1}^{p-1}\frac1k\equiv 0 \pmod p,$$
because $k^{-1}+(p-k)^{-1}\equiv0\pmod p$. Thus the first-order $1/p$ contribution disappears. To decide integrality, one must look modulo $p^2$.
A stronger congruence is known:
$$\sum_{k=1}^{p-1}\frac1k\equiv0\pmod{p^2} \qquad (p\ge5),$$
which is Wolstenholme's theorem. If we use it, the contribution of the terms containing $p$ becomes divisible by $p$ and does not help.
A different idea is needed.
Take the largest prime below $1986$. Since
$$1986=2\cdot 993,$$
any prime $p$ with $1986/2<p<1986$ occurs in exactly one denominator factor. Let us choose such a prime and inspect the sum modulo $p$. Writing all terms over a common denominator not divisible by $p$ except for a single factor $p$, the coefficient of $1/p$ is
$$A=\sum_{k=1}^{p-1}\frac1k.$$
Modulo $p$, $A\equiv0$, so again cancellation occurs.
The hidden point is that among primes in $(1986/3,1986/2)$ there are exactly two multiples below $1986$, namely $p$ and $2p$. Then the terms involving $p$ can be analyzed more finely. This suggests using a prime for which there are exactly two multiples.
Take $p=661$. It is prime and
$$\frac{1986}{3}=662.$$
A better choice is the prime $997$, since
$$993<997<1986.$$
Then $997$ appears only once. The coefficient modulo $997$ vanishes, so one should examine the numerator after reducing to lowest terms. Wolstenholme gives divisibility by $997^2$, which means all terms involving $997$ together equal $B/997$ with $997\mid B$. Hence they contribute an integer modulo $997$ and do not obstruct integrality.
This route is not fruitful.
Instead, choose the prime $p=661$. Since
$$661<993,\qquad 3\cdot661=1983<1986,$$
the multiples of $661$ below $1986$ are $661,1322,1983$.
Terms with denominator divisible by $661$ arise from these three numbers. Modulo $661$, the reciprocals of $1322$ and $1983$ correspond to $2^{-1}$ and $3^{-1}$. The coefficient of $1/661$ becomes
$$\sum_{k=1}^{660}\frac1k+\frac12\sum_{k\ne661,1322}\frac1k+\frac13\sum_{k\ne661,1983}\frac1k.$$
Reducing modulo $661$ and using
$$\sum_{a=1}^{660}a^{-1}\equiv0\pmod{661},$$
the coefficient turns into a nonzero multiple of
$$1+\frac12+\frac13=\frac{11}{6},$$
which is nonzero modulo $661$. Hence the whole sum has denominator divisible by $661$, and cannot be an integer. This is the key insight.
Problem Understanding
We must prove that
$$S=\sum_{1\le m<n<1986}\frac1{mn}$$
is not an integer.
This is a Type B problem. The statement to be proved is that the given rational number is nonintegral.
The core difficulty is to detect a prime that survives in the denominator after all cancellations among the many fractions. The natural strategy is to isolate the contribution of a carefully chosen prime and show that its coefficient is nonzero modulo that prime.
Proof Architecture
Let $p=661$.
First, determine all multiples of $p$ less than $1986$, namely $p,2p,3p$.
Next, separate $S$ into the sum of terms whose denominator is divisible by $p$ and the sum of all remaining terms.
Show that the part whose denominator is divisible by $p$ can be written as $A/p$, where the denominator of $A$ is not divisible by $p$.
Compute $A$ modulo $p$ by replacing every denominator not divisible by $p$ with its inverse modulo $p$.
Use the congruence
$$\sum_{k=1}^{p-1}k^{-1}\equiv0\pmod p$$
to simplify the expression for $A$ modulo $p$.
Prove that
$$A\equiv \frac{11}{6}\sum_{k=1}^{660}k^{-1}\pmod p$$
and hence
$$A\equiv-\frac{11}{6}\left(1+\frac12+\frac13\right)\not\equiv0\pmod p.$$
Conclude that the whole sum has denominator divisible by $p$, so it cannot be an integer.
The most delicate point is the computation of $A$ modulo $p$ and the verification that the resulting residue is nonzero.
Solution
Let
$$S=\sum_{1\le m<n<1986}\frac1{mn}.$$
Take the prime
$$p=661.$$
Since
$$661<1986<4\cdot661,$$
the positive multiples of $p$ smaller than $1986$ are precisely
$$p,\quad 2p,\quad 3p.$$
Write
$$S=T+U,$$
where $T$ is the sum of all terms $\frac1{mn}$ for which at least one of $m,n$ is divisible by $p$, and $U$ is the sum of all remaining terms.
Every denominator occurring in $U$ is relatively prime to $p$, so $U$ can be written as a fraction whose denominator is not divisible by $p$.
We now examine $T$. Since only $p,2p,3p$ are divisible by $p$, we have
$$T= \frac1p\sum_{k=1}^{660}\frac1k + \frac1{2p}\sum_{\substack{1\le k<1986\k\ne661,1322}}\frac1k + \frac1{3p}\sum_{\substack{1\le k<1986\k\ne661,1983}}\frac1k.$$
Hence
$$T=\frac{A}{p},$$
where
$$A= \sum_{k=1}^{660}\frac1k + \frac12\sum_{\substack{1\le k<1986\k\ne661,1322}}\frac1k + \frac13\sum_{\substack{1\le k<1986\k\ne661,1983}}\frac1k .$$
The denominator of $A$ is not divisible by $p$.
To determine $A$ modulo $p$, every denominator not divisible by $p$ may be replaced by its inverse modulo $p$.
For each residue class $r\in{1,\dots,660}$ there are exactly three integers below $1986$ congruent to $r$ modulo $p$, namely
$$r,\quad r+p,\quad r+2p.$$
Consequently,
$$\sum_{\substack{1\le k<1986\k\ne661,1322}}\frac1k \equiv 3\sum_{r=1}^{660}\frac1r-\frac13 \pmod p,$$
because the omitted number $1983=3p$ contributes residue $3^{-1}$ modulo $p$.
Similarly,
$$\sum_{\substack{1\le k<1986\k\ne661,1983}}\frac1k \equiv 3\sum_{r=1}^{660}\frac1r-\frac12 \pmod p,$$
because the omitted number $1322=2p$ contributes residue $2^{-1}$ modulo $p$.
Let
$$H=\sum_{r=1}^{660}\frac1r .$$
Then
$$A\equiv H+\frac12\left(3H-\frac13\right) +\frac13\left(3H-\frac12\right) = \frac72,H-\frac13 \pmod p.$$
Now
$$H\equiv\sum_{r=1}^{660}r^{-1}\pmod p.$$
Since the map $r\mapsto r^{-1}$ permutes the nonzero residues modulo $p$,
$$H\equiv\sum_{r=1}^{660}r =\frac{660\cdot661}{2} \equiv0\pmod p.$$
Therefore
$$A\equiv-\frac13\pmod p.$$
Since $p=661$ does not divide $3$,
$$A\not\equiv0\pmod p.$$
Thus $T=A/p$ has numerator not divisible by $p$ when written in lowest terms, while $U$ has denominator not divisible by $p$.
Adding $T$ and $U$, the resulting fraction $S$ still has denominator divisible by $p$. Hence $S$ cannot be an integer.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the description of the multiples of $661$ below $1986$. Since
$$3\cdot661=1983<1986, \qquad 4\cdot661=2644>1986,$$
the only multiples are $661,1322,1983$. Missing one of these would change the coefficient computation.
The second delicate point is the congruence
$$\sum_{\substack{1\le k<1986\k\ne661,1322}}\frac1k \equiv 3H-\frac13 \pmod p.$$
For every residue $r\not\equiv0\pmod p$, the numbers $r,r+p,r+2p$ all contribute the same inverse $r^{-1}$ modulo $p$. Summing over all residues gives $3H$. The omitted value $1983=3p$ corresponds to residue class $3$, whose contribution would have been $3^{-1}$. Hence subtracting $1/3$ is correct.
The third delicate point is the evaluation of $H$ modulo $p$. The identity
$$H\equiv\sum_{r=1}^{660}r^{-1}$$
does not by itself give zero. One must use that inversion permutes the nonzero residues modulo $p$, so
$$\sum_{r=1}^{660}r^{-1} = \sum_{r=1}^{660}r = \frac{660\cdot661}{2} \equiv0\pmod{661}.$$
Substituting this value yields
$$A\equiv-\frac13\not\equiv0\pmod{661},$$
which is the decisive nonvanishing.
Alternative Approaches
One can use a more general theorem of Kürschák. If a finite set of distinct positive integers is given, the sum of their reciprocals is never an integer. After rewriting
$$\sum_{1\le m<n<1986}\frac1{mn} = \frac12\left(\left(\sum_{k=1}^{1985}\frac1k\right)^2-\sum_{k=1}^{1985}\frac1{k^2}\right),$$
the problem can be reduced to studying a suitable reciprocal sum and applying a prime divisor argument of the same flavor as Kürschák's proof.
Another route is to work $661$-adically from the beginning. One separates all terms according to the exact power of $661$ appearing in the denominator and computes the valuation of the whole sum. The argument above is preferable because it requires only elementary modular arithmetic and a single carefully chosen prime.