Question

Halla la cantidad de enteros positivos que son divisores de al menos uno de $10^{10},$ $15^7,$ $18^{11}.$

Find the number of positive integers that are divisors of at least one of $10^{10},$ $15^7,$ $18^{11}.$

Respuesta

Respuesta: 435

Conceptos:conteo de factores inclusión-exclusión máximo común divisor

Nivel de dificultad: 2230

Pista pequeña:

Cuenta los divisores de cada número a partir de su factorización en primos y luego corrige el conteo repetido.

Count the divisors of each number from its prime factorization, then fix the overcounting

Pista grande:

Los divisores comunes de dos de los números son exactamente los divisores de su máximo común divisor, por ejemplo $\gcd(10^{10}, 15^7) = 5^7.$

The common divisors of two of the numbers are exactly the divisors of their gcd, e.g. $\gcd(10^{10}, 15^7) = 5^7$

Solución:

A partir de las factorizaciones $10^{10} = 2^{10} 5^{10},$ $15^7 = 3^7 5^7$ y $18^{11} = 2^{11} 3^{22},$ las cantidades de divisores son $11 \cdot 11 = 121,$ $8 \cdot 8 = 64$ y $12 \cdot 23 = 276.$

Los divisores comunes a dos de los números son exactamente los divisores de su máximo común divisor: $\gcd(10^{10}, 15^7) = 5^7$ tiene $8$ divisores, $\gcd(10^{10}, 18^{11}) = 2^{10}$ tiene $11$ y $\gcd(15^7, 18^{11}) = 3^7$ tiene $8.$ Solo $1$ divide a los tres números.

Por inclusión-exclusión, la cantidad es $121 + 64 + 276$ $- 8 - 11 - 8 + 1$ $= 435.$

From the factorizations $10^{10} = 2^{10} 5^{10},$ $15^7 = 3^7 5^7,$ and $18^{11} = 2^{11} 3^{22},$ the divisor counts are $11 \cdot 11 = 121,$ $8 \cdot 8 = 64,$ and $12 \cdot 23 = 276.$

The divisors common to two of the numbers are exactly the divisors of their gcd: $\gcd(10^{10}, 15^7) = 5^7$ has $8$ divisors, $\gcd(10^{10}, 18^{11}) = 2^{10}$ has $11,$ and $\gcd(15^7, 18^{11}) = 3^7$ has $8.$ Only $1$ divides all three numbers.

By inclusion-exclusion, the count is $121 + 64 + 276$ $- 8 - 11 - 8 + 1$ $= 435.$

2005 AIME II Problema 4

Respuesta: 435

Nivel de dificultad: 2230

Pista pequeña:

Pista grande:

Solución:

El Problema 4 en otros años