Función \(\varphi\) de Euler

Introducción

En este capítulo exploraremos la función phi de Euler, la cual nos indica cuántos números menores que un entero positivo \(n\) son primos relativos con éste. Recordemos que la definición de números primos relativos la discutimos en la sección del máximo común divisor (Definición 9). Observaremos que esta función puede calcularse de manera laboriosa y tediosa, es decir, manualmente y realizando cálculos, pero también desarrollaremos una fórmula que simplifica este proceso. Además, exploraremos algunas aplicaciones y propiedades de esta función.

Primos relativos menores a un entero dado.

Recordemos que vimos la definición de cuándo dos números son primos relativos (Definición 9). Ahora, nos interesa buscar a los primos relativos con un número \(n\), tales que sean menores a \(n\) y positivos. Los siguientes dos ejemplos nos ilustraran la idea de lo que estamos buscando.

Ejemplo 53

Calculemos para qué valores de \(i\), donde \(1\le i\le 13\), se cumple que \((13,i) = 1\) y para qué valores de \(j\), donde \(1\le j\le 24\), se cumple que \((24,j) = 1\).

Solución.

Notemos que como \(13\) es un número primo, solo tiene como divisores a \(1\) y a \(13\). Entonces, para cualquier número positivo y menor a \(13\) tendríamos que \((13,i)=1\).

Por lo tanto, para \(i = 1,2,3,4,5,6,7,8,9,10,11,12\), se cumple que \((13,i) = 1\).

Ahora, busquemos los primos relativos con \(24\). Tendríamos lo siguiente:

\[\begin{align*} (24,1) &= 1, & (24,9) &= 3, & (24,17) &=1, \\ & \\ (24,2) &= 2, & (24,10) &= 2, & (24,18) &=6, \\ & \\ (24,3) &= 3, & (24,11) &= 1, & (24,19) &=1, \\ & \\ (24,4) &= 4, & (24,12) &= 6, & (24,20) &=4, \\ & \\ (24,5) &= 1, & (24,13) &= 1, & (24,21) &=3, \\ & \\ (24,6) &= 6, & (24,14) &= 2, & (24,22) &=2, \\ & \\ (24,7) &= 1, & (24,15) &= 3, & (24,23) &=1, \\ & \\ (24,8) &= 8, & (24,16) &= 8, & (24,24) &=24. \\ \end{align*}\]

Por lo tanto, para \(j = 1,5,7,11,13,17,19,23\), se cumple que \((24,j) = 1\).

Definición de la función \(\varphi\) de Euler

Definición 21 (Función de Euler)

Sea \(n\) un entero positivo. La función de Euler \(\varphi(n)\) denota el número de enteros positivos menores o iguales que \(n\) y que además son primos relativos con \(n\).

Ejemplo 54

Veamos los primeros \(10\) valores de la función \(\varphi(n)\):

\[\begin{align*} \varphi(1) &= 1, & \varphi(6) &= 2, \\ & \\ \varphi(2) &= 1, & \varphi(7) &= 6, \\ & \\ \varphi(3) &= 2, & \varphi(8) &= 4, \\ & \\ \varphi(4) &= 2, & \varphi(9) &= 6, \\ & \\ \varphi(5) &= 4, & \varphi(10) &= 4. \\ \end{align*}\]

Fórmula para la función \(\varphi\) de Euler

Teniendo en mente el Ejemplo 53, podemos notar lo tardado que sería calcular los primos relativos a un número \(n\) que sean menores que \(n\), cuando \(n\) es demasiado grande. En esta sección vamos a desarrollar una fórmula que nos ayudará a hacer este cálculo más sencillo.

Primero veamos \(\varphi(n)\) cuando \(n\) es un número primo.

Lema 7

Si \(p\) es un número primo, entonces \(\varphi(p) = p-1\).

Demostración. Sea \(p\) un número primo.
Sabemos que los divisores de \(p\) son \(\{1,p\}\) y que los enteros positivos menores a \(p\) son \(\{1,2,\ldots,p-2,p-1\}\).
Entonces para cualquier entero positivo \(n\) menor que \(p\), se cumple que \((n,p) = 1\), es decir que \(p\) es primo relativo con cualquiera de estos números.
Por lo tanto concluimos que \(\varphi(p) = p-1\).\(\square\)

A continuación veremos cómo se comporta la función \(\varphi(n)\) cuando \(n = p^a\), donde \(a\) es un entero positivo. Para la demostración del siguiente teorema veamos un ejercicio previo.

Ejemplo 55

Calcula \(\varphi(16)\).

Solución.

Notemos que \(16 = 2^4\).
Denotemos como \(A\) al conjunto de los números positivos menores o iguales que \(16\), es decir:

\[A = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\}.\]

Notemos que la cardinalidad del conjunto \(A\) es \(16 = 2^4\).

Por otro lado, denotemos como \(B\) al conjunto de los números positivos menores o iguales que \(16\) que NO son primos relativos con \(16\). Como \(16 = 2^4\), entonces los números que NO son primos relativos con \(16\) serían los números que son múltiplos de \(2\), es decir:

\[B = \{ 2, 2\cdot 2, 3\cdot 2, 4\cdot 2, 5\cdot 2, 6\cdot 2, 7\cdot 2, 8\cdot 2 \}.\]

Notemos que la cardinalidad del conjunto \(B\) es \(8 = 2^3\).

Ahora, tendríamos lo siguiente:

\[\begin{align*} \varphi(16) &= \varphi(2^4) \\ & \\ &= \text{Número de enteros positivos } \le 16 \text{ y primos relativos con } 16. \\ & \\ &= |A| - |B| = 2^4 - 2^3 = 2^4 \left( 1 - \frac{1}{2} \right) \\ & \\ &= 16 \left( \frac{1}{2} \right) = 8. \end{align*}\]

Así, tenemos que hay \(8\) números que son primos relativos con \(16\).

Teorema 18

Sea \(p\) un número primo y \(a\) un entero positivo. Entonces \(\varphi(p^a) = p^a - p^{a-1} = p^a \left( 1- \frac{1}{p} \right)\).

Demostración. Sean

\[\begin{align*} A &= \{ \text{ enteros positivos } \le p^a \}, \\ & \\ B &= \{ \text{ enteros positivos } \le p^a \text{ que NO son primos relativos con } p^a \}. \end{align*}\]

Entonces,

\[\begin{align*} \varphi(p^a) &=| \{ \text{enteros positivos } \le p^a \text{ y primos relativos con } p^a \} | \\ & \\ &= |A| - |B|. \end{align*}\]

Notemos que la cardinalidad del conjunto \(A = \{1,2,3,\ldots,p^a-2,p^a-1,p^a\}\) es, \(|A| = p^a\).
Luego notemos que como \(p^a\) es potencia de un primo, si tomamos un valor \(n\) tal que \(1\le n \le p^a\), entonces \((n,p^a)>1\) si y solo si \(n\) es múltiplo de \(p\).
Los múltiplos enteros de \(p\) en el intervalo \([ 1,p^a]\) son \(p,2p,3p,\ldots,(p^{a-1})p\) y estos en total son \(p^{a-1}\), por lo tanto la cardinalidad del conjunto \(B = \{p,2p,3p,\ldots,(p^{a-1})p \}\) es \(|B| = p^{a-1}\).

