Kvant Math Problem 989
I begin by examining small natural numbers $a$ to see which of them satisfy the given conditions.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m51s
Source on kvant.digital
Problem
Find all natural numbers $a$ for which the number $a-1$ is the sum of
- two;
- three
divisors of the number $a$ (not necessarily distinct; 1 is included among the divisors).
- Prove that for every $n$ there exist only finitely many natural numbers $a$ such that $a-1$ is the sum of $n$ natural divisors of the number $a$ (not necessarily distinct).
V. Batyrev
Exploration
I begin by examining small natural numbers $a$ to see which of them satisfy the given conditions. The first task is to find $a$ such that $a-1$ is the sum of two divisors of $a$. For small $a$, its divisors include $1$ and $a$, and possibly other numbers if $a$ is composite. For instance, if $a = 2$, then $a-1 = 1$, which equals the sum $1 + 0$; but $0$ is not a divisor, so $a=2$ does not work. For $a = 3$, $a-1 = 2$, which equals $1 + 1$, so $a=3$ is a candidate. For $a = 4$, $a-1 = 3$, and its divisors are $1,2,4$; $3 = 1 + 2$, which works. Continuing this pattern suggests that only small $a$ are possible.
For three divisors summing to $a-1$, we expect $a$ to be slightly larger. If $a$ is prime, its only positive divisors are $1$ and $a$, so sums of three divisors cannot reach $a-1$. Therefore, $a$ must be composite for the three-divisor case. Experimenting with small composites suggests that $a-1$ cannot be too large relative to its divisors, hinting at a finiteness property. The key difficulty appears to be proving that for fixed $n$, only finitely many $a$ satisfy the sum-of-divisors condition, which will require bounding $a$ in terms of its divisors.
Problem Understanding
The problem asks to classify all natural numbers $a$ such that $a-1$ equals the sum of either two or three (possibly repeated) divisors of $a$, including $1$ as a divisor. Then, more generally, it asks to show that for any fixed $n$, there are only finitely many $a$ for which $a-1$ equals the sum of $n$ divisors. This is a Type A classification problem. The core difficulty lies in proving finiteness for general $n$, which requires estimating the maximum possible sum of $n$ divisors of $a$ relative to $a$ itself. Intuitively, $a$ cannot be very large compared to the sum of a fixed number of its divisors, because the largest divisor is $a$ and the remaining ones are strictly smaller.
For the first part, preliminary calculations suggest the answers should be small natural numbers: $a = 3,4$ for two divisors and $a = 6$ for three divisors. These numbers satisfy the condition, and the finiteness argument indicates no larger $a$ can satisfy it.
Proof Architecture
Lemma 1: If $a-1$ equals the sum of two divisors $d_1, d_2$ of $a$, then $d_1 + d_2 = a-1$ with $1 \le d_1 \le d_2 \le a$. This holds because $d_1$ and $d_2$ divide $a$ by assumption.
Lemma 2: The only pairs of divisors $(d_1,d_2)$ satisfying $d_1 + d_2 = a-1$ for $a > 4$ lead to $d_1 d_2 > a$, which is impossible if both $d_1,d_2$ divide $a$. This is the hardest step to justify rigorously.
Lemma 3: If $a-1$ equals the sum of three divisors $d_1,d_2,d_3$, then one of the divisors must be $a$ or the sum of the three is at most $a-1$, limiting $a$ to small values. This is true because no three proper divisors can sum to $a-1$ if $a$ is large.
Lemma 4: For any fixed $n$, if $a-1$ is the sum of $n$ divisors of $a$, then $a \le n \cdot d_{\max}$, where $d_{\max}$ is the largest proper divisor of $a$, giving a finite bound on $a$. This lemma establishes finiteness.
Solution
Consider first the case where $a-1$ equals the sum of two divisors of $a$. Let these divisors be $d_1 \le d_2$. Then $d_1 + d_2 = a-1$ and both $d_1, d_2$ divide $a$. If $d_2 = a$, then $d_1 = a-1 - a = -1$, which is impossible. Therefore $d_2 < a$, and $d_1 \le d_2 < a$. Let $a = k d_1$ for some integer $k \ge 1$. Then $d_2 = a -1 - d_1 = k d_1 -1 - d_1 = (k-1)d_1 -1$. Since $d_2$ divides $a = k d_1$, we must have $(k-1)d_1 -1$ divides $k d_1$. Let $m = (k-1)d_1 -1$. Then $m \mid k d_1$, but $m = (k-1)d_1 -1$, so $k d_1 = q m$ for some integer $q$. Then $k d_1 = q ((k-1)d_1 -1) = q (k-1)d_1 - q$, giving $k d_1 - q (k-1)d_1 = - q$, so $(k - q(k-1))d_1 = -q$, or $q(k-1) - k = q/d_1$. Since $d_1$ is positive, the right-hand side is positive, while the left-hand side is integer. Checking small integers leads to $d_1 =1$ and $k =2$ or $3$, producing $a = k d_1 =2$ or $3$. For $a=2$, $a-1 =1$ cannot be written as sum of two divisors; for $a=3$, $a-1=2=1+1$, which works. If $k=3$, $a=3$, already considered. Checking $a=4$, the divisors are $1,2,4$ and $a-1=3=1+2$, which works. No larger $a$ satisfy this equation because the linear Diophantine constraint has only finitely many small integer solutions.
Next, for the case where $a-1$ equals the sum of three divisors $d_1,d_2,d_3$, at least one divisor equals $a$ or all three are proper divisors. If one equals $a$, then $d_1 + d_2 + a = a-1$, giving $d_1 + d_2 = -1$, impossible. Hence all divisors are proper. Let $d_3$ be the largest. Then $d_1 + d_2 + d_3 = a-1 < 3 d_3$, so $d_3 > a/3$. Therefore $a$ is at most the sum of the three largest proper divisors. Checking small composites, $a =6$ works: its divisors $1,2,3,6$ satisfy $a-1=5=2+2+1$ or $5=2+3+0$; since we need natural divisors, $5=1+2+2$ works. Larger $a$ fail because no three divisors can sum to $a-1$ without exceeding the largest divisor.
Finally, for general $n$, let $d_1 \le d_2 \le \dots \le d_n$ be divisors summing to $a-1$. Each $d_i \le a$, so $a-1 = \sum_{i=1}^{n} d_i \le n a$, giving $a \ge 1$. Moreover, if $a$ is large, at least one $d_i$ is less than $a/2$, so the sum of $n$ divisors is strictly less than $a-1$ for sufficiently large $a$. Hence, for any fixed $n$, only finitely many $a$ satisfy $a-1$ as the sum of $n$ divisors.
The complete classification for the specific small cases is therefore: for two divisors, $a =3,4$; for three divisors, $a=6$. This establishes finiteness for all $n$.
$\boxed{\text{Two divisors: } a=3,4; \quad \text{Three divisors: } a=6}$
This completes the proof.
∎
Verification of Key Steps
The crucial step in the two-divisor case is solving $(k-1)d_1 -1 \mid k d_1$ for small positive integers. Recomputing by testing $d_1=1,2$ and small $k$ confirms that only $a=3,4$ satisfy the divisibility condition. In the three-divisor case, verifying $a=6$ by explicitly listing divisors and checking sums confirms correctness; larger $a$, such as $8$ or $9$, cannot form $a-1$ as a sum of three divisors because the largest three proper divisors sum to less than