Equation with divisors of positive integer

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Equation with divisors of positive integer

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2017 Belarus Team Selection Test 2.3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

184 posts

#1 h Mar 31, 2019, 5:50 PM • 1 Y

Y by Adventure10

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1400 posts

#5 h Mar 31, 2019, 9:52 PM • 2 Y

Y by Adventure10, Mango247

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$ ).

This post has been edited 1 time. Last edited by grupyorum, Apr 1, 2019, 4:08 PM
Reason: A slicker way of first part added.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

238 posts

#6 h Mar 31, 2019, 10:06 PM • 2 Y

Y by mathisreaI, Adventure10

See here https://artofproblemsolving.com/community/u363632h1740437p11311922

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a