Función totiente de Euler

En teoría de números , la función totiente de Euler cuenta los enteros positivos hasta un entero dado.${\displaystyle n}$que son relativamente primordiales para${\displaystyle n}$Se escribe usando la letra griega phi como${\displaystyle \varphi (n)}$o${\displaystyle \phi (n)}$y también puede llamarse función phi de Euler . En otras palabras, es el número de enteros${\displaystyle k}$en el rango${\displaystyle 1\leq k\leq n}$para el cual el máximo común divisor${\displaystyle \gcd(n,k)}$es igual a 1. ^{[ 2 ] [ 3 ]} Los enteros${\displaystyle k}$de esta forma a veces se denominan totalativos de${\displaystyle n}$.

Por ejemplo, los totales de${\displaystyle n=9}$son los seis números 1, 2, 4, 5, 7 y 8. Todos ellos son primos relativos con el 9, pero los otros tres números en este rango, 3, 6 y 9, no lo son, ya que${\displaystyle \gcd(9,3)=\gcd(9,6)=3}$y${\displaystyle \gcd(9,9)=9}$. Por lo tanto,${\displaystyle \varphi (9)=6}$. Como otro ejemplo,${\displaystyle \varphi (1)=1}$ya que para${\displaystyle n=1}$el único entero en el rango de 1 a${\displaystyle n}$es 1 en sí mismo, y${\displaystyle \gcd(1,1)=1}$.

La función totiente de Euler es una función multiplicativa , lo que significa que si dos números${\displaystyle m}$y${\displaystyle n}$son relativamente importantes, entonces${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$. ^{[ 4 ] [ 5 ]} Esta función da el orden del grupo multiplicativo de enteros módulo n (el grupo de unidades del anillo${\displaystyle \mathbb {Z} /n\mathbb {Z} }$). ^{[ 6 ]} También se utiliza para definir el sistema de cifrado RSA .

Leonhard Euler introdujo la función en 1763. ^{[ 7 ] [ 8 ] [ 9 ]} Sin embargo, en ese momento no eligió ningún símbolo específico para denotarla. En una publicación de 1784, Euler estudió la función más a fondo, eligiendo la letra griega${\displaystyle \pi }$para denotarlo: escribió${\displaystyle \pi D}$para "la multitud de números menores que${\displaystyle D}$y que no tienen divisor común con ella". ^{[ 10 ]} Esta definición difiere de la definición actual para la función totiente en${\displaystyle D=1}$pero por lo demás es lo mismo. La notación ahora estándar ^{[ 8 ] [ 11 ]}${\displaystyle \varphi (A)}$proviene del tratado de Gauss de 1801, Disquisitiones Arithmeticae , ^{[ 12 ] [ 13 ]} aunque Gauss no usó paréntesis alrededor del argumento y escribió${\displaystyle \varphi A}$Por lo tanto, a menudo se la denomina función phi de Euler o simplemente función phi .

En 1879, JJ Sylvester acuñó el término totiente para esta función, ^{[ 14 ] [ 15 ]} por lo que también se la conoce como función totiente de Euler , totiente de Euler o totiente de Euler . ^{[ 16 ]} La totiente de Jordan es una generalización de la de Euler.

El cototiente de${\displaystyle n}$se define como${\displaystyle n-\varphi (n)}$. Cuenta el número de enteros positivos menores o iguales a${\displaystyle n}$que tienen al menos un factor primo en común con${\displaystyle n}$.

Existen varias fórmulas para calcular${\displaystyle \varphi (n)}$.

Los primeros 100 valores (secuencia A000010 en el OEIS ) se muestran en la tabla y el gráfico a continuación:

En el gráfico de la derecha, la línea superior y = n − 1 es una cota superior válida para todos los n distintos de uno, y se alcanza si y solo si n es un número primo. Una cota inferior simple es${\displaystyle \varphi (n)\geq {\sqrt {n/2}}}$, lo cual es bastante impreciso: de hecho, el límite inferior del gráfico es proporcional a ⁠ n / log log n ⁠ . ^{[ 21 ]}

Esto establece que si a y n son primos relativos , entonces

${\displaystyle a^{\varphi (n)}\equiv 1\mod n.}$

El caso especial en el que n es primo se conoce como el pequeño teorema de Fermat .

Esto se deduce del teorema de Lagrange y del hecho de que φ ( n ) es el orden del grupo multiplicativo de los enteros módulo n .

El sistema criptográfico RSA se basa en este teorema: implica que la inversa de la función a ↦ a ^e mod n , donde e es el exponente de cifrado (público), es la función b ↦ b ^d mod n , donde d , el exponente de descifrado (privado), es el inverso multiplicativo de e módulo φ ( n ) . La dificultad de calcular φ ( n ) sin conocer la factorización de n es, por lo tanto, la dificultad de calcular d : esto se conoce como el problema RSA , que se puede resolver factorizando n . El propietario de la clave privada conoce la factorización, ya que una clave privada RSA se construye eligiendo n como el producto de dos primos grandes (elegidos aleatoriamente) p y q . Solo n se divulga públicamente, y dada la dificultad de factorizar números grandes, tenemos la garantía de que nadie más conoce la factorización.

• ${\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}$
• ${\displaystyle m\mid \varphi (a^{m}-1)}$
• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}$
  • En particular:
• ${\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}$
• ${\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}$
• ${\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}$

Compárelo con la fórmula${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$ (véase mínimo común múltiplo ).

• φ ( n ) es par para n ≥ 3 .Además, si n tiene r factores primos impares distintos, 2 ^r | φ ( n )
• Para cualquier a > 1 y n > 6 tal que 4 ∤ n existe un l ≥ 2 n tal que l | φ ( a ⁿ − 1) .
• ${\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}$

donde rad( n ) es el radical de n (el producto de todos los primos distintos que dividen a n ).

• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$ ^{[ 22 ]}
• ${\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1}$
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ( ^{[ 23 ]} citado en ^{[ 24 ]} )
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$[Liu (2016)]
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ^{[ 23 ]}
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k^{2}}}={\frac {6}{\pi ^{2}}}\log n+{\frac {6\gamma }{\pi ^{2}}}-{\frac {\zeta '(2)}{\zeta (2)^{2}}}+O\left({\frac {\log n}{n}}\right)}$^{[ 25 ]}
• ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)}$ ^{[ 26 ]}
• ${\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)}$ ^{[ 26 ]} (dondeγes laconstante de Euler-Mascheroni).

La serie de Dirichlet para φ ( n ) puede escribirse en términos de la función zeta de Riemann como: ^{[ 28 ]}

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}$

donde converge el lado izquierdo para${\displaystyle \Re (s)>2}$.

La función generadora de la serie de Lambert es ^{[ 29 ]}

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}$

que converge para | q | < 1 .

Ambas se demuestran mediante manipulaciones elementales de series y las fórmulas para φ ( n ) .

En palabras de Hardy y Wright, el orden de φ ( n ) es "siempre 'casi n '". ^{[ 30 ]}

Primero ^{[ 31 ]}

${\displaystyle \lim \sup {\frac {\varphi (n)}{n}}=1,}$

pero cuando n tiende a infinito, ^{[ 32 ]} para todo δ > 0

${\displaystyle {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}$

Estas dos fórmulas se pueden demostrar utilizando poco más que las fórmulas para φ ( n ) y la función de suma de divisores σ ( n ) .

De hecho, durante la demostración de la segunda fórmula, la desigualdad

${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,}$

Se demuestra que es cierto para n > 1 .

También tenemos ^{[ 21 ]}

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.}$

Aquí γ es la constante de Euler , γ = 0,577215665... , entonces e ^γ = 1,7810724... y e ^{− γ} = 0,56145948 ....

