Difference between revisions of "2023 IMO Problems/Problem 1"

Latest revision as of 08:43, 4 August 2024

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

Video Solution

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

https://youtu.be/FBwvqDUEDFc?si=DYrxR9wI1YaKvDm- [Video contains IMO 2023 P1 motivation + discussion] (~little-fermat)

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)$ . But $\frac{n}{q}$ is divisible by $p$ , so $\frac{n}{p} + n$ must also be divisible by $p$ , but since $a=1$ $\frac{n}{p}$ is and $n$ isn't.

When $n=p^x$ , it is easy to verify this works for all primes $p$ and all $x\geq 2$ , since $p^y \vert p^{y+1} + p^{y+2}$ , and the divisors are ordered as ${1,\, p,\, p^2…\, p^x}$ .

~SpencerD,K kai

Solution 2

Similar argument as above but restated.

Let $n = p_1^{e_1} p_2^{d_2} \dots p_k^{e_k}$ , with $p_1 < p_2 < \dots < p_k$ primes.

If $k=1$ , it's easy to verify that this property holds, since $p^l \mid p^{l+1} + p^{l+2}$ .

Suppose $k \geq 2$ . All divisors of $n$ which contain a factor of $p_k$ for $k \geq 2$ is at least as large as $p_2$ . So, the only divisors which are possibly less than $p_2$ are of the form $p_1^{j}$ . Also, by construction $p_1$ is less than $p_2$ . Putting it all together, this says that the smallest factors are $(1, p_1, \dots, p_1^j, p_2)$ for some $j \geq 1$ .

If $j \geq 2$ , then $p_1^{j-1} \nmid p_1^j + p_2$ , since the LHS has a factor of $p_1$ and the RHS does not since.

If $j = 1$ , then the largest three factors are $(\frac{n}{p_2}, \frac{n}{p_1}, n)$ . But $\frac{n}{p_2}$ and $n$ have a factor of $p_1^{e_1}$ , while $\frac{n}{p_1}$ only has a factor of $p_1^{e_1 - 1}$ , so $\frac{n}{p_2} \nmid \frac{n}{p_1} + n$ .

Hence the prime powers are the only composite numbers which satisfy the property. ~kislay kai approved

@@ Line 17: / Line 17: @@
 When <math>n=p^x</math>, it is easy to verify this works for all primes <math>p</math> and all <math>x\geq 2</math>, since <math>p^y  \vert  p^{y+1} + p^{y+2}</math>, and the divisors are ordered as <math>{1,\, p,\, p^2…\, p^x}</math>.
-~SpencerD.
+~SpencerD,K kai
 ==Solution 2==

2023 IMO (Problems) • Resources
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search