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"
m (→‎Solution 1)
 
(10 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Determine all composite integers <math>n>1</math> that satisfy the following property: if <math>d_1,d_2,\dots,d_k</math> are all the positive divisors of <math>n</math> with <math>1=d_1<d_2<\dots<d_k=n</math>, then <math>d_i</math> divides <math>d_{i+1}+d_{i+2}</math> for every <math>1\le i \le k-2</math>.
 
Determine all composite integers <math>n>1</math> that satisfy the following property: if <math>d_1,d_2,\dots,d_k</math> are all the positive divisors of <math>n</math> with <math>1=d_1<d_2<\dots<d_k=n</math>, then <math>d_i</math> divides <math>d_{i+1}+d_{i+2}</math> for every <math>1\le i \le k-2</math>.
 +
 +
==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==
 
==Solution 1==
Line 7: Line 13:
 
To prove this claim, note that <math>p</math> is the smallest prime that divides <math>n</math>, so it is the smallest divisor not equal to <math>1</math>, meaning the first <math>2</math> divisors are <math>1</math> and <math>p</math>. Furthermore, the smallest divisor of <math>n</math> that is not equal to a power of <math>p</math> (i.e. not equal to <math>(1,\, p,\, p^2\dots)</math> is equal to <math>q</math>. This is because all other divisors either include a prime <math>z</math> different from both <math>q</math> and <math>p</math>, which is larger than <math>q</math> (since <math>q</math> and <math>p</math> are the smallest two prime divisors of <math>n</math>), or don’t include a different prime <math>z</math>. In the first case, since <math>z>q</math>, the divisor is larger than <math>q</math>. In the second case, all divisors divisible by <math>q^2</math> are also larger than <math>q</math>, and otherwise are of the form <math>p^x \cdot q^1</math> or <math>p^x</math> for some nonnegative integer <math>x</math>. If the divisor is of the form <math>p^x</math>, then it is a power of <math>p</math>. If it is of the form <math>p^x \cdot q^1</math>, the smallest of these factors is <math>p^0 \cdot q^1 = q</math>. Therefore, (in the case where <math>2</math> or more primes divide <math>n</math>) the ordered tuple of divisors is of the form <math>(1,\,  p,\,  p^2 \dots,\,  p^a,\,  q \dots,\,  n)</math> for some integer <math>a\geq 1</math>, since after each divisor <math>p^x</math>, the next smallest divisor is either <math>p^{x+1}</math> or simply <math>q</math>.  
 
To prove this claim, note that <math>p</math> is the smallest prime that divides <math>n</math>, so it is the smallest divisor not equal to <math>1</math>, meaning the first <math>2</math> divisors are <math>1</math> and <math>p</math>. Furthermore, the smallest divisor of <math>n</math> that is not equal to a power of <math>p</math> (i.e. not equal to <math>(1,\, p,\, p^2\dots)</math> is equal to <math>q</math>. This is because all other divisors either include a prime <math>z</math> different from both <math>q</math> and <math>p</math>, which is larger than <math>q</math> (since <math>q</math> and <math>p</math> are the smallest two prime divisors of <math>n</math>), or don’t include a different prime <math>z</math>. In the first case, since <math>z>q</math>, the divisor is larger than <math>q</math>. In the second case, all divisors divisible by <math>q^2</math> are also larger than <math>q</math>, and otherwise are of the form <math>p^x \cdot q^1</math> or <math>p^x</math> for some nonnegative integer <math>x</math>. If the divisor is of the form <math>p^x</math>, then it is a power of <math>p</math>. If it is of the form <math>p^x \cdot q^1</math>, the smallest of these factors is <math>p^0 \cdot q^1 = q</math>. Therefore, (in the case where <math>2</math> or more primes divide <math>n</math>) the ordered tuple of divisors is of the form <math>(1,\,  p,\,  p^2 \dots,\,  p^a,\,  q \dots,\,  n)</math> for some integer <math>a\geq 1</math>, since after each divisor <math>p^x</math>, the next smallest divisor is either <math>p^{x+1}</math> or simply <math>q</math>.  
  
−
If <math>a\geq 2</math>, the condition fails. This is because <math>p^{a-1} \nmid p^a + q</math>, since <math>p^a</math> is divisible by <math>p^{a-1}</math>, but <math>q</math> is not since it is a prime different from <math>p</math>. If <math>a=1</math>, then <math>p^{a-1}=p^0=1</math>, which does divide <math>q</math>. Therefore <math>a</math> must equal <math>1</math> for the condition to be satisfied in this case. However, we know that the ordered list of divisors satisfies <math>d_i \cdot d_{k+1-i}=n</math>, meaning since the first <math>3</math> divisors are <math>(1, p, q)</math>, then the last <math>3</math> divisors are <math>(\frac{n}{q}, \frac{n}{p}, n)</math>, so <math>(\frac{n}{q})</math> must divide <math>(\frac{n}{p} + n)</math>. The fraction <math>\frac{(\frac{n}{p} + n)}{(\frac{n}{q})} = \frac{(\frac{1}{p} + 1)}{(\frac{1}{q})} = (\frac{q}{p}) + q</math> which is clearly not an integer since <math>q</math> is an integer, but <math>\frac{q}{p}</math> is not an integer, so <math>(\frac{q}{p}) + q</math> is not an integer. Therefore the condition fails specifically for the final <math>3</math> divisors in the list in this case, meaning <math>n</math> can never have <math>2</math> or more prime divisors.  
+
If <math>a\geq 2</math>, the condition fails. This is because <math>p^{a-1} \nmid p^a + q</math>, since <math>p^a</math> is divisible by <math>p^{a-1}</math>, but <math>q</math> is not since it is a prime different from <math>p</math>. If <math>a=1</math>, then <math>p^{a-1}=p^0=1</math>, which does divide <math>q</math>. Therefore <math>a</math> must equal <math>1</math> for the condition to be satisfied in this case. However, we know that the ordered list of divisors satisfies <math>d_i \cdot d_{k+1-i}=n</math>, meaning since the first <math>3</math> divisors are <math>(1, p, q)</math>, then the last <math>3</math> divisors are <math>(\frac{n}{q}, \frac{n}{p}, n)</math>, so <math>(\frac{n}{q})</math> must divide <math>(\frac{n}{p} + n)</math>. But <math>\frac{n}{q}</math> is divisible by <math>p</math>, so <math>\frac{n}{p} + n</math> must also be divisible by <math>p</math>, but since <math>a=1</math> <math>\frac{n}{p}</math> is and <math>n</math> isn't.
 +
 
 +
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,K kai
  
−
When <math>n=p^x</math>, it is easy to verify this works for all primes <math>p</math> and all <math>x\geq 1</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>. The remaining case is when <math>n=1</math> (i.e <math>n</math> has no prime divisors), and this clearly works as well.
+
==Solution 2==
 +
Similar argument as above but restated.
  
−
~SpencerD.
+
Let <math>n = p_1^{e_1} p_2^{d_2} \dots p_k^{e_k}</math>, with <math>p_1 < p_2 < \dots < p_k</math> primes.  
  
−
==Video Solution==
+
If <math>k=1</math>, it's easy to verify that this property holds, since <math>p^l \mid p^{l+1} + p^{l+2}</math>.
−
https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]
+
 
 +
Suppose <math>k \geq 2</math>. All divisors of <math>n</math> which contain a factor of <math>p_k</math> for <math>k \geq 2</math> is at least as large as <math>p_2</math>. So, the only divisors which are possibly less than <math>p_2</math> are of the form  <math>p_1^{j}</math>. Also, by construction <math>p_1</math> is less than <math>p_2</math>. Putting it all together, this says that the smallest factors are <math>(1, p_1, \dots, p_1^j, p_2)</math> for some <math>j \geq 1</math>.
 +
 
 +
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 <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.
 +
~kislay kai approved
 +
 
 +
==See Also==
 +
 
 +
{{IMO box|year=2023|before=First Problem|num-a=2}}

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

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=224415"