Números primos II: Estudio de los divisores y función $\varphi$ de Euler

Para estudiar los divisores de un número, lo más conveniente es tenerlo en descomposición canónica.

Supongamos que:

$$N = a^\alpha \cdot b^\beta \cdot c^\theta \cdots$$

donde $a, b, c, \ldots$ son primos distintos y $\alpha, \beta, \theta, \ldots$ son enteros positivos.

Un divisor $d$ de $N$ debe estar formado por los mismos primos $a, b, c, \ldots$, pero con exponentes que no pueden superar los que tienen en $N$.

Por eso, todo divisor $d$ tiene la forma:

$$d = a^x \cdot b^y \cdot c^z \cdots$$

donde:

$$0 \le x \le \alpha,\qquad 0 \le y \le \beta,\qquad 0 \le z \le \theta,\ldots$$

Ejemplo.

Para $72 = 2^3 \cdot 3^2$, los divisores se forman eligiendo:

• exponente de 2: $0, 1, 2, 3$,
• exponente de 3: $0, 1, 2$.

Así se obtienen todos los divisores de 72:

Cada casilla es el resultado de multiplicar una potencia de 2 por una potencia de 3.

Este es el punto de partida de todo el estudio de divisores: un divisor es una elección de exponentes permitidos.

Contar divisores de $N$ se convierte en contar combinaciones de exponentes.

Si:

$$N = a^\alpha \cdot b^\beta \cdot c^\theta \cdots$$

entonces:

• Para el primo $a$, el exponente puede ser $0, 1, 2, \ldots, \alpha$. Hay $\alpha + 1$ opciones.
• Para el primo $b$, hay $\beta + 1$ opciones.
• Para el primo $c$, hay $\theta + 1$ opciones.

Como las elecciones son independientes, multiplicamos:

$$CD(N) = (\alpha + 1)(\beta + 1)(\theta + 1)\cdots$$

Ejemplo.

Para $72 = 2^3 \cdot 3^2$:

$$CD(72) = (3+1)(2+1) = 4 \cdot 3 = 12$$

En efecto, en la tabla anterior hay 12 divisores.

Ejemplo.

Para $360 = 2^3 \cdot 3^2 \cdot 5^1$:

$$CD(360) = (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24$$

Observa que solo importan los exponentes, no el valor de los primos.

En los problemas de admisión aparecen expresiones como “divisores simples” o “divisores compuestos”. Hay que saber interpretarlas.

Divisores simples

Son los divisores formados por:

• el 1,
• todos los divisores primos de $N$.

Es decir, un divisor simple es el 1 o un divisor primo.

Si $N$ tiene $k$ primos distintos en su descomposición canónica, entonces:

$$\text{CD simples} = 1 + k$$

Ejemplo.

Para $18 = 2 \cdot 3^2$, los divisores son:

$$1, 2, 3, 6, 9, 18$$

Los divisores simples son:

$$1, 2, 3$$

Entonces $CD(18) = 6$ y los divisores simples son $3$. Como hay dos primos distintos, $1 + 2 = 3$.

Divisores primos

Son los divisores de $N$ que son números primos.

Si:

$$N = a^\alpha \cdot b^\beta \cdot c^\theta$$

entonces sus divisores primos son:

$$a, b, c$$

No se cuentan las potencias repetidas. Por ejemplo, en $72 = 2^3 \cdot 3^2$, los divisores primos son solo $2$ y $3$.

Divisores compuestos

Son los divisores mayores que 1 que no son primos.

Entonces:

$$\text{CD compuestos} = CD(N) - \text{CD simples}$$

Equivalentemente:

$$\text{CD compuestos} = CD(N) - (1 + k)$$

donde $k$ es el número de divisores primos.

Ejemplo.

Para $72 = 2^3 \cdot 3^2$:

$$CD(72) = 12$$

Divisores simples:

$$1, 2, 3 \quad \Rightarrow \quad 3$$

Entonces:

$$\text{CD compuestos} = 12 - 3 = 9$$

Divisores propios

Son todos los divisores positivos de $N$ excepto el propio $N$.

$$\text{CD propios} = CD(N) - 1$$

Ejemplo.

Para $72$:

$$\text{CD propios} = 12 - 1 = 11$$

Los divisores propios son los 11 divisores de 72 distintos de 72.

Muchos problemas piden contar, de todos los divisores de $N$, cuántos son múltiplos de un número $m$.

La idea es sencilla:

$$\text{divisor de } N \text{ múltiplo de } m$$

equivale a:

$$d = m \cdot q$$

donde $q$ también es divisor de $\dfrac{N}{m}$.

Por lo tanto:

$$CD_{\text{múltiplos de } m}(N) = CD\left(\frac{N}{m}\right)$$

siempre que $m$ sea divisor de $N$. Si $m$ no divide a $N$, entonces no hay divisores de $N$ que sean múltiplos de $m$.

Procedimiento práctico

1. Descompón $N$ canónicamente.
2. Descompón $m$ canónicamente.
3. Verifica que los primos de $m$ estén en $N$ con exponentes suficientes.
4. Divide $N$ entre $m$ restando exponentes.
5. Calcula la cantidad de divisores del resultado.

Ejemplo.

Sea:

$$N = 2^5 \cdot 3^4 \cdot 7^3$$

¿Cuántos divisores de $N$ son múltiplos de $28$?

Como:

$$28 = 2^2 \cdot 7$$

entonces:

$$\frac{N}{28} = 2^{5-2} \cdot 3^4 \cdot 7^{3-1}$$

$$\frac{N}{28} = 2^3 \cdot 3^4 \cdot 7^2$$

Luego:

$$CD_{\text{múltiplos de }28}(N) = CD(2^3 \cdot 3^4 \cdot 7^2)$$

$$= (3+1)(4+1)(2+1) = 4 \cdot 5 \cdot 3 = 60$$

Por lo tanto, hay 60 divisores de $N$ que son múltiplos de 28.

Otro tipo de pregunta frecuente es:

De los divisores de $N$, ¿cuántos son PESI con $m$?

Para que un divisor $d$ de $N$ sea PESI con $m$, $d$ no debe contener ningún primo que esté en $m$.

Por lo tanto, en la descomposición canónica de $N$ simplemente eliminamos todos los primos que aparecen en $m$. Luego contamos los divisores de lo que queda.

Procedimiento práctico

1. Descompón $m$ canónicamente.
2. En la descomposición de $N$, elimina las potencias de los primos que aparecen en $m$.
3. Calcula $CD$ del factor que queda.

Ejemplo.

Sea:

$$N = 2^5 \cdot 3^4 \cdot 7^3$$

Calculemos cuántos divisores de $N$ son PESI con $12$.

Como:

$$12 = 2^2 \cdot 3$$

los primos prohibidos son $2$ y $3$.

Eliminamos $2^5$ y $3^4$ de $N$. Queda:

$$7^3$$

Entonces:

$$CD_{\text{PESI con }12}(N) = CD(7^3) = 3+1 = 4$$

Los divisores son:

$$1, 7, 7^2, 7^3$$

o sea:

$$1, 7, 49, 343$$

Todos son PESI con 12.

También se puede calcular la suma de todos los divisores positivos de un número.

Veamos un caso pequeño para entender la idea.

Sea $45 = 3^2 \cdot 5$.

Sus divisores se forman así:

• potencias de 3: $1, 3, 3^2$,
• potencias de 5: $1, 5$.

La suma de todos los divisores es:

$$(1 + 3 + 3^2)(1 + 5)$$

¿Por qué? Porque al multiplicar estos dos paréntesis obtienes:

$$1 \cdot 1 + 1 \cdot 5 + 3 \cdot 1 + 3 \cdot 5 + 3^2 \cdot 1 + 3^2 \cdot 5$$

Es decir:

$$1 + 5 + 3 + 15 + 9 + 45 = 78$$

que son exactamente los divisores de 45 sumados.

En general, si:

$$N = a^\alpha \cdot b^\beta \cdot c^\theta \cdots$$

entonces:

$$SD(N) = \frac{a^{\alpha+1} - 1}{a - 1} \cdot \frac{b^{\beta+1} - 1}{b - 1} \cdot \frac{c^{\theta+1} - 1}{c - 1} \cdots$$

Cada fracción es la suma de una serie geométrica:

$$1 + a + a^2 + \cdots + a^\alpha = \frac{a^{\alpha+1} - 1}{a - 1}$$

Ejemplo.

Para $360 = 2^3 \cdot 3^2 \cdot 5$:

$$SD(360) = \frac{2^4 - 1}{2 - 1} \cdot \frac{3^3 - 1}{3 - 1} \cdot \frac{5^2 - 1}{5 - 1}$$

$$SD(360) = \frac{15}{1} \cdot \frac{26}{2} \cdot \frac{24}{4}$$

$$SD(360) = 15 \cdot 13 \cdot 6 = 1170$$

Entonces, la suma de todos los divisores positivos de 360 es 1170.

Suma de divisores propios

Si te piden la suma de los divisores propios de $N$, solo resta $N$:

$$SD_{\text{propios}}(N) = SD(N) - N$$

Ejemplo.

Para $360$:

$$SD_{\text{propios}}(360) = 1170 - 360 = 810$$

Otra propiedad útil, aunque menos común, es la del producto de todos los divisores positivos de $N$.

Si $N$ tiene $CD(N)$ divisores, entonces:

$$PD(N) = N^{CD(N)/2}$$

La razón es que cada divisor $d$ se puede emparejar con su complemento $N/d$, y cada pareja multiplica $N$.

Ejemplo.

Para $12 = 2^2 \cdot 3$, tenemos:

$$CD(12) = (2+1)(1+1) = 3 \cdot 2 = 6$$

Entonces:

$$PD(12) = 12^{6/2} = 12^3 = 1728$$

Los divisores de 12 son:

$$1, 2, 3, 4, 6, 12$$

y efectivamente su producto es:

$$1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728$$

Hasta ahora hablamos de divisores de $N$. La función $\varphi$ de Euler responde otra pregunta:

¿Cuántos números enteros positivos menores o iguales que $N$ son PESI con $N$?

A este número se le denota $\varphi(N)$.

Ejemplo.

Para $N = 10$, los números del 1 al 10 son:

$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$$

Los que son PESI con 10 son:

$$1, 3, 7, 9$$

Entonces:

$$\varphi(10) = 4$$

Observa que no todos estos números son divisores de 10; por ejemplo, 3, 7 y 9 no lo dividen. Estamos contando enteros desde 1 hasta $N$, no divisores.

Caso $N$ primo

Si $p$ es primo, todos los números $1, 2, \ldots, p-1$ son PESI con $p$. Entonces:

$$\varphi(p) = p - 1$$

Caso potencia de primo

Si $N = p^k$, los únicos números entre 1 y $p^k$ que no son PESI con $p^k$ son los múltiplos de $p$:

$$p, 2p, 3p, \ldots, p^{k-1}p$$

Hay $p^{k-1}$ de estos. Por lo tanto:

$$\varphi(p^k) = p^k - p^{k-1}$$

Equivalentemente:

$$\varphi(p^k) = p^{k-1}(p-1)$$

Fórmula general

Si:

$$N = a^\alpha \cdot b^\beta \cdot c^\theta \cdots$$

entonces:

$$\varphi(N) = a^{\alpha - 1}(a-1) \cdot b^{\beta - 1}(b-1) \cdot c^{\theta - 1}(c-1) \cdots$$

También se puede escribir:

$$\varphi(N) = N \left(1 - \frac{1}{a}\right) \left(1 - \frac{1}{b}\right) \left(1 - \frac{1}{c}\right) \cdots$$

Ejemplo.

Para $360 = 2^3 \cdot 3^2 \cdot 5$:

$$\varphi(360) = 2^{2}(2-1) \cdot 3^{1}(3-1) \cdot 5^{0}(5-1)$$

$$\varphi(360) = 4 \cdot 1 \cdot 3 \cdot 2 \cdot 1 \cdot 4$$

$$\varphi(360) = 4 \cdot 6 \cdot 4 = 96$$

Con la otra forma:

$$\varphi(360) = 360 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{5}\right)$$

$$\varphi(360) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96$$

Por lo tanto, hay 96 números entre 1 y 360 que son PESI con 360.