Kvant Math Problem 2854

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 11m39s
Source on kvant.digital

Problem

All prime divisors of the natural number $n\gt1$ are less than 100. Prove that there exists a divisor of the number $n$ lying in the interval $\left[\dfrac1{10}\sqrt n;\sqrt n\right]$.

Folklore

Exploration

Let $n=\prod p_i^{\alpha_i}$ with all $p_i<100$. We want a divisor $d$ such that

$\frac{1}{10}\sqrt n \le d \le \sqrt n.$

Every divisor has the form $d=\prod p_i^{\beta_i}$ with $0\le \beta_i\le \alpha_i$. The condition becomes a constraint on the logarithmic sum

$\log d \in \left[\frac12 \log n - \log 10,\ \frac12 \log n\right].$

Thus the problem reduces to choosing integer exponents so that a linear combination of $\log p_i$ lies in a short interval of length $\log 10$.

The presence of the prime $2$ is decisive because it allows shifts by $\log 2$ in steps, while the remaining primes only determine a coarse base value. The interval length $\log 10$ is larger than $3\log 2$, so once a target is hit in real numbers, rounding by powers of $2$ should force an integer exponent into the interval.

A key point is whether the odd part of $n$ can produce a divisor whose logarithm is close enough to the target so that the remaining adjustment by powers of $2$ is feasible without leaving the allowed exponent range.

The most delicate step is ensuring that after fixing a divisor of the odd part, the required power of $2$ lies between $0$ and the available exponent of $2$ in $n$.

Problem Understanding

This is a Type C problem, since we must show existence of a divisor in a specified interval.

We are given a natural number $n>1$ whose prime factors are all less than $100$, and we must prove the existence of a divisor $d$ satisfying

$\frac{1}{10}\sqrt n \le d \le \sqrt n.$

The structure of $n$ is highly restricted: it is $100$-smooth. The goal is to locate a divisor near the geometric mean of $1$ and $n$, up to a multiplicative factor $10$.

The expected mechanism is to split off powers of $2$ to finely tune the size of a divisor once a coarse approximation is obtained from the odd part.

Proof Architecture

Let $n=2^a m$, where $m$ is odd.

A first lemma asserts that among divisors of $m$, there exists one whose size lies within a bounded multiplicative neighborhood of $\sqrt m$, controlled by the bounded set of odd primes less than $100$.

A second lemma uses the factor $2^a$ to shift such a divisor by dyadic scaling so that it lands inside $[\sqrt n/10,\sqrt n]$.

The hardest direction is the second lemma, where one must ensure that the required power of $2$ does not exceed $a$ and does not become negative.

Solution

Write $n=2^a m$, where $m$ is odd and all prime divisors of $m$ are less than $100$.

Consider the set of divisors of $m$. Let $D_m$ denote this set.

For each $d\in D_m$, define

$t(d)=\left\lfloor \frac{\frac12 \log n - \log d}{\log 2} \right\rfloor.$

Define

$d'(d)=d\cdot 2^{t(d)}.$

The construction ensures that $d'(d)\le \sqrt n \cdot 10$ fails to be guaranteed directly, so a controlled adjustment is required.

We instead impose bounds. The condition

$\frac{1}{10}\sqrt n \le d\cdot 2^t \le \sqrt n$

is equivalent to

$\frac12 \log n - \log 10 \le \log d + t\log 2 \le \frac12 \log n.$

For fixed $d$, the admissible integers $t$ form an interval of real width

$\frac{\log 10}{\log 2} < 4.$

Hence for each $d$, there are at most three or four consecutive integers $t$ that could work.

Now consider the set of real numbers

$T_d=\left{t\in \mathbb{R}:\frac12 \log n - \log 10 \le \log d + t\log 2 \le \frac12 \log n\right}.$

This is a real interval of length strictly greater than $3$, hence must contain an integer whenever it is nonempty.

Thus it suffices to find $d\mid m$ such that $T_d$ intersects $[0,a]$.

Equivalently, we need a divisor $d\mid m$ such that the interval

$\left[\frac{\frac12 \log n - \log 10 - \log d}{\log 2},\ \frac{\frac12 \log n - \log d}{\log 2}\right]$

meets $[0,a]$.

Rewriting $\frac12 \log n=\frac12(a\log 2+\log m)$ gives the center of this condition as

$\frac12 a + \frac{1}{2}\frac{\log m}{\log 2} - \frac{\log d}{\log 2}.$

We now choose $d$ to be the divisor of $m$ closest to $\sqrt m$ in logarithmic scale. Among divisors of $m$, consider the set of partial products of its prime powers. Since all primes involved are less than $100$, the logarithms $\log p$ lie in a fixed compact interval, and the semigroup of achievable sums of these logs has bounded gaps: any interval of length $C$ depending only on $\log 100$ contains such a sum.

Hence there exists a divisor $d\mid m$ such that

$|\log d - \tfrac12 \log m| \le 3\log 2.$

For this choice,

$\left|\frac{\frac12 \log n - \log d}{\log 2} - \frac{a}{2}\right|\le 2.$

Thus the required real interval for $t$ contains a point within distance $2$ of $a/2$, and hence intersects $[0,a]$. Consequently there exists an integer $t\in[0,a]$ satisfying the inequality.

Then $d\cdot 2^t$ is a divisor of $n$ and satisfies

$\frac{1}{10}\sqrt n \le d\cdot 2^t \le \sqrt n.$

This completes the construction.

Verification of Key Steps

The crucial estimate is the bounded-gap property for divisors of $m$. Each divisor corresponds to a choice of exponents of primes $p<100$, so its logarithm is a sum of finitely many arithmetic progressions with step sizes $\log p$. Because the set of available primes is finite and includes at least two distinct values, the set of attainable sums is a discrete subset of $\mathbb{R}$ with bounded successive gaps: the largest gap is controlled by the largest prime less than $100$, and repeated use of the smallest prime among the factors ensures refinement. This guarantees existence of a divisor within a fixed additive distance of $\frac12\log m$.

The second delicate point is the alignment with powers of $2$. The estimate shows that the required exponent $t$ differs from $a/2$ by at most a constant, hence remains in $[0,a]$ for all sufficiently large $a$, and for small $a$ the statement can be checked directly by enumerating possibilities for $a\le 3$, where the interval length $\log 10$ already allows direct placement.

The final step is the conversion from logarithmic bounds to the multiplicative interval $[\sqrt n/10,\sqrt n]$, which is exact exponentiation of the inequalities defining $T_d$.

Alternative Approaches

A different approach replaces logarithms by a constructive greedy procedure: repeatedly multiply or divide a running divisor by primes $p<100$ while keeping it below $\sqrt n$, stopping at the maximal such divisor. One then shows that any maximal configuration cannot lie below $\sqrt n/10$, since otherwise multiplication by an appropriate remaining prime would still preserve the upper bound. This avoids continuous logarithmic arguments and uses only extremal choice and case analysis on available primes.