Question

Hay exactamente $77{,}000$ cuádruplas ordenadas $(a,b,c,d)$ tales que $\gcd(a,b,c,d)=77$ y $\text{lcm}(a,b,c,d)=n.$ ¿Cuál es el menor valor posible de $n$ ?

There are exactly $77{,}000$ ordered quadruples $(a,b,c,d)$ such that $\gcd(a,b,c,d)=77$ and $\text{lcm}(a,b,c,d)=n.$ What is the smallest possible value of $n?$

$13{,}860$

$20{,}790$

$21{,}560$

$27{,}720$

$41{,}580$

Respuesta: D

Conceptos:máximo común divisor mínimo común múltiplo factorización en primos

Nivel de dificultad: 2550

Solución:

Al escribir cada entrada como $77$ por un valor reducido, necesitamos $\gcd=1$ y $\text{lcm}=m=n/77.$ Para cada primo $p$ que divide a $m$ con exponente máximo $M,$ la cantidad de cuádruplas de exponentes válidas es $(M+1)^4-2M^4$ $+(M-1)^4$ $=2(6M^2+1).$ El producto sobre todos los primos debe ser $77{,}000=2^3\cdot5^3\cdot7\cdot11.$ Como $2(6M^2+1)$ vale $14,$ $50,$ y $110$ para $M=1,2,3,$ y $14\cdot50\cdot110=77{,}000,$ los exponentes $1,2,3$ dan una factorización candidata.

Cada primo aporta exactamente un factor $2,$ así que exactamente tres primos dividen a $m.$ Sus factores impares $6M^2+1$ deben dividir a $77{,}000/2^3=9625.$ Al revisar los divisores se obtiene $M=1,2,3,8,$ con factores impares $7,25,55,385.$ La opción $M=8$ deja solo $25$ como producto de los otros dos factores impares, pero cada uno es al menos $7,$ lo cual es imposible. Por tanto, los exponentes máximos son exactamente $1,2,3.$ Para minimizar $m=n/77,$ asignamos el exponente mayor al primo menor: $m=2^3\cdot3^2\cdot5=360,$ así que $n=77\cdot360=27{,}720.$

Por lo tanto, la respuesta correcta es D.

Writing each entry as $77$ times a reduced value, we need $\gcd=1$ and $\text{lcm}=m=n/77.$ For each prime $p$ dividing $m$ with maximum exponent $M,$ the number of valid exponent quadruples is $(M+1)^4-2M^4$ $+(M-1)^4$ $=2(6M^2+1).$ The total over all primes must equal $77{,}000=2^3\cdot5^3\cdot7\cdot11.$ Since $2(6M^2+1)$ equals $14,$ $50,$ and $110$ for $M=1,2,3,$ and $14\cdot50\cdot110=77{,}000,$ the exponents $1,2,3$ give one candidate factorization.

Every prime contributes exactly one factor of $2,$ so exactly three primes divide $m.$ Their odd factors $6M^2+1$ must divide $77{,}000/2^3=9625.$ Checking the divisors gives $M=1,2,3,8,$ with odd factors $7,25,55,385.$ The choice $M=8$ leaves only $25$ for the product of the other two odd factors, but each is at least $7,$ so this is impossible. Therefore the maximum exponents are exactly $1,2,3.$ To minimize $m=n/77,$ assign the largest exponent to the smallest prime: $m=2^3\cdot3^2\cdot5=360,$ so $n=77\cdot360=27{,}720.$

Thus, the correct answer is D.

2016 AMC 12B Problema 24

Respuesta: D

Nivel de dificultad: 2550

Solución:

El Problema 24 en otros años