Difference between revisions of "2023 IMO Problems/Problem 1"
m (→Solution 1) |
|||
(5 intermediate revisions by 2 users not shown) | |||
Line 13: | 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>. | + | 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>. | 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== | ||
+ | Similar argument as above but restated. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | 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== | ==See Also== | ||
{{IMO box|year=2023|before=First Problem|num-a=2}} | {{IMO box|year=2023|before=First Problem|num-a=2}} |
Latest revision as of 08:43, 4 August 2024
Problem
Determine all composite integers that satisfy the following property: if are all the positive divisors of with , then divides for every .
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 has at least prime divisors, WLOG let be the smallest two of these primes. Then the ordered tuple of divisors is of the form for some integer .
To prove this claim, note that is the smallest prime that divides , so it is the smallest divisor not equal to , meaning the first divisors are and . Furthermore, the smallest divisor of that is not equal to a power of (i.e. not equal to is equal to . This is because all other divisors either include a prime different from both and , which is larger than (since and are the smallest two prime divisors of ), or don’t include a different prime . In the first case, since , the divisor is larger than . In the second case, all divisors divisible by are also larger than , and otherwise are of the form or for some nonnegative integer . If the divisor is of the form , then it is a power of . If it is of the form , the smallest of these factors is . Therefore, (in the case where or more primes divide ) the ordered tuple of divisors is of the form for some integer , since after each divisor , the next smallest divisor is either or simply .
If , the condition fails. This is because , since is divisible by , but is not since it is a prime different from . If , then , which does divide . Therefore must equal for the condition to be satisfied in this case. However, we know that the ordered list of divisors satisfies , meaning since the first divisors are , then the last divisors are , so must divide . But is divisible by , so must also be divisible by , but since is and isn't.
When , it is easy to verify this works for all primes and all , since , and the divisors are ordered as .
~SpencerD,K kai
Solution 2
Similar argument as above but restated.
Let , with primes.
If , it's easy to verify that this property holds, since .
Suppose . All divisors of which contain a factor of for is at least as large as . So, the only divisors which are possibly less than are of the form . Also, by construction is less than . Putting it all together, this says that the smallest factors are for some .
If , then , since the LHS has a factor of and the RHS does not since.
If , then the largest three factors are . But and have a factor of , while only has a factor of , so .
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 |