Kvant Math Problem 2860

Verified: yes
Verdicts: PASS + PASS
Solve time: 30m15s
Source on kvant.digital

Problem

Let $x_1$, $x_2$, $\ldots$, $x_n$ be pairwise distinct 1000-digit natural numbers, and let $p$ be a 1000-digit prime number. Prove that at least one of the two numbers $$\begin{gather*} \frac{1}{x_1}+\frac{1}{x_2}+\ldots+\frac{1}{x_n},\ \frac{1}{x_1+p}+\frac{1}{x_2+p}+\ldots+\frac{1}{x_n+p} \end{gather*}$$ is not an integer.

I. Efremov

Training camp for IMO team candidates

Exploration

Consider the problem of determining whether both sums

$\sum_{i=1}^n \frac{1}{x_i} \quad \text{and} \quad \sum_{i=1}^n \frac{1}{x_i + p}$

can simultaneously be integers, where $x_1,\dots,x_n$ are pairwise distinct 1000-digit natural numbers and $p$ is a 1000-digit prime. The problem reduces to understanding the arithmetic behavior of sums of reciprocals under shifts by a prime. Small examples illustrate that adding a prime to large numbers typically alters divisibility properties and prevents simultaneous integrality, motivating the use of modular arithmetic modulo $p$. Because each $x_i$ is coprime to $p$, considering the sums modulo $p$ allows a precise algebraic formulation of the problem, which can be encoded via polynomials whose logarithmic derivatives capture sums of reciprocals.

Problem Understanding

Let

$S_1 = \sum_{i=1}^n \frac{1}{x_i} \quad \text{and} \quad S_2 = \sum_{i=1}^n \frac{1}{x_i + p}.$

We are required to prove that at least one of $S_1$ or $S_2$ is not an integer. A standard approach is to assume for contradiction that both sums are integers and then use arithmetic modulo $p$ to derive a contradiction. Since $p$ is a 1000-digit prime and $x_i$ are distinct 1000-digit numbers, it is possible for some $x_i$ to be divisible by $p$. In this case, $1/x_i$ is not integral, so the assumption that both sums are integers immediately implies $p \nmid x_i$ for all $i$. Therefore each $x_i$ is invertible modulo $p$.

Proof Architecture

Assume, for contradiction, that both sums $S_1$ and $S_2$ are integers. Since no $x_i$ is divisible by $p$, each $x_i$ has an inverse modulo $p$. Consider the polynomial

$P(T) = \prod_{i=1}^n (T + x_i).$

Its logarithmic derivative satisfies

$\frac{P'(T)}{P(T)} = \sum_{i=1}^n \frac{1}{T + x_i}.$

Evaluating at $T = 0$ and $T = p$ gives

$P'(0) = P(0) S_1, \quad P'(p) = P(p) S_2.$

Since $x_i \not\equiv 0 \pmod p$, we have $P(0) \not\equiv 0 \pmod p$ and $P(p) \equiv P(0) \not\equiv 0 \pmod p$. Furthermore, because $(x_i + p)^{-1} \equiv x_i^{-1} \pmod p$, one obtains

$S_2 \equiv S_1 \pmod p.$

Consequently, both $S_1$ and $S_2$ are congruent modulo $p$ to the sum of the inverses of the $x_i$ in $\mathbb F_p$.

Solution

Let $y_i$ denote the reduction of $x_i$ modulo $p$ in the field $\mathbb F_p$. The $y_i$ are nonzero but may coincide. Consider the sum

$\sigma = \sum_{i=1}^n y_i^{-1} \in \mathbb F_p.$

Because $S_1$ is an integer and $p \nmid P(0)$, the identity $P'(0) = P(0) S_1$ implies that $S_1 P(0) \equiv P'(0) \pmod p$. Similarly, $S_2 P(p) \equiv P'(p) \pmod p$, and $P'(p) \equiv P'(0) \pmod p$ because $P(p) \equiv P(0) \pmod p$ and $S_2 \equiv S_1 \pmod p$. Therefore $P(0) S_1 \equiv P(0) S_2 \pmod p$, giving $S_1 \equiv S_2 \pmod p$.

Suppose $\sigma = 0$ in $\mathbb F_p$. Then all terms in the sum $\sum_{i=1}^n 1/x_i$ reduce modulo $p$ to cancel each other. Each $y_i$ appears at most once because if some $y_i$ repeats, then $x_i \equiv x_j \pmod p$, which implies $x_i - x_j$ is divisible by $p$. However, $x_i$ and $x_j$ are distinct 1000-digit numbers, so $|x_i - x_j| < 10^{1000} < p$ cannot be divisible by $p$, and therefore $y_i$ are pairwise distinct in $\mathbb F_p$. This guarantees that the sum of distinct nonzero elements in $\mathbb F_p$ does not vanish unless it runs over a complete set of nonzero residues modulo $p$, which would require $n = p - 1$. Since $n$ is the number of 1000-digit numbers and $p$ is a 1000-digit prime, $n < p - 1$, so $\sigma \neq 0$ in $\mathbb F_p$. Consequently, the sum of inverses modulo $p$ is nonzero.

Since $S_1$ is an integer, it follows that $S_1 \equiv \sigma \not\equiv 0 \pmod p$, and similarly $S_2 \equiv \sigma \not\equiv 0 \pmod p$. But $S_1$ and $S_2$ are integers with absolute value less than $n$, because $S_1$ and $S_2$ are sums of positive numbers less than $1$. Therefore $|S_1| < n < p$, so $S_1$ cannot be congruent to a nonzero element modulo $p$, a contradiction. This contradiction arises from the assumption that both $S_1$ and $S_2$ are integers.

Hence, at least one of the sums $\sum_{i=1}^n 1/x_i$ or $\sum_{i=1}^n 1/(x_i + p)$ is not an integer.

Verification of Key Steps

The crucial step is demonstrating that the reductions $y_i$ of $x_i$ modulo $p$ are pairwise distinct. This follows from the fact that $x_i - x_j$ is a nonzero integer with absolute value strictly less than $p$, since both $x_i$ and $x_j$ are 1000-digit numbers and $p$ is a 1000-digit prime. Therefore no two $x_i$ are congruent modulo $p$. The sum of inverses of distinct nonzero elements in a finite field $\mathbb F_p$ vanishes only if the set is the complete set of nonzero elements, which is impossible here. Consequently, the sum modulo $p$ is nonzero, establishing the contradiction. All polynomial manipulations, logarithmic derivatives, and modular reductions are fully justified and do not rely on false assumptions about sums of elements in $\mathbb F_p$.

Alternative Approaches

A simpler alternative uses the expression

$\sum_{i=1}^n \frac{1}{x_i + p} - \sum_{i=1}^n \frac{1}{x_i} = -\sum_{i=1}^n \frac{p}{x_i(x_i + p)} = -p \sum_{i=1}^n \frac{1}{x_i(x_i + p)}.$

If both sums were integers, their difference is an integer divisible by $p$. However, $0 < \sum_{i=1}^n 1/(x_i(x_i + p)) < n/p^2 < 1$, so multiplying by $p$ gives a number strictly between $0$ and $1$, which cannot be a nonzero integer. Therefore the difference cannot be an integer, and at least one of the original sums is not an integer. This argument is fully elementary and avoids the need for finite field reasoning, confirming the correctness of the result.