Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2023 IMO Problems/Problem 1

Revision as of 12:07, 15 July 2023 by Spencerd. (talk | contribs)

Problem

Determine all composite integers $n>1$ that satisfy the following property: if $d_1,d_2,\dots,d_k$ are all the positive divisors of $n$ with $1=d_1<d_2<\dots<d_k=n$, then $d_i$ divides $d_{i+1}+d_{i+2}$ for every $1\le i \le k-2$.

Solution 1

If $n$ has at least $2$ prime divisors, WLOG let $p<q$ be the smallest two of these primes. Then the ordered tuple of divisors is of the form $(1,\, p,\, p^2 \dots,\, p^a,\, q \dots,\, n)$ for some integer $a\geq 1$.

To prove this claim, note that $p$ is the smallest prime that divides $n$, so it is the smallest divisor not equal to $1$, meaning the first $2$ divisors are $1$ and $p$. Furthermore, the smallest divisor of $n$ that is not equal to a power of $p$ (i.e. not equal to $(1,\, p,\, p^2\dots)$ is equal to $q$. This is because all other divisors either include a prime $z$ different from both $q$ and $p$, which is larger than $q$ (since $q$ and $p$ are the smallest two prime divisors of $n$), or don’t include a different prime $z$. In the first case, since $z>q$, the divisor is larger than $q$. In the second case, all divisors divisible by $q^2$ are also larger than $q$, and otherwise are of the form $p^x \cdot q^1$ or $p^x$ for some nonnegative integer $x$. If the divisor is of the form $p^x$, then it is a power of $p$. If it is of the form $p^x \cdot q^1$, the smallest of these factors is $p^0 \cdot q^1 = q$. Therefore, (in the case where $2$ or more primes divide $n$) the ordered tuple of divisors is of the form $(1,\, p,\, p^2 \dots,\, p^a,\, q \dots,\, n)$ for some integer $a\geq 1$, since after each divisor $p^x$, the next smallest divisor is either $p^{x+1}$ or simply $q$.

If $a\geq 2$, the condition fails. This is because $p^{a-1} \nmid p^a + q$, since $p^a$ is divisible by $p^{a-1}$, but $q$ is not since it is a prime different from $p$. If $a=1$, then $p^{a-1}=p^0=1$, which does divide $q$. Therefore $a$ must equal $1$ for the condition to be satisfied in this case. However, we know that the ordered list of divisors satisfies $d_i \cdot d_{k+1-i}=n$, meaning since the first $3$ divisors are $(1, p, q)$, then the last $3$ divisors are $(\frac{n}{q}, \frac{n}{p}, n)$, so $(\frac{n}{q})$ must divide $(\frac{n}{p} + n)$. The fraction $\frac{(\frac{n}{p} + n)}{(\frac{n}{q})} = \frac{(\frac{1}{p} + 1)}{(\frac{1}{q})} = (\frac{q}{p}) + q$ which is clearly not an integer since $q$ is an integer, but $\frac{q}{p}$ is not an integer, so $(\frac{q}{p}) + q$ is not an integer. Therefore the condition fails specifically for the final $3$ divisors in the list in this case, meaning $n$ can never have $2$ or more prime divisors.

When $n=p^x$, it is easy to verify this works for all primes $p$ and all $x\geq 1$, since $p^y \vert p^{y+1} + p^{y+2}$, and the divisors are ordered as ${1,\, p,\, p^2…\, p^x}$. The remaining case is when $n=1$ (i.e $n$ has no prime divisors), and this clearly works as well.


Video Solution

https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_IMO_Problems/Problem_1&oldid=195755"