Difference between revisions of "2023 IMO Problems/Problem 1"
(→Video Solution) |
|||
Line 18: | Line 18: | ||
~SpencerD. | ~SpencerD. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2023|before=First Problem|num-a=2}} |
Revision as of 01:56, 19 November 2023
Contents
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
. The fraction
which is clearly not an integer since
is an integer, but
is not an integer, so
is not an integer. Therefore the condition fails specifically for the final
divisors in the list in this case, meaning
can never have
or more prime divisors.
When , it is easy to verify this works for all primes
and all
, since
, and the divisors are ordered as
.
~SpencerD.
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 |