Por lo tanto tenemos que:

\[\begin{align*} \varphi(p^a) = |A| - |B| = p^a - p^{a-1} = p^a \left( 1- \frac{1}{p} \right). \square \end{align*}\]

Ejemplo 56

Calcula cuántos números positivos menores a \(81\) son primos relativos con \(81\) utilizando la fórmula para la función \(\varphi(n)\).

Solución.

Sabemos que \(81=3^4\), entonces:

\[\begin{align*} \varphi(81) &= \varphi(3^4) \\ & \\ &= 3^4\left( 1- \frac{1}{3} \right) \\ & \\ &= 81\left( \frac{2}{3} \right) = 54. \end{align*}\]

Antes de proceder con el siguiente teorema, veamos una proposición que nos será de mucha ayuda en la demostración del caso general para la función \(\varphi(n)\).

Proposición 18

Sea \(m\) un número entero. Si \(m\) es primo relativo con un entero \(n\), en donde \(1 < n <m\), entonces \(m\) es primo relativo con \(m + n\).

Demostración. Supongamos que \((m,m+n) = d\), queremos demostrar que \(d=1\).
Notemos que, como \(d|m\) y \(d|(m+n)\), entonces \(d|(m+n) - m = n\).
Por lo tanto obtenemos que \(d|n\) y \(d|m\), pero como \(n\) y \(m\) son primos relativos, sabemos que \((m,n) = 1\), por lo tanto \(d = 1\).

Así, concluimos que \(m\) es primo relativo con \(m+n. \square\)

La Proposición 18 nos ayuda a ver que si tomamos un entero \(m\) y nos fijamos en el intervalo \([0,m]\), si en el intervalo hay \(k\) números que son primos relativos con \(m\), entonces en el intervalo \([m+1,2m]\) también habrá \(k\) números que son primos relativos con \(m\).

Ejemplo de inducción para la demostración del caso general de la función \(\varphi\)

Lo que vamos a demostrar en la siguiente sección es la fórmula para el caso general de la función \(\varphi(n)\) de Euler, es decir, que para un entero positivo \(n\) con descomposición canónica \(n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\), se cumple que

\[\varphi(n) = \varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}) = n \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right).\]

Para la demostración de la fórmula vamos a proceder por inducción. Antes de pasar a la demostración, presentaremos un ejemplo particular para comprender la idea de la inducción que realizaremos. En este ejemplo, vamos a ver que podemos calcular el valor de \(\varphi(2^3\cdot 3\cdot 5^2)\) suponiendo que ya demostramos que la fórmula es válida para

\[\begin{align*} \varphi(5^2) &= 5^2\left(1 - \frac{1}{5} \right), \\ & \\ \varphi(2^3\cdot 3) &= 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right). \end{align*}\]

También, vamos a apoyarnos con códigos de Python para observar con mas detalle los intervalos de los cuales vamos a hablar.

Ejemplo 57

Supongamos que la fórmula de la función \(\varphi\) de Euler es válida para:

\[\begin{align*} \varphi(5^2) &= 5^2\left(1 - \frac{1}{5} \right), \\ & \\ \varphi(2^3\cdot 3) &= 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right). \end{align*}\]

Con lo anterior, calcula el valor de \(\varphi(n)\) para \(n = 600 = 2^3\cdot 3\cdot 5^2\).

Solución.

La idea para encontrar éste valor es la siguiente.

Primero, vamos a buscar los números que son múltiplos de \(2\) o \(3\) en el intervalo \([1,600]\). Para ello, vamos a formar intervalos de tamaño \(2^3\cdot 3\).

Por la suposición inicial, sabemos que en el intervalo \([1,2^3\cdot 3]\) hay

\[\varphi(2^3\cdot 3) = 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right),\]

números que son primos relativos con \(2^3\cdot 3\). Entonces, la cantidad de números que son múltiplos de \(2\) o \(3\) serían

\[2^3\cdot 3 - 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right).\]

Es decir, el total de números en el intervalo menos los que son primos relativos con \(2^3\cdot 3\).

Ahora, vamos a seguir tomando intervalos de tamaño \(2^3\cdot 3\) hasta que cubramos el intervalo \([1,600]\) con éstos. Entonces tendríamos los intervalos

\[\begin{align*} &[2^3\cdot 3+ 1,\text{ } 2\cdot 2^3\cdot 3], \\ & \\ &[2\cdot 2^3\cdot 3 + 1,\text{ } 3\cdot 2^3\cdot 3 ], \\ &\vdots \\ &[(5^2 - 2) 2^3\cdot 3 + 1,\text{ } (5^2 - 1) 2^3\cdot 3], \\ & \\ &[(5^2 - 1) 2^3\cdot 3 + 1,\text{ } 5^2\cdot 2^3\cdot 3 ]. \end{align*}\]

En total tenemos \(5^2\) intervalos. Por la Proposición 18, tenemos que cada uno de ellos tiene la misma cantidad de números que son múltiplos de \(2\) o \(3\). Por lo tanto, tenemos que en el intervalo \([1,600]\) hay

\[5^2\left( 2^3\cdot 3 - 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right) \right)\]

números que son múltiplos de \(2\) o \(3\) (en la Observación 8 se encuentran los intervalos).

De manera similar, vamos a obtener los números que son múltiplos de \(5\) en el intervalo \([1,600]\). Vamos a formar intervalos de tamaño \([1,5^2]\), por el Teorema 18 sabemos que hay

\[\varphi(5^2) = 5^2\left(1 - \frac{1}{5} \right),\]

números que son primos relativos con \(5^2\). Entonces la cantidad de números que son múltiplos de \(5\) son

\[5^2 - 5^2\left(1 - \frac{1}{5} \right).\]

Ahora, seguiremos formando intervalos de tamaño \(5^2\) hasta que cubramos el intervalo \([1,600]\) con éstos. Entonces, tendríamos los intervalos

\[\begin{align*} &[5^2 + 1, \text{ } 2\cdot 5^2 ], \\ & \\ &[2\cdot 5^2 + 1, \text{ } 3\cdot 5^2 ], \\ &\vdots \\ &[(2^3\cdot 3 -2)5^2 + 1, \text{ } (2^3\cdot 3 -1)5^2 ], \\ & \\ &[(2^3\cdot 3 -1)5^2 + 1, \text{ } 2^3\cdot 3\cdot 5^2 ]. \\ \end{align*}\]

En total hay \(2^3\cdot 3\) intervalos. Nuevamente por la Proposición 18, tenemos en cada uno de los intervalos la misma cantidad de números que son múltiplos de \(5\). Por lo tanto, tenemos que en el intervalo \([1,600]\) hay

\[2^3\cdot 3 \left( 5^2 - 5^2\left(1 - \frac{1}{5} \right) \right)\]

números que son múltiplos de \(5\) (en la Observación 9 se encuentran los intervalos).

