Question

Para enteros positivos $N$ y $k,$ se dice que $N$ es $k$ -nice si existe un entero positivo $a$ tal que $a^k$ tiene exactamente $N$ divisores positivos. Halla el número de enteros positivos menores que $1000$ que no son ni $7$ -nice ni $8$ -nice.

For positive integers $N$ and $k,$ define $N$ to be $k$ -nice if there exists a positive integer $a$ such that $a^k$ has exactly $N$ positive divisors. Find the number of positive integers less than $1000$ that are neither $7$ -nice nor $8$ -nice.

Respuesta

Solución:

Si $a = p_1^{m_1} \cdots p_t^{m_t},$ entonces $a^k$ tiene $(km_1 + 1)(km_2 + 1)$ $\cdots (km_t + 1)$ divisores positivos, y cada factor es $\equiv 1 \pmod{k},$ así que el producto también. Recíprocamente, si $N = km + 1,$ entonces $a = p^m$ da $a^k = p^{km}$ con exactamente $N$ divisores. Así que $N$ es $k$ -nice exactamente cuando $N \equiv 1 \pmod{k}.$

Entre $1, 2, \ldots, 999$ hay $143$ enteros $\equiv 1 \pmod{7}$ (a saber $1, 8, \ldots, 995$ ) y $125$ enteros $\equiv 1 \pmod{8}$ (a saber $1, 9, \ldots, 993$ ). Como $\operatorname{lcm}(7, 8) = 56,$ hay $18$ enteros $\equiv 1 \pmod{56}$ (a saber $1, 57, \ldots, 953$ ). Por inclusión-exclusión, $143 + 125 - 18 = 250$ de ellos son $7$ -nice u $8$ -nice.

Por tanto $999 - 250 = 749$ enteros positivos menores que $1000$ no son ninguno de los dos.

If $a = p_1^{m_1} \cdots p_t^{m_t},$ then $a^k$ has $(km_1 + 1)(km_2 + 1)$ $\cdots (km_t + 1)$ positive divisors, and each factor is $\equiv 1 \pmod{k},$ so the product is too. Conversely, if $N = km + 1,$ then $a = p^m$ gives $a^k = p^{km}$ with exactly $N$ divisors. So $N$ is $k$ -nice exactly when $N \equiv 1 \pmod{k}.$

Among $1, 2, \ldots, 999$ there are $143$ integers $\equiv 1 \pmod{7}$ (namely $1, 8, \ldots, 995$ ) and $125$ integers $\equiv 1 \pmod{8}$ (namely $1, 9, \ldots, 993$ ). Since $\operatorname{lcm}(7, 8) = 56,$ there are $18$ integers $\equiv 1 \pmod{56}$ (namely $1, 57, \ldots, 953$ ). By inclusion-exclusion, $143 + 125 - 18 = 250$ of them are $7$ -nice or $8$ -nice.

Hence $999 - 250 = 749$ positive integers less than $1000$ are neither.

2016 AIME II Problema 11

Solución:

El Problema 11 en otros años