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

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

(→‎Solution 1)
(→‎Solution 2)
 
Line 30: Line 30:
 
If <math>j \geq 2</math>, then <math>p_1^{j-1} \nmid p_1^j + p_2</math>, since the LHS has a factor of <math>p_1</math> and the RHS does not since.
 
If <math>j \geq 2</math>, then <math>p_1^{j-1} \nmid p_1^j + p_2</math>, since the LHS has a factor of <math>p_1</math> and the RHS does not since.
  
−
If <math>j = 1</math>, then the largest three factors are <math>(\frac{n}{p_2}, \frac{n}{p_1}, n)</math>. But <math>\frac{n}{p_2}</math> and <math>n</math> have a factor of <math>p_1^{e_1}</math>, while \frac{n}{p_1}<math> only has a factor of </math>p_1^{e_1 - 1}<math>, so </math>\frac{n}{p_2} \nmid \frac{n}{p_1} + n$.
+
If <math>j = 1</math>, then the largest three factors are <math>(\frac{n}{p_2}, \frac{n}{p_1}, n)</math>. But <math>\frac{n}{p_2}</math> and <math>n</math> have a factor of <math>p_1^{e_1}</math>, while <math>\frac{n}{p_1}</math> only has a factor of <math>p_1^{e_1 - 1}</math>, so <math>\frac{n}{p_2} \nmid \frac{n}{p_1} + n</math>.
  
 
Hence the prime powers are the only composite numbers which satisfy the property.
 
Hence the prime powers are the only composite numbers which satisfy the property.

Latest revision as of 12:44, 16 December 2023

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.

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.

See Also

2023 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_IMO_Problems/Problem_1&oldid=207721"