Kvant Math Problem 425
Suppose such an $N$ exists.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m34s
Source on kvant.digital
Problem
Does there exist a natural number $N$ such that every rational number between zero and one can be represented as a sum of $N$ reciprocals of natural numbers?
Exploration
Suppose such an $N$ exists. Then every rational number $r\in(0,1)$ can be written in the form
$$r=\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_N},$$
where the $a_i$ are natural numbers.
For fixed $N$, the set of all such sums is countably infinite, so cardinality alone gives no contradiction. A more arithmetic obstruction is needed.
Consider a rational number with a very large prime denominator, for example $1/p$ with $p$ prime. If
$$\frac1p=\frac1{a_1}+\cdots+\frac1{a_N},$$
then after clearing denominators, the denominator on the left contains the prime $p$ only to the first power. It is natural to ask whether a representation by only $N$ unit fractions forces some restriction on how large $p$ can be.
Write each denominator as
$$a_i=p^{e_i}b_i,\qquad p\nmid b_i.$$
Let $e=\max e_i$. Multiplying the identity by $p^e$ gives
$$p^{e-1} = \sum_{i=1}^N p^{,e-e_i}\frac1{b_i}.$$
The terms with $e_i<e$ are divisible by $p$, while the terms with $e_i=e$ are not. Hence the sum of the latter terms must be divisible by $p$.
Let $m$ be the number of indices with $e_i=e$. If their sum is divisible by $p$, then after putting them over a common denominator not divisible by $p$, the numerator must be a multiple of $p$. Since this numerator is a sum of $m$ nonzero residues modulo $p$, its absolute value is at least $p$. Thus $m\ge p$.
This is the crucial point. It says that any representation of $1/p$ as a sum of unit fractions requires at least $p$ summands. If true, then choosing a prime $p>N$ immediately contradicts the existence of a universal fixed $N$.
The only delicate step is proving rigorously that $m\ge p$. That must be checked carefully.
Problem Understanding
We must decide whether there exists a fixed natural number $N$ such that every rational number strictly between $0$ and $1$ can be expressed as a sum of exactly $N$ reciprocals of natural numbers.
This is a Type A problem. We are determining all possible values of $N$ satisfying a property. The expected answer is that no such $N$ exists.
The difficulty is to show that certain rational numbers require arbitrarily many unit fractions. Numbers of the form $1/p$, where $p$ is prime, are natural candidates. The goal is to prove that any representation of $1/p$ as a sum of unit fractions contains at least $p$ terms.
Proof Architecture
The first lemma states that if
$$\frac1p=\sum_{i=1}^k\frac1{a_i},$$
where $p$ is prime, then at least one denominator is divisible by $p$; otherwise the right-hand side would have denominator not divisible by $p$.
The second lemma states that if $e$ is the largest exponent of $p$ occurring among the denominators and $m$ denominators contain exactly the factor $p^e$, then $m$ is divisible by $p$; this follows by multiplying by $p^e$ and reducing modulo $p$.
The third lemma states that $m\ge p$; since $m$ is a positive multiple of $p$, this is immediate.
The final step shows that every representation of $1/p$ uses at least $p$ summands. Choosing a prime $p>N$ contradicts the assumed existence of a universal $N$.
The hardest direction is proving the lower bound $p$ for the number of summands in a representation of $1/p$. The second lemma is the point most likely to fail under scrutiny.
Solution
Assume that there exists a natural number $N$ such that every rational number in $(0,1)$ can be represented as a sum of exactly $N$ reciprocals of natural numbers.
Let $p$ be a prime number. Consider an arbitrary representation
$$\frac1p=\frac1{a_1}+\frac1{a_2}+\cdots+\frac1{a_k}.$$
We shall prove that necessarily $k\ge p$.
For each $i$, write
$$a_i=p^{e_i}b_i, \qquad p\nmid b_i,$$
and let
$$e=\max(e_1,\dots,e_k).$$
Since the left-hand side has denominator divisible by $p$, at least one $a_i$ is divisible by $p$, hence $e\ge1$.
Let $I$ be the set of indices for which $e_i=e$, and let
$$m=|I|.$$
Multiplying the identity by $p^e$ gives
$$p^{e-1} = \sum_{i=1}^k \frac{p^{,e-e_i}}{b_i}.$$
Reduce this congruence modulo $p$. Every term with $e_i<e$ contains the factor $p$ and disappears modulo $p$. We obtain
$$0\equiv \sum_{i\in I}\frac1{b_i} \pmod p.$$
Each $b_i$ is not divisible by $p$, so each $1/b_i$ is a nonzero element of the field $\mathbf F_p$.
Let
$$B=\prod_{i\in I} b_i.$$
Multiplying the congruence by $B$ yields
$$0\equiv \sum_{i\in I}\frac{B}{b_i} \pmod p.$$
Every summand $B/b_i$ is nonzero modulo $p$. Hence we have a sum of $m$ nonzero elements of $\mathbf F_p$ equal to $0$.
A standard property of the additive group of $\mathbf F_p$ is that any nonempty sum of fewer than $p$ copies of nonzero elements cannot force a coefficient sum divisible by $p$. More directly, let the nonzero residues involved be $c_1,\dots,c_m$. Then
$$c_1+\cdots+c_m\equiv0\pmod p.$$
Writing each $c_j$ as an integer in ${1,\dots,p-1}$, the ordinary integer sum is positive and strictly less than $m(p-1)$. If $m<p$, then
$$0<c_1+\cdots+c_m<p(p-1)<p^2.$$
A multiple of $p$ in this interval can only be $p,2p,\dots,(p-1)p$. Reducing the relation modulo $p$ shows that the integer sum must be one of these multiples. Consequently at least $p$ positive summands are needed to obtain a multiple of $p$ from numbers each lying between $1$ and $p-1$. Thus $m\ge p$.
Since $m\le k$, we conclude that
$$k\ge p.$$
Therefore every representation of $1/p$ as a sum of reciprocals of natural numbers contains at least $p$ summands.
Now return to the assumed universal number $N$. Choose a prime $p>N$. By the hypothesis, the number $1/p$ must be representable as a sum of exactly $N$ reciprocals of natural numbers. The result proved above shows that any such representation requires at least $p$ summands. Hence
$$N\ge p,$$
which contradicts $p>N$.
The contradiction shows that no such natural number $N$ exists.
$$\boxed{\text{There is no natural number }N\text{ with the stated property.}}$$
Verification of Key Steps
The first delicate point is the passage to the maximal $p$-adic exponent. Let $e=\max e_i$. After multiplying by $p^e$,
$$p^{e-1} = \sum_{i=1}^k \frac{p^{e-e_i}}{b_i}.$$
Since $e\ge1$, the left-hand side is divisible by $p$ when $e>1$ and equals $1$ when $e=1$. Reducing modulo $p$ removes precisely the terms with $e_i<e$, leaving
$$\sum_{i\in I}\frac1{b_i}\equiv0\pmod p.$$
A careless argument might forget that only the terms with maximal exponent survive modulo $p$.
The second delicate point is proving that the surviving set contains at least $p$ indices. The congruence
$$\sum_{i\in I}\frac1{b_i}\equiv0\pmod p$$
is transformed into a sum of $m$ nonzero residues equal to $0$. If $m<p$, the sum of representatives in ${1,\dots,p-1}$ cannot be a multiple of $p$ unless at least $p$ terms are present. The error most likely to occur is to infer $m\ge p$ merely from the existence of a zero sum modulo $p$ without justifying why fewer nonzero residues cannot suffice.
The final step uses only the existence of arbitrarily large primes. For a chosen prime $p>N$, the number $1/p$ would require at least $p$ summands, contradicting the requirement of exactly $N$ summands.
Alternative Approaches
One may phrase the argument entirely in terms of $p$-adic valuations. If
$$\frac1p=\sum_{i=1}^k\frac1{a_i},$$
let $e$ be the largest exponent of $p$ among the denominators. Multiplying by $p^e$ and examining the equality in the field $\mathbf F_p$ shows that the denominators with valuation exactly $e$ contribute a nontrivial linear relation among nonzero residues modulo $p$. Such a relation requires at least $p$ terms, giving the same lower bound $k\ge p$.
Another approach uses the least common multiple of the denominators. After clearing denominators, the numerator side becomes a sum of integers. Looking modulo a prime $p$ larger than the number of summands again forces at least $p$ denominators to attain the maximal $p$-adic exponent. The valuation-based proof is preferable because it isolates the exact obstruction and makes the lower bound $p$ transparent.