Demostrar esto no requiere exactamente el teorema de los números primos . ^{[ 33 ] [ 34 ]} Dado que log log n tiende a infinito, esta fórmula muestra que

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}=0.}$

De hecho, hay más. ^{[ 35 ] [ 36 ] [ 37 ]}

${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}$

y

${\displaystyle \varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.}$

La segunda desigualdad fue demostrada por Jean-Louis Nicolas . Ribenboim afirma: «El método de demostración es interesante, ya que la desigualdad se muestra primero bajo el supuesto de que la hipótesis de Riemann es verdadera, y en segundo lugar bajo el supuesto contrario». ^{[ 37 ] : 173}

Para el orden promedio, tenemos ^{[ 23 ] [ 38 ]}

${\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,}$

debido a Arnold Walfisz , su demostración explotando estimaciones sobre sumas exponenciales debidas a IM Vinogradov y NM Korobov . Mediante una combinación de los métodos de van der Corput y Vinogradov, H.-Q. Liu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) mejoró el término de error a

${\displaystyle O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$

(actualmente esta es la mejor estimación conocida de este tipo). La " O grande " representa una cantidad que está acotada por una constante multiplicada por la función de ⁿ dentro de los paréntesis (que es pequeña en comparación con n² ).

Este resultado se puede utilizar para demostrar ^{[ 39 ]} que la probabilidad de que dos números elegidos al azar sean primos relativos es 6 / π ² .

En 1950 Somayajulu demostró ^{[ 40 ] [ 41 ]}

${\displaystyle {\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}}$

En 1954, Schinzel y Sierpiński reforzaron esto, demostrando ^{[ 40 ] [ 41 ]} que el conjunto

${\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}}$

es denso en los números reales positivos. También demostraron ^{[ 40 ]} que el conjunto

${\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}}$

es denso en el intervalo (0,1).

Un número totiente es un valor de la función totiente de Euler: es decir, un m para el cual existe al menos un n tal que φ ( n ) = m . La valencia o multiplicidad de un número totiente m es el número de soluciones de esta ecuación. ^{[ 42 ]} Un no totiente es un número natural que no es un número totiente. Todo entero impar mayor que 1 es trivialmente un no totiente. También existen infinitos no totientes pares, ^{[ 43 ]} y, de hecho, todo entero positivo tiene un múltiplo que es un no totiente par. ^{[ 44 ]}

Los primeros números totientes son${\displaystyle 1,2,4,6,8,10,12,16,18,20}$, ver secuencia A002202 .

El número de números totientes hasta un límite dado x es

${\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}$

para una constante C = 0,8178146... . ^{[ 45 ]}

Si se cuenta de acuerdo con la multiplicidad, el número de números totientes hasta un límite dado x es

${\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}$

donde el término de error R es de orden como máximo ⁠ x / (log x ) ^k ⁠ para cualquier k positivo . ^{[ 46 ]}

Se sabe que la multiplicidad de m excede a m ^δ infinitas veces para cualquier δ < 0,55655 . ^{[ 47 ] [ 48 ]}

• Función de Carmichael (λ)
• Función psi de Dedekind (𝜓)
• Función divisora ​​(σ)
• Conjetura de Duffin-Schaeffer
• Generalizaciones del pequeño teorema de Fermat
• Número altamente compuesto
• Grupo multiplicativo de enteros módulo n
• Ramanujan sum
• Función sumativa totiente (𝛷)

• "Función totiente" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Función áurea de Euler y el teorema chino del resto: demostración de que φ ( n ) es multiplicativa. Archivado el 28/02/2021 en Wayback Machine.
• Calculadora de la función totiente de Euler en JavaScript: hasta 20 dígitos
• Dineva, Rosica, El totiente de Euler, la Möbius y las funciones divisorias. Archivado el 16 de enero de 2021 en Wayback Machine.
• Plytage, Loomis y Polhill resumen la función phi de Euler.