Difference between revisions of "2023 IMO Problems/Problem 1"
(Created page with "==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</...") |
|||
Line 2: | Line 2: | ||
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>. | ||
− | ==Solution== | + | ==Solution 1== |
+ | If <math>n</math> has at least <math>2</math> prime divisors, WLOG let <math>p<q</math> be the smallest two of these primes. Then 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>. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems] | https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems] |
Revision as of 13:07, 15 July 2023
Problem
Determine all composite integers that satisfy the following property: if
are all the positive divisors of
with
, then
divides
for every
.
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
. The remaining case is when
(i.e
has no prime divisors), and this clearly works as well.
Video Solution
https://www.youtube.com/watch?v=JhThDz0H7cI [Video contains solutions to all day 1 problems]