Por último, tenemos que buscar los números que encuentran en la intersección, es decir, los números que son múltiplos de \(2\) y \(5\) o de \(3\) y \(5\). Necesitamos restar estos números para evitar contar dos veces el mismo número.

Vamos a fijarnos en los números que son múltiplos de \(2\) o \(3\) en el intervalo \([1,120]\). Entre éstos, la \(\frac{1}{5}\) parte son múltiplos de \(5\).

\[\begin{align*} &[2, 3, 4, 6, 8, 9, (10), 12, 14, (15), 16, 18, (20), 21, 22, 24 ], \\ & \\ &[26, 27, 28, (30), 32, 33, 34, 36, 38, 39, (40), 42, 44, (45), 46, 48 ], \\ & \\ &[(50), 51, 52, 54, 56, 57, 58, (60), 62, 63, 64, 66, 68, 69, (70), 72 ], \\ & \\ &[74, (75), 76, 78, (80), 81, 82, 84, 86, 87, 88, (90), 92, 93, 94, 96 ],\\ & \\ &[98, 99, (100), 102, 104, (105), 106, 108, (110), 111, 112, 114, 116, 117, 118, (120) ]. \end{align*}\]

Pero esto, también se cumple en los siguientes \(4\) intervalos \([121,240]\),\([241,360]\),\([361,480]\) y \([481,600]\) (en la Observación 10 se encuentran los intervalos). De está manera, si multiplicamos por \(\frac{1}{5}\) la cantidad de números que son divisibles entre \(2\) o \(3\) en el intervalo \([1,600]\), obtendríamos los números que son divisibles entre \(2\) y \(5\) o \(3\) y \(5\). Por lo tanto, la cantidad de números repetidos que tenemos que restar es

\[\begin{align*} \frac{1}{5}\cdot 5^2 &\left( 2^3\cdot 3 - 2^3\cdot 3 \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \right), \\ & \\ 5^{2-1} &\left( 2^3\cdot 3 - 2^3\cdot 3 \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \right). \\ \end{align*}\]

Finalmente tenemos lo siguiente

\[\begin{align*} \varphi(2^3\cdot 3 \cdot 5^2) &= |\{ \text{números en el intervalo} [1,600] \}| - \left (|\{ \text{múltiplos de $2$ o $3$} \}| + |\{ \text{múltiplos de $5$} \}| - |\{ \text{múltiplos de } 2 \text{ y } 5 \text{ o de } 3 \text{ y } 5 \}| \right) \\ & \\ &= 2^3\cdot 3\cdot 5^2 - \left( 5^2\left( 2^3\cdot 3 - 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right) \right) + 2^3\cdot 3 \left( 5^2 - 5^2\left(1 - \frac{1}{5} \right) \right) - 5^{2-1} \left( 2^3\cdot 3 - 2^3\cdot 3 \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \right) \right) \\ & \\ &= n - 5^2\left( 2^3\cdot 3 - 2^3\cdot 3\left(1- \frac{1}{2} \right)\left(1- \frac{1}{3} \right) \right) - 2^3\cdot 3 \left( 5^2 - 5^2\left(1 - \frac{1}{5} \right) \right) + 5^{2-1} \left( 2^3\cdot 3 - 2^3\cdot 3 \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \right) \\ & \\ &= n - 2^3\cdot 3\cdot 5^2 + 2^3\cdot 3\cdot 5^2\left(1- \frac{1}{2} \right) \left(1- \frac{1}{3} \right) - 2^3\cdot 3\cdot 5^2 + 2^3\cdot 3\cdot 5^2\left(1 - \frac{1}{5} \right) + 2^3\cdot 3\cdot 5^{2-1} - 2^3\cdot 3\cdot 5^{2-1} \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \\ & \\ &= n - n + n\left(1- \frac{1}{2} \right) \left(1- \frac{1}{3} \right) - n + n\left(1 - \frac{1}{5} \right) + \frac{n}{5} - \frac{n}{5} \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \\ & \\ &= n\left(1- \frac{1}{2} \right) \left(1- \frac{1}{3} \right) - \frac{n}{5} \left( 1 - \frac{1}{2}\right) \left( 1 - \frac{1}{3} \right) \\ & \\ &= n\left(1- \frac{1}{2} \right) \left(1- \frac{1}{3} \right) \left(1 - \frac{1}{5} \right). \end{align*}\]

Aquí están los códigos que utilizamos para el Ejemplo 57.

Usaremos la función que construimos en la sección del algoritmo de Euclides para calcular el máximo común divisor. También, la función que creamos en el capítulo del teorema fundamental de la aritmética para encontrar los primos involucrados en la factorización de un entero.

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return b

def factorizar_en_primos(n):
    lst = []
    for i in range(2, n+1):
        while n % i == 0:
            lst.append(i)
            n //= i
        if n == 1:
            break
    return lst

El siguiente código nos ayuda a generar los intervalos que se mencionan en el Ejemplo 57. El argumento «opcion» define el comportamiento de la función. Acepta únicamente los valores “relativos”, “multiplos” o “interseccion”. Cada uno de estos valores indica un caso específico para ejecutar la lógica.»

def prel_mult_int(numero, intervalos, opcion):
    for i in range(1,intervalos+1):
        int_1 = i*numero - numero +1
        int_2 = i*numero
        if opcion == "prelativos":
            primos_relativos = [x for x in range(int_1,int_2+1) if algoritmo_euclides(numero,x) == 1]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(primos_relativos)} primos relativos con {numero} y son: ")
            print(primos_relativos)
        elif opcion == "multiplos":
            primos = set(factorizar_en_primos(numero))
            multiplos = [x for x in range(int_1,int_2+1) if any(x % d == 0 for d in primos)]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(multiplos)} números que son múltiplos de {primos} y son: ")
            print(f"{i}: {multiplos}")
        elif opcion == "interseccion":
            interseccion = [x for x in range(int_1,int_2+1) if (x%2 == 0 and x%5 == 0) or (x%3 == 0 and x%5 == 0)]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(interseccion)} números que son múltiplos de 2 y 5 o 3 y 5: ")
            print(f"{i}: {interseccion}")
        else:
            print("Opción no válida. Ingresa como tercer argumento: 'prelativos', 'multiplos' o 'interseccion'.")

Con la siguiente ejecución del código obtenemos los números que son primos relativos con \(600\) en el intervalo \([1,600]\).

prel_mult_int(2**3 * 3 * 5**2, 1, "prelativos")

En el intervalo [1,600] hay 160 primos relativos con 600 y son: 
[1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139, 143, 149, 151, 157, 161, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 203, 209, 211, 217, 221, 223, 227, 229, 233, 239, 241, 247, 251, 253, 257, 259, 263, 269, 271, 277, 281, 283, 287, 289, 293, 299, 301, 307, 311, 313, 317, 319, 323, 329, 331, 337, 341, 343, 347, 349, 353, 359, 361, 367, 371, 373, 377, 379, 383, 389, 391, 397, 401, 403, 407, 409, 413, 419, 421, 427, 431, 433, 437, 439, 443, 449, 451, 457, 461, 463, 467, 469, 473, 479, 481, 487, 491, 493, 497, 499, 503, 509, 511, 517, 521, 523, 527, 529, 533, 539, 541, 547, 551, 553, 557, 559, 563, 569, 571, 577, 581, 583, 587, 589, 593, 599]

