Conteo de Divisores a partir del TFA

Teoría

La función de conteo de divisores, que escribimos como $\tau(n)$ o $d(n)$, representa la cantidad de divisores enteros positivos de un número natural $n$. Aunque puedes encontrar los divisores de números pequeños simplemente fijándote bien, este método se vuelve imposible para números más grandes. El Teorema Fundamental de la Aritmética (TFA) te da un atajo muy potente al conectar la teoría de números con la combinatoria. El TFA dice que todo entero $n > 1$ tiene una factorización prima única. Al escribir un número como producto de sus potencias primas, encontrar cuántos divisores tiene se convierte en un problema de contar opciones con los exponentes de esos primos.

Esta técnica es básica en las olimpiadas de matemáticas porque te permite analizar cómo están armados los números sin tener que hacer una lista de todos sus factores. Se usa mucho para resolver problemas de números altamente compuestos, para saber si un número es un cuadrado perfecto (que siempre tiene un número impar de divisores) y para calcular probabilidades de divisibilidad. La idea clave es que cada divisor de $n$ se construye tomando una parte de los "ingredientes" primos de $n$. Para cada factor primo $p$ que aparece $a$ veces en la factorización de $n$, un divisor puede incluir a $p$ desde $0$ hasta $a$ veces. Como la elección del exponente para un primo no afecta a los demás, el total de divisores es simplemente el producto de las opciones que tienes para cada factor primo.

Fórmulas Clave

Supón que la factorización prima de un entero $n > 1$ viene dada por el Teorema Fundamental de la Aritmética como: $$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$ donde $p_1, p_2, \dots, p_k$ son números primos distintos y $a_1, a_2, \dots, a_k$ son enteros positivos.

El número de divisores positivos de $n$, que escribimos como $\tau(n)$, se calcula así: $$\tau(n) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$$ o usando la notación de producto: $$\tau(n) = \prod_{i=1}^{k} (a_i + 1)$$

Propiedades importantes y casos especiales:

• Propiedad multiplicativa: Si $\gcd(m, n) = 1$, entonces $\tau(mn) = \tau(m)\tau(n)$.
• Números primos: Para cualquier primo $p$, $\tau(p) = 2$ (sus divisores son solo $1$ y $p$).
• Cuadrados perfectos: Un entero $n$ es un cuadrado perfecto si y solo si $\tau(n)$ es impar. Esto pasa porque todos los exponentes $a_i$ en la factorización prima de un cuadrado son pares, lo que hace que cada término $(a_i+1)$ sea impar.

Demostración

Teorema: Si $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, entonces la cantidad de divisores positivos de $n$ es $(a_1 + 1)(a_2 + 1)\cdots(a_k + 1)$.

Demostración: Toma un divisor positivo $d$ de $n$. Por el Teorema Fundamental de la Aritmética, cualquier divisor $d$ tiene que estar formado por los mismos factores primos que $n$. Por lo tanto, $d$ debe verse así: $$d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$$

Para que $d$ divida a $n$, el exponente de cada primo en $d$ no puede ser mayor que el exponente correspondiente en $n$. Además, como $d$ es un entero, los exponentes no pueden ser negativos. Esto te da las siguientes desigualdades para cada exponente $b_i$: $$0 \le b_i \le a_i$$

Ahora puedes determinar cuántos valores posibles hay para cada $b_i$:

1. Para el primo $p_1$, el exponente $b_1$ puede ser cualquier entero del conjunto ${0, 1, 2, \dots, a_1}$. Tienes exactamente $a_1 + 1$ opciones.
2. Para el primo $p_2$, el exponente $b_2$ puede ser cualquier entero del conjunto ${0, 1, 2, \dots, a_2}$. Tienes exactamente $a_2 + 1$ opciones.
3. En general, para el primo $p_i$, puedes elegir el exponente $b_i$ de $a_i + 1$ maneras.

Como la elección del exponente $b_i$ para cualquier primo $p_i$ es independiente de lo que elijas para los otros primos, aplica el Principio Multiplicativo de la combinatoria. El número total de divisores distintos $d$ es el producto de la cantidad de opciones para cada exponente:

$$\text{Total de divisores} = (a_1 + 1) \times (a_2 + 1) \times \cdots \times (a_k + 1)$$

Así, $\tau(n) = \prod_{i=1}^{k} (a_i + 1)$. $\square$