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

Revision as of 21:41, 13 March 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

@@ Line 32: / Line 32: @@
 <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
 ==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

Page

Toolbox

Search