Observación 8

Con la siguiente ejecución de código obtenemos los \(5^2\) intervalos de tamaño \(2^3\cdot 3\) que tienen números que son múltiplos de \(2\) y \(3\).

prel_mult_int(2**3 * 3, 5**2, "multiplos")

En el intervalo [1,24] hay 16 números que son múltiplos de {2, 3} y son: 
1: [2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24]
En el intervalo [25,48] hay 16 números que son múltiplos de {2, 3} y son: 
2: [26, 27, 28, 30, 32, 33, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48]
En el intervalo [49,72] hay 16 números que son múltiplos de {2, 3} y son: 
3: [50, 51, 52, 54, 56, 57, 58, 60, 62, 63, 64, 66, 68, 69, 70, 72]
En el intervalo [73,96] hay 16 números que son múltiplos de {2, 3} y son: 
4: [74, 75, 76, 78, 80, 81, 82, 84, 86, 87, 88, 90, 92, 93, 94, 96]
En el intervalo [97,120] hay 16 números que son múltiplos de {2, 3} y son: 
5: [98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 116, 117, 118, 120]
En el intervalo [121,144] hay 16 números que son múltiplos de {2, 3} y son: 
6: [122, 123, 124, 126, 128, 129, 130, 132, 134, 135, 136, 138, 140, 141, 142, 144]
En el intervalo [145,168] hay 16 números que son múltiplos de {2, 3} y son: 
7: [146, 147, 148, 150, 152, 153, 154, 156, 158, 159, 160, 162, 164, 165, 166, 168]
En el intervalo [169,192] hay 16 números que son múltiplos de {2, 3} y son: 
8: [170, 171, 172, 174, 176, 177, 178, 180, 182, 183, 184, 186, 188, 189, 190, 192]
En el intervalo [193,216] hay 16 números que son múltiplos de {2, 3} y son: 
9: [194, 195, 196, 198, 200, 201, 202, 204, 206, 207, 208, 210, 212, 213, 214, 216]
En el intervalo [217,240] hay 16 números que son múltiplos de {2, 3} y son: 
10: [218, 219, 220, 222, 224, 225, 226, 228, 230, 231, 232, 234, 236, 237, 238, 240]
En el intervalo [241,264] hay 16 números que son múltiplos de {2, 3} y son: 
11: [242, 243, 244, 246, 248, 249, 250, 252, 254, 255, 256, 258, 260, 261, 262, 264]
En el intervalo [265,288] hay 16 números que son múltiplos de {2, 3} y son: 
12: [266, 267, 268, 270, 272, 273, 274, 276, 278, 279, 280, 282, 284, 285, 286, 288]
En el intervalo [289,312] hay 16 números que son múltiplos de {2, 3} y son: 
13: [290, 291, 292, 294, 296, 297, 298, 300, 302, 303, 304, 306, 308, 309, 310, 312]
En el intervalo [313,336] hay 16 números que son múltiplos de {2, 3} y son: 
14: [314, 315, 316, 318, 320, 321, 322, 324, 326, 327, 328, 330, 332, 333, 334, 336]
En el intervalo [337,360] hay 16 números que son múltiplos de {2, 3} y son: 
15: [338, 339, 340, 342, 344, 345, 346, 348, 350, 351, 352, 354, 356, 357, 358, 360]
En el intervalo [361,384] hay 16 números que son múltiplos de {2, 3} y son: 
16: [362, 363, 364, 366, 368, 369, 370, 372, 374, 375, 376, 378, 380, 381, 382, 384]
En el intervalo [385,408] hay 16 números que son múltiplos de {2, 3} y son: 
17: [386, 387, 388, 390, 392, 393, 394, 396, 398, 399, 400, 402, 404, 405, 406, 408]
En el intervalo [409,432] hay 16 números que son múltiplos de {2, 3} y son: 
18: [410, 411, 412, 414, 416, 417, 418, 420, 422, 423, 424, 426, 428, 429, 430, 432]
En el intervalo [433,456] hay 16 números que son múltiplos de {2, 3} y son: 
19: [434, 435, 436, 438, 440, 441, 442, 444, 446, 447, 448, 450, 452, 453, 454, 456]
En el intervalo [457,480] hay 16 números que son múltiplos de {2, 3} y son: 
20: [458, 459, 460, 462, 464, 465, 466, 468, 470, 471, 472, 474, 476, 477, 478, 480]
En el intervalo [481,504] hay 16 números que son múltiplos de {2, 3} y son: 
21: [482, 483, 484, 486, 488, 489, 490, 492, 494, 495, 496, 498, 500, 501, 502, 504]
En el intervalo [505,528] hay 16 números que son múltiplos de {2, 3} y son: 
22: [506, 507, 508, 510, 512, 513, 514, 516, 518, 519, 520, 522, 524, 525, 526, 528]
En el intervalo [529,552] hay 16 números que son múltiplos de {2, 3} y son: 
23: [530, 531, 532, 534, 536, 537, 538, 540, 542, 543, 544, 546, 548, 549, 550, 552]
En el intervalo [553,576] hay 16 números que son múltiplos de {2, 3} y son: 
24: [554, 555, 556, 558, 560, 561, 562, 564, 566, 567, 568, 570, 572, 573, 574, 576]
En el intervalo [577,600] hay 16 números que son múltiplos de {2, 3} y son: 
25: [578, 579, 580, 582, 584, 585, 586, 588, 590, 591, 592, 594, 596, 597, 598, 600]

Observación 9

Con la siguiente ejecución de código obtenemos los \(2^3\cdot 3\) intervalos de tamaño \(5^2\) que tienen números que son múltiplos de \(5\).

prel_mult_int(5**2, 2**3 * 3, "multiplos")

