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

Solución:

Si un primo $p$ divide a $n,$ entonces $p \mid n^n \mid m^m,$ así que $p \mid m$ y por lo tanto $p \mid 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.$ Comparar los exponentes de $p$ en $n^n \mid m^m$ da $bm \ge an,$ así que $m \ge \frac{a}{b}n \ge 2n.$ En particular $a \ge 2,$ así que $p^2 \mid 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 \mid m^m,$ y $m + n = 407 = 11 \cdot 37$ es coprimo con $210.$

Cualquier otro $n$ admisible es al menos $13^2 = 169,$ forzando $m + n \ge 3n \ge 507.$ Por lo tanto el menor valor posible es $407.$

If a prime $p$ divides $n,$ then $p \mid n^n \mid m^m,$ so $p \mid m$ and hence $p \mid 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.$ Comparing exponents of $p$ in $n^n \mid m^m$ gives $bm \ge an,$ so $m \ge \frac{a}{b}n \ge 2n.$ In particular $a \ge 2,$ so $p^2 \mid 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 \mid m^m,$ and $m + n = 407 = 11 \cdot 37$ is coprime to $210.$

Any other admissible $n$ is at least $13^2 = 169,$ forcing $m + n \ge 3n \ge 507.$ Hence the least possible value is $407.$

2020 AIME I Problema 10

Solución:

El Problema 10 en otros años