For a positive integer $n$ consider all its divisors $1 = d_1 < d_2 < \ldots < d_k = n$. For $2 \le i \le k-1$, let's call divisor $d_i$ good, if $d_{i-1}d_{i+1}$ isn't divisible by $d_i$. Find all $n$, such that the number of their good divisors is smaller than the number of their prime distinct divisors. Proposed by Mykhailo Shtandenko
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 2, Problem 11.7
Tags: number theory
06.04.2023 17:15
The answer is $n=1$, prime powers, and $n=p^aq$ with $q>p^a$, $p,q$ are primes, and $a \geq 1$. It is clear that the first two work. We first prove the working $n$ with two prime divisors are precisely those given. If $q<p^a$ then there exists some $i$ with $d_i=p^k$ for some $1 \leq k<a$, and then $d_{i+1}=q$, so $d_{i-1}=p^{k-1}$ and $d_i$ is good. Then $d_{i+2}=p^{k+1}$, so $d_{i+1}$ is good as well. On the other hand, if $q>p^a$, then the divisors of $n$ are $1,\ldots,p^a,q,\ldots,qp^a,q^2,\ldots,q^2p^a,\ldots,q^b,\ldots,q^bp^a$ in that order. It is clear that each $q^ip^a$ divisor for $0 \leq i \leq b$ is good, so we need $b=1$ which on the other hand clearly works. Henceforth suppose that $n$ has at least $3$ prime divisors and let them be $p_1<\cdots<p_k$; also let $e\geq 1$ be $\nu_{p_1}(n)$. The following claim will provide $k$ good divisors, resolving the problem. Claim: For each $i$ (possibly equaling $1$) there exists some $m\geq 0$ such that $p_1^mp_i$ is good. Proof: Suppose otherwise. Let $d_j=p_i$, so $d_{j-1} \perp d_j$, and we must have $p_i \mid d_{j+1}$, so in fact $d_{j+1}=p_1p_i$. If $d_{j+1}$ is not good, then we need $p_1 \mid d_{j+2}$, so $d_{j+2}=p_1a$ for some $a>p_i$. On the other hand, if $a>p_1p_i$, then the divisor $a$ comes between $d_{j+1}$ and $d_{j+2}$, and if $a<p_1p_i$, then $a$ comes between $d_j$ and $d_{j+1}$, so in fact $a=p_1p_i \implies d_{j+2}=p_1^2p_i$. Then $p_1$ must divide $d_{j+3}$ as well, so we apply the same logic and get $d_{j+3}=p_1^3p_i$, and so on. But then $d_{j+e+1}$ must equal $p_1^{e+1}p_i$, which doesn't divide $n$: contradiction. $\blacksquare$ An important fact used implicitly in the proof: the divisors that we look at will never equal $n$, since they are divisible by at most $2$ distinct primes ($p_1$ and $p_i$): this is why we have to check the other cases separately, since if it turns out that, say, $d_{j+2}=n$, we run into issues because $d_{j+2}$ not being good is always true and we can no longer restrict the next divisor.
06.04.2023 18:47
For another construction, the divisor before each prime divisor is good. This way, we have $k-1$ good numbers so there aren't any more. Also, if we divide $d_i$ and $d_{i+1}$ by their gcd the resulting numbers are also consecutive divisors, where the first is good. This gives that Claim: After $p_k$, every divisor is divisible by $p_k$. Proof: Suppose not and let $d_t$ be the first time it happens (so $p_k\mid d_{t-1}$ but $p_k\nmid d_t$). Divide out by gcd and we'll get a good number greater than $p_k$, a contradiction. This way we naturally sort them and create at least $2$ "classes" by $v_{p_k}$ where each class has $k-1$ good divisors.