En el intervalo [1,25] hay 5 números que son múltiplos de {5} y son: 
1: [5, 10, 15, 20, 25]
En el intervalo [26,50] hay 5 números que son múltiplos de {5} y son: 
2: [30, 35, 40, 45, 50]
En el intervalo [51,75] hay 5 números que son múltiplos de {5} y son: 
3: [55, 60, 65, 70, 75]
En el intervalo [76,100] hay 5 números que son múltiplos de {5} y son: 
4: [80, 85, 90, 95, 100]
En el intervalo [101,125] hay 5 números que son múltiplos de {5} y son: 
5: [105, 110, 115, 120, 125]
En el intervalo [126,150] hay 5 números que son múltiplos de {5} y son: 
6: [130, 135, 140, 145, 150]
En el intervalo [151,175] hay 5 números que son múltiplos de {5} y son: 
7: [155, 160, 165, 170, 175]
En el intervalo [176,200] hay 5 números que son múltiplos de {5} y son: 
8: [180, 185, 190, 195, 200]
En el intervalo [201,225] hay 5 números que son múltiplos de {5} y son: 
9: [205, 210, 215, 220, 225]
En el intervalo [226,250] hay 5 números que son múltiplos de {5} y son: 
10: [230, 235, 240, 245, 250]
En el intervalo [251,275] hay 5 números que son múltiplos de {5} y son: 
11: [255, 260, 265, 270, 275]
En el intervalo [276,300] hay 5 números que son múltiplos de {5} y son: 
12: [280, 285, 290, 295, 300]
En el intervalo [301,325] hay 5 números que son múltiplos de {5} y son: 
13: [305, 310, 315, 320, 325]
En el intervalo [326,350] hay 5 números que son múltiplos de {5} y son: 
14: [330, 335, 340, 345, 350]
En el intervalo [351,375] hay 5 números que son múltiplos de {5} y son: 
15: [355, 360, 365, 370, 375]
En el intervalo [376,400] hay 5 números que son múltiplos de {5} y son: 
16: [380, 385, 390, 395, 400]
En el intervalo [401,425] hay 5 números que son múltiplos de {5} y son: 
17: [405, 410, 415, 420, 425]
En el intervalo [426,450] hay 5 números que son múltiplos de {5} y son: 
18: [430, 435, 440, 445, 450]
En el intervalo [451,475] hay 5 números que son múltiplos de {5} y son: 
19: [455, 460, 465, 470, 475]
En el intervalo [476,500] hay 5 números que son múltiplos de {5} y son: 
20: [480, 485, 490, 495, 500]
En el intervalo [501,525] hay 5 números que son múltiplos de {5} y son: 
21: [505, 510, 515, 520, 525]
En el intervalo [526,550] hay 5 números que son múltiplos de {5} y son: 
22: [530, 535, 540, 545, 550]
En el intervalo [551,575] hay 5 números que son múltiplos de {5} y son: 
23: [555, 560, 565, 570, 575]
En el intervalo [576,600] hay 5 números que son múltiplos de {5} y son: 
24: [580, 585, 590, 595, 600]

Observación 10

Con la siguiente ejecución de código obtenemos los \(5\) intervalos de tamaño \(2^3\cdot 3\cdot 5\) que tienen números que son múltiplos de \(2\) y \(5\) o de \(3\) y \(5\).

prel_mult_int(2**3 * 3 * 5, 5, "interseccion")

En el intervalo [1,120] hay 16 números que son múltiplos de 2 y 5 o 3 y 5: 
1: [10, 15, 20, 30, 40, 45, 50, 60, 70, 75, 80, 90, 100, 105, 110, 120]
En el intervalo [121,240] hay 16 números que son múltiplos de 2 y 5 o 3 y 5: 
2: [130, 135, 140, 150, 160, 165, 170, 180, 190, 195, 200, 210, 220, 225, 230, 240]
En el intervalo [241,360] hay 16 números que son múltiplos de 2 y 5 o 3 y 5: 
3: [250, 255, 260, 270, 280, 285, 290, 300, 310, 315, 320, 330, 340, 345, 350, 360]
En el intervalo [361,480] hay 16 números que son múltiplos de 2 y 5 o 3 y 5: 
4: [370, 375, 380, 390, 400, 405, 410, 420, 430, 435, 440, 450, 460, 465, 470, 480]
En el intervalo [481,600] hay 16 números que son múltiplos de 2 y 5 o 3 y 5: 
5: [490, 495, 500, 510, 520, 525, 530, 540, 550, 555, 560, 570, 580, 585, 590, 600]

Fórmula para el caso general de la función \(\varphi\)

Teorema 19

Sea \(n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) la descomposición canónica del entero positivo \(n\). Entonces

\[\varphi(n) = \varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}) = n \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) .\]

Demostración. Vamos a proceder por inducción en el número de primos que aparecen en la descomposición canónica del número \(n\).

Sea \(P(k)\) la proposición que afirma que para el entero positivo \(k\) se cumple que:

\[\varphi(n) = \varphi(p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3}\cdot \ldots \cdot p_{k-1}^{\alpha_{k-1}} p_k^{\alpha_k}) = n\left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right).\]

Base inductiva. Verifiquemos que \(P(1)\) es verdadera.
Ya demostramos en el Teorema 18 que el caso cuando \(k = 1\) se cumple.

\[\varphi(p_1^{\alpha_1}) = p_1^{\alpha_1} - p_1^{\alpha_1 -1} = p_1^{\alpha_1} \left( 1- \frac{1}{p_1} \right) = n \left( 1- \frac{1}{p_1} \right).\]

Hipótesis inductiva. Supongamos que \(P(1), P(2), P(3), \ldots , P(k)\) son verdaderas, es decir, que para el entero \(n = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) se cumple que:

\[\varphi(n) = \varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}) = n \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right).\]

Paso inductivo. Queremos probar que \(P(1), P(2), P(3), \ldots , P(k)\) implican \(P(k+1)\). Entonces tenemos lo siguiente.

Sea \(n= p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} p_{k+1}^{\alpha_{k+1}}\).

Sea \(|A|\) el conjunto de los números positivos menores o iguales que \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} p_{k+1}^{\alpha_{k+1}}\), entonces:

\[|A| = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1}^{\alpha_{k+1}}.\]

Sea \(B\) el conjunto de los números que son múltiplos de \(p_1,p_2, \ldots,p_k,p_{k+1}\), sin repetir algún elemento, menores o iguales que \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} p_{k+1}^{\alpha_{k+1}}\).

Vamos a descomponer al conjunto \(B\) como \(B = B_1 \cup B_2\).

Sea \(B_1\) el conjunto de los números positivos que son múltiplos de \(p_1,p_2, \ldots,p_k\) menores que \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\).

Por la hipótesis de inducción sabemos que la cantidad de primos relativos con el número \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) en el intervalo \([1,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}]\) es:

\[\varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}) = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right).\]

Entonces la cantidad de números que son múltiplos de \(p_1,p_2, \ldots,p_k\) serían:

\[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right).\]

Como esto todavía no llega hasta el número que deseamos \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\), utilizando la Proposición 18 tomamos intervalos de tamaño \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) hasta llegar al número deseado:

\[\begin{align*} &[1,2,\ldots,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}], \\ & \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} +1,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} +2,\ldots,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot 2], \\ & \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot 2 +1,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot 2 +2,\ldots,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot 3], \\ &\vdots \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot (p_{k+1}^{\alpha_{k+1}} - 2) +1,\ldots,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot (p_{k+1}^{\alpha_{k+1}} -1)], \\ & \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot (p_{k+1}^{\alpha_{k+1}} -1) +1,\ldots,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot (p_{k+1}^{\alpha_{k+1}})]. \end{align*}\]

Cada uno de estos intervalos tiene la misma cantidad de primos relativos con el número \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) que el intervalo \([1,p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}]\) y entonces también tiene la misma cantidad de números que son múltiplos de \(p_1,p_2, \ldots,p_k\). En total tenemos \(p_{k+1}^{\alpha_{k+1}}\) intervalos. Por lo tanto,

