Let $1=d_1<d_2<\ldots<d_k=n$ be all natural divisors of a natural number $n$. Find all possible values of $k$ if $n=d_2d_3+d_2d_5+d_3d_5$.
Problem
Source: 2017 Belarus Team Selection Test 2.3
Tags: number theory
01.04.2019 00:52
I claim that, the only possibility is either $k=9$ for $n=36$, or $k=8$, achieved for $n=pqr$, with $p<q<r$ are primes, where $r=p+q+1$; or $n=p^3(p^2+p+1)$, with $p^2+p+1$ prime, or $n=p^3q$ with $p<q<p^2$ primes. Note that $d_2=p$, where $p$ is the smallest prime dividing $n$. In particular, $p\mid d_3d_5$. Now, assume first that, $p\mid d_3$. In this case, $d_3=p^2$ must necessarily hold. Since $p^2\mid n$, we have $p^2\mid d_2d_5$, and thus, $p\mid d_5$. In particular, the first five divisors are, $1=d_1<p<p^2<d_4<d_5$. Check that, $d_5$ can have at most 2 distinct prime divisors. Now, first suppose $d_5=p^j$ for some $j$. If $j=3$, then $n=p^3(p^2+p+1)$, and $d_4$ is the smallest prime divisor of $p^2+p+1$. This is possible, only when, $p^2+p+1$ is a prime. Namely, $n=p^3(p^2+p+1)$, where $p^2+p+1$ is a prime. Similarly, if $j=4$, then $n=p^3(p^2+p^3+1)$, which is not divisible by $p^4$, contradiction. Thus, $d_5=p^a q^b$ for some $a,b\geq 1$. Now, if $p^2\mid d_5$, then both $pq^b$ and $q^b$ must appear as divisors smaller than $d_5$, yielding a contradiction. Thus, $p\mid \mid d_5$. Furthermore, if $d_5=pq^b$ with $b\geq 2$, then check again that, $q^b$ and $pq^{b-1}$ are all divisors of $n$, less than $d_5$, contradiction. Thus, $d_5=pq$, and hence, $n=p^2(p+pq+q)$. However, since $q\mid n$, we get $q\mid p+pq+q$, yielding $q\mid p$, a contradiction. Thus, no solutions. Edit: For this case, there is apparently a much slicker way of getting around. Notice, upon obtaining $d_3=p^2$ and $d_2=p$, by inspecting modulo $d_5$, we obtain that, $d_5\mid d_3d_2=p^3$, and thus, $d_5=p^3$ necessarily. This saves us substantial calculations. Now, suppose $p\nmid d_3$. Then $p\mid d_5$. Note also that, if $p^2\mid n_5$, then $p^2\mid d_2d_3$, and thus, $p\mid d_3$, contradicting with the assumption. Thus, $p\mid\mid d_5$. As above, the first five divisors of $n$ are, $1=d_1<p<d_3<d_4<d_5$. Now, if $d_5$ has $\geq 3$ distinct prime divisors, we have a contradiction. Hence, it has at most two distinct prime divisors, one of which is $p$, namely, $d_5=pq^b$ for some $b$. If $b\geq 2$, then check that, $q^{b-1},q^b,pq^{b-1}$ are all divisors of $n$, distinct from $1$ and $p$, and less than $d_5$, but we only have $d_3$ and $d_4$ in there, a contradiction. Hence, $b=1$. Thus, $d_5=pq$. Now, if $d_3\neq q$, then $d_3=r$ for some prime $r$, different from $p$ and $q$. But this gives a contradiction: $r\mid n\implies r\mid d_2d_3+d_2d_5+d_3d_5\implies r\mid d_2d_5=p^2q$. Hence, $d_3=q$. Then, $n=pq+p^2q+pq^2=pq(1+p+q)$. Now, if $p+q+1$ is a prime, we get $k=8$, and $n=pq(1+p+q)$, where $p<q$ and $p+q+1$ is a prime. Now, if $p+q+1$ is not a prime, then it has at least two divisors, other than $1$. Hence, either $p\mid p+q+1$ or $q\mid p+q+1$. In the latter case, $q\mid p+1$. Since $q\geq p+1$, it follows that, $p=2,q=3$, and $n=36$. If not, then $p\mid q+1$. Let $q+1=pt$ for some $t$. Observe that, $t<q$. Then, $p+q+1=p(t+1)$, and therefore, $n=p^2q(t+1)$. Now, note that, both $p^2,p(t+1),(t+1)$ are divisors, less than. $pq$. Hence, $d_4=p^2$ must hold. Furthermore, since $t+1<p(t+1)$, it must hold that, $t+1=p$ or $t+1=q$. If $t+1=q$, then we have $t+2=pt$, and thus, $t\mid 2$. This gives, $t\in\{1,2\}$, where $t=1$ is impossible, and $t=2$ implies $p=2,q=3$. Finally, $t+1=p$, and thus, $n=p^2q(t+1)=p^3q$, with $1<p<q<p^2<pq$ being first five divisors (forcing, also, $p^2>q$).
01.04.2019 01:06
See here https://artofproblemsolving.com/community/u363632h1740437p11311922