Question

Sean $m$ y $n$ enteros positivos que satisfacen las condiciones

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

• $m^m$ es múltiplo de $n^n,$ y

• $m$ no es múltiplo de $n.$

Halle el menor valor posible de $m + n.$

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

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

• $m^m$ is a multiple of $n^n,$ and

• $m$ is not a multiple of $n.$

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

Respuesta

Respuesta: 407

Conceptos:factorización en primos divisibilidad acotación a casos límite

Nivel de dificultad: 2990

Pista pequeña:

Todo primo que divide a $n$ debe dividir a $m,$ por lo que divide a $m + n$ : así que todos los factores primos de $n$ son al menos $11.$

Every prime dividing $n$ must divide $m,$ hence divides $m + n$ — so all prime factors of $n$ are at least $11.$

Pista grande:

Pruebe $n = 11^2$ y $m = 11t$ con $t$ no divisible por $11;$ entonces que $n^n$ divida a $m^m$ necesita $m \ge 242.$ Explore hacia arriba buscando $\gcd(m + n, 210) = 1,$ y luego use la cota superior resultante para descartar exponentes deficientes más altos y valores mayores de $n.$

Try $n = 11^2$ and $m = 11t$ with $t$ not divisible by $11;$ then $n^n$ dividing $m^m$ needs $m \ge 242.$ Scan upward for $\gcd(m + n, 210) = 1,$ then use the resulting upper bound to rule out larger deficient exponents and larger $n.$

Solución:

Si un primo $p$ divide a $n,$ entonces $p$ divide a $n^n,$ que a su vez divide a $m^m,$ así que $p$ divide a $m$ y por lo tanto $p$ divide a $m + n.$ Como $\gcd(m + n, 210) = 1,$ ningún factor primo de $n$ es $2,$ $3,$ $5,$ o $7:$ todo factor primo de $n$ es al menos $11.$ Como $m$ no es múltiplo de $n,$ algún primo $p$ cumple $b = v_p(m) \lt a = v_p(n),$ donde $v_p$ denota el exponente de $p.$ Como $n^n$ divide a $m^m,$ comparar los exponentes de $p$ da $bm \ge an,$ así que $m \ge \frac{a}{b}n.$ En particular $a \ge 2,$ así que $p^2$ divide a $n$ y $n \ge 11^2 = 121.$

Tome $n = 121$ con $p = 11,$ $a = 2,$ $b = 1:$ entonces $m$ es múltiplo de $11$ pero no de $121,$ y $m \ge 2 \cdot 121 = 242.$ Los candidatos $m = 253, 264, 275$ dan $m + n = 374 = 2 \cdot 11 \cdot 17,$ $385 = 5 \cdot 7 \cdot 11,$ $396 = 2^2 \cdot 3^2 \cdot 11,$ todos compartiendo un factor con $210,$ mientras que $m = 242 = 2 \cdot 11^2$ es múltiplo de $121.$ Pero $m = 286 = 2 \cdot 11 \cdot 13$ funciona: $v_{11}(m^m) = 286$ $\ge 242 = v_{11}(n^n),$ así que $n^n$ divide a $m^m,$ y $m + n = 407 = 11 \cdot 37$ es coprimo con $210.$

Falta demostrar que nada menor funciona. Suponga que $m + n \lt 407.$ Entonces $n \lt 407.$ Para el primo deficiente anterior, $a \ge 3$ implicaría $n \ge 11^3 \gt 407,$ así que $a = 2$ y $b = 1.$ Por ello $m \ge 2n,$ y $m + n \lt 407$ implica $n \le 135.$ El único entero en este intervalo divisible por el cuadrado de un primo al menos $11$ , sin factores primos menores que $11,$ es $n = 121.$ La comprobación anterior agota todos los valores posibles de $m$ para este $n$ menores que $286,$ así que el menor valor posible es $407.$

If a prime $p$ divides $n,$ then $p$ divides $n^n,$ which in turn divides $m^m,$ so $p$ divides $m$ and hence $p$ divides $m + n.$ Since $\gcd(m + n, 210) = 1,$ no prime factor of $n$ is $2,$ $3,$ $5,$ or $7:$ every prime factor of $n$ is at least $11.$ Because $m$ is not a multiple of $n,$ some prime $p$ has $b = v_p(m) \lt a = v_p(n),$ where $v_p$ denotes the exponent of $p.$ Since $n^n$ divides $m^m,$ comparing exponents of $p$ gives $bm \ge an,$ so $m \ge \frac{a}{b}n.$ In particular $a \ge 2,$ so $p^2$ divides $n$ and $n \ge 11^2 = 121.$

Take $n = 121$ with $p = 11,$ $a = 2,$ $b = 1:$ then $m$ is a multiple of $11$ but not of $121,$ and $m \ge 2 \cdot 121 = 242.$ The candidates $m = 253, 264, 275$ give $m + n = 374 = 2 \cdot 11 \cdot 17,$ $385 = 5 \cdot 7 \cdot 11,$ $396 = 2^2 \cdot 3^2 \cdot 11,$ all sharing a factor with $210,$ while $m = 242 = 2 \cdot 11^2$ is a multiple of $121.$ But $m = 286 = 2 \cdot 11 \cdot 13$ works: $v_{11}(m^m) = 286$ $\ge 242 = v_{11}(n^n),$ so $n^n$ divides $m^m,$ and $m + n = 407 = 11 \cdot 37$ is coprime to $210.$

It remains to prove that nothing smaller works. Suppose $m + n \lt 407.$ Then $n \lt 407.$ For the deficient prime above, $a \ge 3$ would imply $n \ge 11^3 \gt 407,$ so $a = 2$ and $b = 1.$ Thus $m \ge 2n,$ and $m + n \lt 407$ implies $n \le 135.$ The only integer in this range divisible by the square of a prime at least $11$ , with no prime factors below $11,$ is $n = 121.$ The preceding check exhausts every possible $m$ for this $n$ below $286,$ so the least possible value is $407.$

2020 AIME I Problema 10

Respuesta: 407

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 10 en otros años