\[|B_1| = p_{k+1}^{\alpha_{k+1}} \left( p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \right).\]

Sea \(B_2\) el conjunto de los números positivos que son múltiplos de \(p_{k+1}^{\alpha_{k+1}}\) menores que \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} p_{k+1}^{\alpha_{k+1}}\). Por hipótesis sabemos que el número de primos relativos con \(p_{k+1}^{\alpha_{k+1}}\) en el intervalo \([1,p_{k+1}^{\alpha_{k+1}}]\) es:

\[\varphi(p_{k+1}^{\alpha_{k+1}}) = p_{k+1}^{\alpha_{k+1}} \left(1-\frac{1}{p_{k+1}} \right).\]

Entonces la cantidad de números que son múltiplos de \(p_{k+1}^{\alpha_{k+1}}\) serían:

\[p_{k+1}^{\alpha_{k+1}} - p_{k+1}^{\alpha_{k+1}} \left(1-\frac{1}{p_{k+1}} \right).\]

De igual manera para llegar hasta el número \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\), utilizando la Proposición 18, tomamos intervalos de tamaño \(p_{k+1}^{\alpha_{k+1}}\) hasta llegar al número deseado,

\[\begin{align*} &[1,2,\ldots,p_{k+1}^{\alpha_{k+1}}], \\ & \\ &[p_{k+1}^{\alpha_{k+1}} + 1, p_{k+1}^{\alpha_{k+1}}+2, \ldots, p_{k+1}^{\alpha_{k+1}} \cdot 2], \\ & \\ &[p_{k+1}^{\alpha_{k+1}} \cdot 2 +1, p_{k+1}^{\alpha_{k+1}} \cdot 2 +2, \ldots, p_{k+1}^{\alpha_{k+1}} \cdot 3], \\ &\vdots \\ &[p_{k+1}^{\alpha_{k+1}} \cdot (p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} -2) +1, \ldots, p_{k+1}^{\alpha_{k+1}} \cdot (p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} -1)], \\ & \\ &[p_{k+1}^{\alpha_{k+1}} \cdot (p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} -1) +1, \ldots, p_{k+1}^{\alpha_{k+1}} \cdot (p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k})]. \end{align*}\]

Cada uno de estos intervalos tiene la misma cantidad de primos relativos con el número \(p_{k+1}^{\alpha_{k+1}}\) que el intervalo \([1,p_{k+1}^{\alpha_{k+1}}]\) y entonces también tiene la misma cantidad de números que son múltiplos de \(p_{k+1}\). En total tenemos \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) intervalos. Por lo tanto,

\[|B_2| = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( p_{k+1}^{\alpha_{k+1}} - p_{k+1}^{\alpha_{k+1}} \left(1-\frac{1}{p_{k+1}} \right) \right).\]

Por último debemos calcular \(|B_1 \cap B_2|\). Para esto, notemos que para compartir factores con \(p_{k+1}\) se tiene que ser múltiplo de \(p_{k+1}\). Podemos hacer los siguientes intervalos de tamaño \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}\):

\[\begin{align*} &[1, 2, \ldots, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1}], \\ & \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} +1, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} +2, \ldots, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} \cdot 2], \\ & \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} \cdot 2 +1, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} \cdot 2 +2, \ldots, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} \cdot 3], \\ &\vdots \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} (p_{k+1}^{\alpha_{k+1} -1} -2) +1, \ldots, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} (p_{k+1}^{\alpha_{k+1} -1} -1) ], \\ & \\ &[p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} (p_{k+1}^{\alpha_{k+1} -1} -1) +1, \ldots, p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot p_{k+1} (p_{k+1}^{\alpha_{k+1} -1} )]. \end{align*}\]

Tenemos en total \(p_{k+1}^{\alpha_{k+1} -1}\) intervalos. En cada uno de estos intervalos de los cuales comparten factores con \(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\), la \(\frac{1}{p_{k+1}}\) parte son múltiplos de \(p_{k+1}\), con lo cual tenemos que:

\[|B_1 \cap B_2| = p_{k+1}^{\alpha_{k+1} -1} \left( p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \right).\]

Por lo tanto, tenemos lo siguiente:

\[\begin{align*} \varphi(n) &= \varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} p_{k+1}^{\alpha_{k+1}} ) \\ & \\ &= |A| - |B| \\ & \\ &= |A| - \left( |B_1 \cup B_2| \right) \\ & \\ &= |A| - \left( |B_1| + |B_2| - |B_1 \cap B_2| \right) \\ & \\ &= |A| - \left( |B_1| + |B_2| - |B_1 \cap B_2| \right) \\ & \\ &= |A| - \left( p_{k+1}^{\alpha_{k+1}} \left( p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \right) + p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( p_{k+1}^{\alpha_{k+1}} - p_{k+1}^{\alpha_{k+1}} \left(1-\frac{1}{p_{k+1}} \right) \right) - p_{k+1}^{\alpha_{k+1} -1} \left( p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \right) \right) \\ & \\ &= |A| - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}} \left( 1 -\left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) + \underline{1 - \left(1-\frac{1}{p_{k+1}} \right) - \frac{1}{p_{k+1}} } + \frac{1}{p_{k+1}}\left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \right) \\ & \\ &= |A| - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}} \left( 1 - \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) + \frac{1}{p_{k+1}}\left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \right) \\ & \\ &= |A| - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}} \left( 1 - \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \left( 1- \frac{1}{p_{k+1}} \right) \right) \\ & \\ &= \underline{ p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}} - p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}} }+ p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \left( 1- \frac{1}{p_{k+1}} \right) \\ &\\ & = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}p_{k+1}^{\alpha_{k+1}}\left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdot \ldots \cdot \left( 1- \frac{1}{p_k} \right) \left( 1- \frac{1}{p_{k+1}} \right). \square \end{align*}\]

Ejemplo 58

¿Cuántos números positivos menores a \(9000\) son primos relativos con \(9000\)? Utiliza la fórmula del Teorema 19 para calcularlo.

Solución.

Como \(9000 = 5^3\cdot 3^2 \cdot 2^3\), entonces tenemos lo siguiente:

\[\begin{align*} \varphi(9000) &= \varphi(5^3\cdot 3^2 \cdot 2^3) \\ &= 9000 \left(1 - \frac{1}{5}\right) \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{2}\right) \\ &= 9000 \left(\frac{4}{5}\right)\left(\frac{2}{3}\right)\left(\frac{1}{2}\right) \\ &= 2400. \end{align*}\]

Por lo tanto hay \(2400\) números menores que \(9000\) que son primos relativos con \(9000\).

Vamos a ver una propiedad importante de la función \(\varphi\) de Euler. Veamos un ejemplo antes de pasar a demostrar esta propiedad.

Ejemplo 59

Sean \(m=4\) y \(n=9\), verifica que se cumple que \(\varphi(36) = \varphi(4) \cdot \varphi(9)\).

Solución.

Listemos los enteros desde el \(1\) hasta el \(36\).

