2023 IMO Problems/Problem 1
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.
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.
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 |