7.5: La función PHI de Euler
- Page ID
- 118516
Después de leer las dos secciones anteriores, probablemente te estés preguntando por qué afirmamos el Principio de Inclusión-Exclusión de una manera tan abstracta, ya que en esos ejemplos\(N(S)\) dependía solo del tamaño\(S\) y no de su contenido. En esta sección, producimos un ejemplo importante donde el valor de\(N(S)\) sí depende\(S\). Sin embargo, somos capaces de hacer una reducción para obtener un resultado final útil. En lo que sigue, vamos a\(\mathbb{N}\) denotar el conjunto de enteros positivos.
Para un entero positivo\(n \geq 2\), let
\(\phi(n)=|\{m \in \mathbb{N}:m \leq n,gcd(m,n)=1\}|\).
Esta función se suele llamar la función de Euler o la \(\phi\)función totiente de Euler y tiene muchas conexiones con la teoría de números. Aquí no nos centraremos en los aspectos teóricos de números, solo siendo capaces de computar\(\phi(n)\) eficientemente para cualquiera\(n\).
Por ejemplo,\(\phi(12)=4\) ya que los únicos números desde\(\{1,2,…,12\}\) que son relativamente primos hasta 12 son 1, 5, 7 y 11. Como segundo ejemplo,\(\phi(9)=6\) ya que 1, 2, 4, 5, 7 y 8 son relativamente primos a 9. Por otro lado,\(\phi(p)=p−1\) cuando\(p\) es un prime. Supongamos que se le pidió que computara\(\phi(321974)\). ¿Cómo procedería?
En el capítulo 3 discutimos un procedimiento recursivo para determinar el mayor divisor común de dos enteros, y escribimos código para lograr esta tarea. Supongamos que tenemos una función gcd (m, n) que devuelve el mayor divisor común de los enteros m y n. (Convenientemente suficiente, SaeMath viene con una función incorporada.) Entonces podemos calcular\(\phi(n)\) con este fragmento de código:
//código
Ejecutar el código anterior responde casi de inmediato eso\(\phi(321974)=147744\). (Como es habitual, en la versión web del texto, se puede cambiar el valor 321974 para calcular el valor de\(\phi\) para otros enteros. Sin embargo, si intenta aumentar el valor de n para que sea demasiado grande, puede encontrarse con problemas de memoria impuestos por el Sage Cell Server utilizado por el texto. Por ejemplo, intentar calcular\(\phi(319572943)\) da como resultado un error al momento de escribir. (Es posible que tengas más suerte ejecutando el código directamente en SaeMath Cloud o una instalación local de SaeMath.)
Dadas estas dificultades, ¿cómo podríamos encontrarlas\(\phi(1369122257328767073)\)?
Claramente, ¡el programa es inútil para hacer frente a esta bestia! No solo itera\(n−2\) tiempos sino que también invoca una recursión durante cada iteración. Afortunadamente, la Inclusión-Exclusión viene al rescate.
Dejar\(n \geq 2\) ser un entero positivo y supongamos que\(n\) tiene\(m\) distintos factores primos:\(p_1, p_2,…,p_m\). Entonces
\(\phi(n) = n\displaystyle \prod_{i=1}^m \dfrac{p_i-1}{p_i}\)
Nuestra prueba de Teorema 7.14 requiere de la siguiente proposición elemental cuya prueba dejamos como ejercicio.
Dejar\(n \geq 2, k \geq 1\), y dejar que\(p_1,p_2,…,p_k\) sean primos distintos cada uno de los cuales se divide de\(n\) manera uniforme (sin resto). Entonces el número de números enteros de los\(\{1,2,…,n\}\) que son divisibles por cada uno de estos\(k\) primos es
\(\dfrac{n}{p_1p_2 \cdot \cdot \cdot p_k}\)
- Prueba
-
Presentamos el argumento cuándo\(m=3\). El resultado completo es una extensión fácil.
A la luz de la Proposición 7.15, el Principio de Inclusión-Exclusión arroja:
\(\phi(n) = n - (\dfrac{n}{p_1} + \dfrac{n}{p_2} + \dfrac{n}{p_3}) + (\dfrac{n}{p_1p_2} + \dfrac{n}{p_1p_3} + \dfrac{n}{p_2p_3}) - \dfrac{n}{p_1p_2p_3}\)
\( = n \dfrac{p_1p_2p_3 - (p_2p_3 + p_1p_3 + p_1p_2) + (p_3+p_2+p_1) -1}{p_1p_2p_3}\)
\( = n \dfrac{p_1 -1}{p_1} \dfrac{p_2 - 1}{p_2} \dfrac{p_3 - 1}{p_3}\).
SaeMath informa que
\(1369122257328767073=(3)^3(11)(19)^4(31)^2(6067)^2\)
es la factorización de\(1369122257328767073\) en primos. De ello se deduce que
\(\phi(1369122257328767073)=1369122257328767073\)\(\dfrac{2}{3} \dfrac{10}{11} \dfrac{18}{19} \dfrac{30}{31} \dfrac{6066}{6067}\).
Así SaeMath informa rápidamente que
\(\phi(1369122257328767073)=760615484618973600\).
Amanda y Bruce reciben el mismo reto de su profesor, a saber, encontrar\(\phi(n)\) cuándo
\(n=314849727861997688894791078609643681715439846090179313900192215985166853104070853972232932490281335924101693211209710523\).
No obstante el profesor también le dice a Amanda que\(n=p_1p_2\) es producto de dos grandes primos donde
\(p_1=470287785858076441566723507866751092927015824834881906763507\)
y
\(p_2=669483106578092405936560831017556154622901950048903016651289\).
¿Esta información es de algún valor especial para Amanda? ¿Realmente hace su trabajo más fácil que el de Bruce? ¿Nivelaría el campo de juego si el profesor le\(n\) dijera a Bruce que eso era producto de dos primos?