Difference between revisions of "2020 AIME I Problems/Problem 10"

(Solution)
m (Video Solution)
(15 intermediate revisions by 12 users not shown)
Line 1: Line 1:
Note: Please do not post problems here until after the AIME.
+
== Problem ==
 +
Let <math>m</math> and <math>n</math> be positive integers satisfying the conditions
 +
 
 +
<math>\quad\bullet\ \gcd(m+n,210)=1,</math>
 +
 
 +
<math>\quad\bullet\ m^m</math> is a multiple of <math>n^n,</math> and
 +
 
 +
<math>\quad\bullet\ m</math> is not a multiple of <math>n.</math>
 +
 
 +
Find the least possible value of <math>m+n.</math>
 +
 
 +
== 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 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>.
 +
 
 +
==Video Solution==
 +
https://youtu.be/Z47NRwNB-D0
  
== Problem ==
 
  
== Solution ==
+
==Video Solution==
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 dividng <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
+
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}}

Revision as of 22:18, 25 November 2020

Problem

Let $m$ and $n$ be positive integers satisfying the conditions

$\quad\bullet\ \gcd(m+n,210)=1,$

$\quad\bullet\ m^m$ is a multiple of $n^n,$ and

$\quad\bullet\ m$ is not a multiple of $n.$

Find the least possible value of $m+n.$

Solution 1

Taking inspiration from $4^4 \mid 10^{10}$ we are inspired to take $n$ to be $p^2$, the lowest prime not dividing $210$, or $11 \implies n = 121$. Now, there are $242$ factors of $11$, so $11^{242} \mid m^m$, and then $m = 11k$ for $k \geq 22$. Now, $\gcd(m+n, 210) = \gcd(11+k,210) = 1$. Noting $k = 26$ is the minimal that satisfies this, we get $(n,m) = (121,286)$. Thus, it is easy to verify this is minimal and we get $\boxed{407}$. ~awang11

Solution 2

Assume for the sake of contradiction that $n$ is a multiple of a single digit prime number, then $m$ must also be a multiple of that single digit prime number to accommodate for $n^n | m^m$. However that means that $m+n$ is divisible by that single digit prime number, which violates $\gcd(m+n,210) = 1$, so contradiction.

$n$ is also not 1 because then $m$ would be a multiple of it.

Thus, $n$ is a multiple of 11 and/or 13 and/or 17 and/or...

Assume for the sake of contradiction that $n$ has at most 1 power of 11, at most 1 power of 13...and so on... Then, for $n^n | m^m$ to be satisfied, $m$ must contain at least the same prime factors that $n$ has. This tells us that for the primes where $n$ has one power of, $m$ also has at least one power, and since this holds true for all the primes of $n$, $n|m$. Contradiction.

Thus $n$ needs more than one power of some prime. The obvious smallest possible value of $n$ now is $11^2 =121$. Since $121^{121}=11^{242}$, we need $m$ to be a multiple of 11 at least $242$ that is not divisible by $121$ and most importantly, $\gcd(m+n,210) = 1$. $242$ is divisible by $121$, out. $253+121$ is divisible by 2, out. $264+121$ is divisible by 5, out. $275+121$ is divisible by 2, out. $286+121=37\cdot 11$ and satisfies all the conditions in the given problem, and the next case $n=169$ will give us at least $169\cdot 3$, so we get $\boxed{407}$.

Video Solution

https://youtu.be/Z47NRwNB-D0


Video Solution

https://www.youtube.com/watch?v=FQSiQChGjpI&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=7 ~ MathEx

See Also

2020 AIME I (ProblemsAnswer KeyResources)
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. AMC logo.png