\[\begin{align*} \Rightarrow &1\checkmark & &5\checkmark & &9 & &13\checkmark & &17\checkmark & &21 & &17\checkmark & &29\checkmark & &33 \\ &2 & &6 & &10 & &14 & &18 & &22 & &26 & &30 & &34 \\ \Rightarrow &3 & &7\checkmark & &11\checkmark & &15 & &19\checkmark & &23\checkmark & &27 & &31\checkmark & &35\checkmark \\ &4 & &8 & &12 & &16 & &20 & &24 & &28 & &32 & &36. \end{align*}\]

Con la lista anterior podemos notar que en la segunda y cuarta línea no hay primos relativos con \(36\), ya que ninguno de esos números son primos relativos con \(4\) y por lo tanto no son primos relativos con \(36\). Sin embargo, los números que están en la primera y tercera línea si son primos relativos con \(4\). Además, en cada una de estas líneas hay \(6\) números que son primos relativos con \(9\), los cuales marcaremos con una \(\checkmark\). Así, tendríamos \(12\) números de la lista que son primos relativos con \(36\).
Entonces tenemos lo siguiente:

\[\varphi(36) = 12 = 2\cdot 6 = \varphi(4) \cdot \varphi(9).\]

Teorema 20

Sean \(m\) y \(n\) enteros positivos primos relativos, entonces \(\varphi(mn) =\varphi(m) \varphi(n)\).

Demostración. Sea \(N = mn\), en donde \(m = p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\) y \(n = q_1^{\alpha_1}q_2^{\alpha_2} \cdot \ldots \cdot q_j^{\alpha_j}\).

Por hipótesis sabemos que \(m\) y \(n\) son primos relativos, entonces tanto \(m\) como \(n\) no tienen divisores en común, es decir que cada \(p_i \neq q_t\), donde \(1\le i \le k\) y \(1\le t \le j\).

Luego, desarrollando el lado izquierdo usando Teorema 19 tenemos que:

\[\begin{align*} \varphi(mn) &= \varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot q_1^{\alpha_1}q_2^{\alpha_2} \cdot \ldots \cdot q_j^{\alpha_j}) \\ & \\ &= p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k} \cdot q_1^{\alpha_1}q_2^{\alpha_2} \cdot \ldots \cdot q_j^{\alpha_j} \left(1 - \frac{1}{p_1} \right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k} \right)\left(1 - \frac{1}{q_1} \right) \cdot \ldots \cdot \left(1 - \frac{1}{q_j} \right) \\ & \\ &= \left( p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}\left(1 - \frac{1}{p_1} \right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k} \right) \right) \left( q_1^{\alpha_1}q_2^{\alpha_2} \cdot \ldots \cdot q_j^{\alpha_j}\left(1 - \frac{1}{q_1} \right) \cdot \ldots \cdot \left(1 - \frac{1}{q_j} \right) \right) \\ & \\ &= \varphi(p_1^{\alpha_1}p_2^{\alpha_2} \cdot \ldots \cdot p_k^{\alpha_k}) \cdot \varphi(q_1^{\alpha_1}q_2^{\alpha_2} \cdot \ldots \cdot q_j^{\alpha_j}) \\ & \\ &= \varphi(m) \varphi(n). \square \end{align*}\]

Por último, veamos que el resultado de la función \(\varphi(n)\) de Euler es casi siempre par.

Teorema 21

Sea \(n\) un entero positivo mayor que \(2\). Entonces \(\varphi(n)\) es par.

Demostración. Sea \(n\) un entero positivo mayor que \(2\).

Supongamos que \(n = p_1^{\alpha_1} p_2^{\alpha_2} \cdot \ldots \cdot p_s^{\alpha_s}\) es la factorización en primos de \(n\). Como para cada uno de los primos \(p_s\) de la factorización cumple que \((p_i,p_j) = 1\), donde \(1\le i,j \le s\) entonces por el Teorema 20 tenemos que:

\[\varphi(n) = \prod_{k=1}^s\varphi(p_k^{\alpha_k}).\]

Luego, por Teorema 18 tenemos lo siguiente,

\[\varphi(n) = \prod_{k=1}^s\varphi(p_k^{\alpha_k}) = \prod_{k=1}^sp_k^{\alpha_k -1}(p_k - 1).\]

Podemos ver que \(\varphi(p_k^{\alpha_k}) = p_k^{\alpha_k -1}(p_k - 1)\) es par en cualquiera de los dos casos siguientes:

• Si \(p_k\) es un primo impar entonces \(p_k -1\) es par y asi \(p_k^{\alpha_k -1}(p_k - 1)\) es par.

• Si \(p_k = 2\) y \(\alpha_k >1\), entonces \(p_k^{\alpha_k -1}\) es par y asi \(p_k^{\alpha_k - 1}(p_k - 1)\) es par.

Dado que \(n>2\), al menos una de estas dos condiciones se cumple, por lo tanto \(\varphi(p_k^{\alpha_k}) = p_k^{\alpha_k}(p_k - 1)\) es par para al menos algún entero \(k\), en donde \(1 \le k \le s\).

Así, concluimos que \(\varphi(n)\) es par. \(\square\)

Código para calcular la función \(\varphi\)

El siguiente código nos ayudará a calcular el valor de la función \(\varphi(n)\). Para ello vamos a utilizar la función «factorizar_en_primos».

La siguiente función nos calcula el valor de la función \(\varphi(n)\) de Euler para un entero positivo \(n\).

def phi_euler(n):
    resultado = n
    sin_repetir = list(set(factorizar_en_primos(n)))
    for i in sin_repetir:
        resultado *= (1 - 1/ i)
    return int(resultado)

phi_euler(143)

120

phi_euler(59)

58

phi_euler(9000)

2400

phi_euler(13400509)

13400508

Explicación del código

En este capítulo utilizamos la función incorporada en Python any(). Ésta función evalúa una secuencia de valores y regresa True si al menos uno de los elementos es verdadero. Si todos son falsos, regresa False.
No es un condicional en sí, pero puede usarse dentro de condicionales para tomar decisiones basadas en si alguno de los valores cumple una condición.

Veamos cómo funcionan los códigos.

El primer código que creamos fue con el propósito de poder ver más a fondo la Proposición 18.

def prel_mult_int(numero, intervalos, opcion):
    for i in range(1,intervalos+1):
        int_1 = i*numero - numero +1
        int_2 = i*numero
        if opcion == "prelativos":
            primos_relativos = [x for x in range(int_1,int_2+1) if algoritmo_euclides(numero,x) == 1]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(primos_relativos)} primos relativos con {numero} y son: ")
            print(primos_relativos)
        elif opcion == "multiplos":
            primos = set(factorizar_en_primos(numero))
            multiplos = [x for x in range(int_1,int_2+1) if any(x % d == 0 for d in primos)]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(multiplos)} números que son múltiplos de {primos} y son: ")
            print(f"{i}: {multiplos}")
        elif opcion == "interseccion":
            interseccion = [x for x in range(int_1,int_2+1) if (x%2 == 0 and x%5 == 0) or (x%3 == 0 and x%5 == 0)]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(interseccion)} números que son múltiplos de 2 y 5 o 3 y 5: ")
            print(f"{i}: {interseccion}")
        else:
            print("Opción no válida. Ingresa como tercer argumento: 'prelativos', 'multiplos' o 'interseccion'.")

