Difference between revisions of "2020 AIME I Problems/Problem 10"
(→Problem) |
Ihatemath123 (talk | contribs) |
||
(17 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
− | |||
− | |||
== Problem == | == Problem == | ||
Let <math>m</math> and <math>n</math> be positive integers satisfying the conditions | Let <math>m</math> and <math>n</math> be positive integers satisfying the conditions | ||
Line 12: | Line 10: | ||
Find the least possible value of <math>m+n.</math> | Find the least possible value of <math>m+n.</math> | ||
− | == Solution == | + | == Solution 1== |
− | Taking inspiration from <math>4^4 \mid 10^{10}</math> we are inspired to take <math>n</math> to be <math>p^2</math>, the lowest prime not | + | Taking inspiration from <math>4^4 \mid 10^{10}</math> we are inspired to take <math>n</math> to be <math>p^2</math>, the lowest prime not dividing <math>210</math>, or <math>11 \implies n = 121</math>. Now, there are <math>242</math> factors of <math>11</math>, so <math>11^{242} \mid m^m</math>, and then <math>m = 11k</math> for <math>k \geq 22</math>. Now, <math>\gcd(m+n, 210) = \gcd(11+k,210) = 1</math>. Noting <math>k = 26</math> is the minimal that satisfies this, we get <math>(n,m) = (121,286)</math>. Thus, it is easy to verify this is minimal and we get <math>\boxed{407}</math>. ~awang11 |
+ | |||
+ | == Solution 2 == | ||
+ | Assume for the sake of contradiction that <math>n</math> is a multiple of a single digit prime number, then <math>m</math> must also be a multiple of that single digit prime number to accommodate for <math>n^n | m^m</math>. However that means that <math>m+n</math> is divisible by that single digit prime number, which violates <math>\gcd(m+n,210) = 1</math>, so contradiction. | ||
+ | |||
+ | <math>n</math> is also not 1 because then <math>m</math> would be a multiple of it. | ||
+ | |||
+ | Thus, <math>n</math> is a multiple of 11 and/or 13 and/or 17 and/or... | ||
+ | |||
+ | Assume for the sake of contradiction that <math>n</math> has at most 1 power of 11, at most 1 power of 13...and so on... | ||
+ | Then, for <math>n^n | m^m</math> to be satisfied, <math>m</math> must contain at least the same prime factors that <math>n</math> has. This tells us that for the primes where <math>n</math> has one power of, <math>m</math> also has at least one power, and since this holds true for all the primes of <math>n</math>, <math>n|m</math>. Contradiction. | ||
+ | |||
+ | Thus <math>n</math> needs more than one power of some prime. | ||
+ | The obvious smallest possible value of <math>n</math> now is <math>11^2 =121</math>. | ||
+ | Since <math>121^{121}=11^{242}</math>, we need <math>m</math> to be a multiple of 11 at least <math>242</math> that is not divisible by <math>121</math> and most importantly, <math>\gcd(m+n,210) = 1</math>. | ||
+ | <math>242</math> is divisible by <math>121</math>, out. | ||
+ | <math>253+121</math> is divisible by 2, out. | ||
+ | <math>264+121</math> is divisible by 5, out. | ||
+ | <math>275+121</math> is divisible by 2, out. | ||
+ | <math>286+121=37\cdot 11</math> and satisfies all the conditions in the given problem, and the next case <math>n=169</math> will give us at least <math>169\cdot 3</math>, so we get <math>\boxed{407}</math>. | ||
+ | |||
+ | ==Solution 3 (Official MAA)== | ||
+ | Let <math>m</math> and <math>n</math> be positive integers where <math>m^m</math> is a multiple of <math>n^n</math> and <math>m</math> is not a multiple of <math>n</math>. If a prime <math>p</math> divides <math>n</math>, then <math>p</math> divides <math>n^n</math>, so it also divides <math>m^m</math>, and thus <math>p</math> divides <math>m</math>. Therefore any prime <math>p</math> dividing <math>n</math> also divides both <math>m</math> and <math>k = m + n</math>. Because <math>k</math> is relatively prime to <math>210=2\cdot3\cdot5\cdot7</math>, the primes <math>2</math>, <math>3</math>, <math>5</math>, and <math>7</math> cannot divide <math>n</math>. Furthermore, because <math>m</math> is divisible by every prime factor of <math>n</math>, but <math>m</math> is not a multiple of <math>n</math>, the integer <math>n</math> must be divisible by the square of some prime, and that prime must be at least <math>11</math>. Thus <math>n</math> must be at least <math>11^2 = 121</math>. | ||
+ | |||
+ | If <math>n=11^2</math>, then <math>m</math> must be a multiple of <math>11</math> but not a multiple of <math>121</math>, and <math>m^m</math> must be divisible by <math>n^n = 121^{121} = 11^{242}</math>. Therefore <math>m</math> must be a multiple of <math>11</math> that is greater than <math>242</math>. Let <math>m = 11m_0</math>, with <math>m_0 > 22</math>. Then <math>k = m + n = 11(m_0 + 11)</math>. The least <math>m_0 > 22</math> for which <math>m_0 + 11</math> is not divisible by any of the primes <math>2</math>, <math>3</math>, <math>5</math>, or <math>7</math> is <math>m_0 = 26</math>, giving the prime <math>m_0 + 11 = 37</math>. Hence the least possible <math>k</math> when <math>n = 121</math> is <math>k = 11 \cdot 37 = 407</math>. | ||
+ | |||
+ | It remains to consider other possible values for <math>n</math>. If <math>n = 13^2 = 169</math>, then <math>m</math> must be divisible by <math>13</math> but not <math>169</math>, and <math>m^m</math> must be a multiple of <math>n^n = 169^{169} = 13^{338}</math>, so <math>m > 338</math>. Then <math>k = m + n > 169 + 338 = 507</math>. All other possible values for <math>n</math> have <math>n \ge 242</math>, and in this case <math>m > n \ge 242</math>, so <math>k \ge 2 \cdot 242 = 484</math>. Hence no greater values of <math>n</math> can produce lesser values for <math>k</math>, and the least possible <math>k</math> is indeed <math>407</math>. | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/Z47NRwNB-D0 | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=FQSiQChGjpI&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=7 ~ MathEx | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2020|n=I|num-b=9|num-a=11}} | {{AIME box|year=2020|n=I|num-b=9|num-a=11}} | ||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 20:00, 31 October 2021
Contents
Problem
Let and
be positive integers satisfying the conditions
is a multiple of
and
is not a multiple of
Find the least possible value of
Solution 1
Taking inspiration from we are inspired to take
to be
, the lowest prime not dividing
, or
. Now, there are
factors of
, so
, and then
for
. Now,
. Noting
is the minimal that satisfies this, we get
. Thus, it is easy to verify this is minimal and we get
. ~awang11
Solution 2
Assume for the sake of contradiction that is a multiple of a single digit prime number, then
must also be a multiple of that single digit prime number to accommodate for
. However that means that
is divisible by that single digit prime number, which violates
, so contradiction.
is also not 1 because then
would be a multiple of it.
Thus, is a multiple of 11 and/or 13 and/or 17 and/or...
Assume for the sake of contradiction that has at most 1 power of 11, at most 1 power of 13...and so on...
Then, for
to be satisfied,
must contain at least the same prime factors that
has. This tells us that for the primes where
has one power of,
also has at least one power, and since this holds true for all the primes of
,
. Contradiction.
Thus needs more than one power of some prime.
The obvious smallest possible value of
now is
.
Since
, we need
to be a multiple of 11 at least
that is not divisible by
and most importantly,
.
is divisible by
, out.
is divisible by 2, out.
is divisible by 5, out.
is divisible by 2, out.
and satisfies all the conditions in the given problem, and the next case
will give us at least
, so we get
.
Solution 3 (Official MAA)
Let and
be positive integers where
is a multiple of
and
is not a multiple of
. If a prime
divides
, then
divides
, so it also divides
, and thus
divides
. Therefore any prime
dividing
also divides both
and
. Because
is relatively prime to
, the primes
,
,
, and
cannot divide
. Furthermore, because
is divisible by every prime factor of
, but
is not a multiple of
, the integer
must be divisible by the square of some prime, and that prime must be at least
. Thus
must be at least
.
If , then
must be a multiple of
but not a multiple of
, and
must be divisible by
. Therefore
must be a multiple of
that is greater than
. Let
, with
. Then
. The least
for which
is not divisible by any of the primes
,
,
, or
is
, giving the prime
. Hence the least possible
when
is
.
It remains to consider other possible values for . If
, then
must be divisible by
but not
, and
must be a multiple of
, so
. Then
. All other possible values for
have
, and in this case
, so
. Hence no greater values of
can produce lesser values for
, and the least possible
is indeed
.
Video Solution
Video Solution
https://www.youtube.com/watch?v=FQSiQChGjpI&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=7 ~ MathEx
See Also
2020 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.