Difference between revisions of "2023 IMO Problems/Problem 1"
Soakthrough (talk | contribs) (→Solution 2) |
m (→Solution 1) |
||
(3 intermediate revisions by the same user not shown) | |||
Line 17: | Line 17: | ||
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== | ==Solution 2== | ||
Line 33: | Line 33: | ||
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. | ||
+ | ~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 09: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 |