1. Definimos una función llamada «prel_mult_int» la cual recibe tres argumentos. El primero y el segundo argumento, son números enteros. El tercer argumento es «opcion», define el comportamiento de la función. Acepta únicamente los valores «prelativos», «multiplos» o «interseccion». Cada uno de estos valores indica un caso específico para ejecutar la lógica.

def prel_mult_int(numero, intervalos, opcion):

2. Empezamos un ciclo for el cual tiene como rango desde \(1\) hasta el número de intervalos que queremos crear.
   Luego, creamos las variables «int_1» y «int_2», las cuales nos ayudan a formar los bloques del tamaño del argumento «numero» que introducimos.

    for i in range(1,intervalos+1):
        int_1 = i*numero - numero + 1
        int_2 = i*numero

3. Creamos una estructura de control condicional. Dependiendo del valor que se de al argumento «opcion», es el código que se ejecuta.
   Si el valor del argumento «opcion» es «prelativos», el código entra en el condicional if. En el bloque identado creamos la variable «primos_relativos» la cual es una lista, ésta se crea con una comprensión de listas. Dentro de ella se inicia un ciclo for el cual recorre los valores dentro del intervalo \([int_1,int_2]\), si se cumple la condición de que el valor es primo relativo con «numero» éste se agrega a la lista. Una vez que se crea la lista, el código nos da a conocer el intervalo, la cantidad de primos relativos que hay con respecto a «numero» y una lista con todos los números. Este proceso se repite hasta crear todos los intervalos que le pedimos crear al código en la variable «intervalos».

        if opcion == "prelativos":
            primos_relativos = [x for x in range(int_1,int_2+1) if algoritmo_euclides(numero,x) == 1]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(primos_relativos)} primos relativos con {numero} y son: ")
            print(primos_relativos)

4. Si el valor del argumento «opcion» es «multiplos», el código entra en el primer condicional elif. En el bloque identado se crea la variable «primos», la cual es un conjunto que contiene los primos que aparecen en la factorización en primos de la variable «numero». Luego, creamos la variable «multiplos» la cual es una lista que se crea con una comprensión de listas. Dentro de ella se inicia un ciclo for el cual recorre los valores dentro del intervalo \([int_1,int_2]\), el valor se agrega a la lista si la función any() regresa un valor de True.
   Dentro de la función any() se revisa si el valor que tomamos del intervalo es divisible entre cualquiera de los primos del conjunto «primos». Si al menos un primo divide al valor, la función any() regresa True. Si ningún primo divide al valor entonces la función nos regresa un valor de False. Una vez que se termina de crear la lista, el código nos imprime el intervalo, el número de valores que contiene y de quién son múltiplos éstos, además de la lista con todos ellos. Este proceso se repite hasta crear todos los intervalos que le pedimos crear al código en la variable «intervalos».

        elif opcion == "multiplos":
            primos = set(factorizar_en_primos(numero))
            multiplos = [x for x in range(int_1,int_2+1) if any(x % d == 0 for d in primos)]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(multiplos)} números que son múltiplos de {primos} y son: ")
            print(f"{i}: {multiplos}")

5. Si el valor del argumento «opcion» es «interseccion», el código entra en el segundo condicional elif. En el bloque identado creamos la variable «interseccion» la cual es una lista, ésta se crea con una comprensión de listas. Dentro de ella se inicia un ciclo for el cual recorre los valores dentro del intervalo \([int_1,int_2]\), si se cumple la condición de que el valor es divisible entre \(2\) y \(5\) o entre \(3\) y \(5\), éste se agrega a la lista. Una vez que se crea la lista, el código nos da a conocer el intervalo, la cantidad de múltiplos de \(2\) y \(5\) o de \(3\) y \(5\) y una lista con todos los números. Este proceso se repite hasta crear todos los intervalos que le pedimos crear al código en la variable «intervalos».

        elif opcion == "interseccion":
            interseccion = [x for x in range(int_1,int_2+1) if (x%2 == 0 and x%5 == 0) or (x%3 == 0 and x%5 == 0)]
            print(f"En el intervalo [{int_1},{int_2}] hay {len(interseccion)} números que son múltiplos de 2 y 5 o 3 y 5: ")
            print(f"{i}: {interseccion}")

6. Finalmente, se el valor del argumento «opcion» no es ninguno de los \(3\) anteriores, el código nos dice que la opción no es válida y las opciones válidas.

        else:
            print("Opción no válida. Ingresa como tercer argumento: 'prelativos', 'multiplos' o 'interseccion' ")

El segundo código que creamos nos calcula el valor de la función \(\varphi(n)\) de Euler.

def phi_euler(n):
    resultado = n
    sin_repetir = list(set(factorizar_en_primos(n)))
    for i in sin_repetir:
        resultado *= 1 - 1/ i
    return int(resultado)

1. Definimos una función llamada «phi_euler» la cual recibe como argumento un número entero positivo \(n\).

def phi_euler(n):

2. Creamos la variable «resultado» para guardar el valor de \(n\). Y creamos la variable «sin_repetir» la cual es una lista que contiene los primos involucrados en la factorización en primos del número \(n\) sin repetir algunos de estos.

    resultado = n
    sin_repetir = list(set(factorizar_en_primos(n)))

3. Comenzamos un ciclo for el cual va tomando cada primo de la lista «sin_repetir» y calcula el valor de \(1 - \frac{1}{p}\) y se lo multiplica a la variable «resultado», en esta variable se va guardando el valor y se le siguen multiplicando los valores de cada uno de los primos en la lista siguiendo la idea de la fórmula para el caso general del Teorema 19. Finalmente la función nos regresa el valor de la variable «resultado», el cual sólo convertimos en entero porque Python nos calcula los valores pero deja ceros en los decimales, es decir, si el resultado es \(8\) Python nos regresa un valor flotante de \(8.00\).

    for i in sin_repetir:
        resultado *= 1 - 1/ i
    return int(resultado)

Ejercicios de práctica

1. Demuestra el regreso del Lema 7. Si \(\varphi(p) = p-1\) entonces \(p\) es primo.

2. Sea \(p\) primo y \(n\) un entero positivo. Demuestra que si \(p \nmid n\), entonces \(\varphi(p \cdot n) = (p-1)\cdot \varphi(n)\). Intenta dar un argumento que no use la fórmula del Teorema 19.

3. Sean \(m, n\) enteros positivos. Demuestra que si \(m \mid n\) entonces \(\varphi(m) \mid \varphi(n)\).

4. Demuestra lo siguiente:

   • \(\varphi( \sigma(666)) = 2 \varphi(666)\).

   • Si \(p\) es primo entonces \(\varphi(p) + \sigma(p) = 2p\).

5. Demuestra que si \(n\) es un entero positivo compuesto entonces \(\varphi(n) \le n - \sqrt{n}\).