Función φ de Euler

función que da el número de enteros coprimos relativos y menores respecto a un número dado

La función φ de Euler (también llamada función indicatriz de Euler o función totiente) es una función importante en teoría de números. Si n es un número entero positivo, entonces φ(n) se define como la cantidad de enteros positivos menores a n y coprimos con n, es decir, formalmente se puede definir como:[2][3]

Los primeros mil valores de .[1]

donde |·| significa la cardinalidad del conjunto descrito.

Otra forma de definir el totiente de un número natural n es indicar que es la cantidad de números enteros positivos menores que n tales que el máximo común divisor con respecto a n es igual a 1.

La función φ es importante principalmente porque proporciona el tamaño del grupo multiplicativo de enteros módulo n. Más precisamente, es el orden del grupo de unidades del anillo . En efecto, junto con el teorema de Lagrange de los posibles tamaños de subgrupos de un grupo, proporciona una demostración del teorema de Euler que dice que para todo a coprimo con n. La función φ juega también un papel clave en la definición del sistema de cifrado RSA.

Historia, terminología y notación editar

Leonhard Euler introdujo la función en 1763.[4][5][6]​ Sin embargo, en ese momento no eligió ningún símbolo específico para denotarla. En una publicación de 1784, Euler estudió de nuevo la función más a fondo, eligiendo la letra griega π para denotarla: escribió πD para "la multitud de números menores que D, y que no tienen un divisor común con él".[7]​ Esta definición varía de la definición actual de la función totiente en D = 1 pero, por lo demás, es la misma. La notación ahora estándar[5][8]φ(A) proviene del tratado de Carl Friedrich Gauss de 1801 Disquisitiones arithmeticae,[9][10]​ aunque Gauss no usó paréntesis alrededor del argumento y escribió φA. Por lo tanto, a menudo se la llama función phi de Euler o simplemente función phi.

En 1879, J. J. Sylvester acuñó el término totiente para esta función,[11][12]​ por lo que también se la conoce como función totiente de Euler, totiente de Euler, o el totiente de Euler. El totiente de Jordan es una generalización de la idea de Euler.

El cototiente de   se define como  . Cuenta el número de enteros positivos menores o iguales a   que tienen al menos un factor primo en común con  .

Primeras propiedades y cálculo de la función editar

Se sigue de la definición que  , pues el elemento   sólo puede ser coprimo consigo mismo. Para otros números se cumple que:

  1.   si   es primo.
  2.   si   es primo y   es un número natural.
  3.   es una función multiplicativa: si   y   son coprimos, entonces  .

La primera propiedad se demuestra fácilmente, porque un número primo es coprimo con todos sus números anteriores. Y, por tanto, existen   elementos coprimos con  . En otras palabras, como   es primo sólo tendrá de divisores a sí mismo y a la unidad, la cual está presente en los   números anteriores a  .

Para la segunda propiedad, debemos observar que si   es primo sólo sus múltiplos   menores o iguales que   presentan un común divisor con   distinto de uno. Esto es,   son los únicos números   tales que  . Como en total hay   números que satisfacen esta propiedad, el resto de números entre   y   sólo tienen a   como divisor común con  . Esto es,  . (Nótese que esta segunda propiedad se cumple porque   es primo. En efecto, si hubiera un  ,   tal que  , entonces   sería divisor de   (  veces); es decir,   sería una potencia (y por consiguiente múltiplo) de  , contradiciendo la suposición inicial  ).

Para demostrar la tercera propiedad, sean  ,  ,   los conjuntos de enteros positivos que son coprimos y menores que  ,  ,   respectivamente ( entonces  ,   y   ). Luego, por el Teorema Chino del Resto existe una biyección entre   y  , lo que implica que  .

Con esto, el valor de   puede calcularse empleando el Teorema Fundamental de la Aritmética: si

 

donde los pj son números primos distintos, entonces

 

Esta fórmula puede reescribirse de la siguiente manera (conocida como la Fórmula de Producto de Euler):

 

donde los   son los distintos primos que dividen a  .

Ejemplo de cálculo editar

 

También,

 

Se puede comprobar manualmente que los números coprimos con 36 (o sea, que no son divisibles por 2 ni por 3) son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.

Transformada de Fourier editar

El totiente es la transformada de Fourier discreta del mcd, evaluado en 1.[13]​ Sea

 

donde xk = mcd(k,n) para k ∈ {1, ..., n}. Entonces

 

La parte real de esta fórmula es

 

A diferencia del producto de Euler y la fórmula de la suma del divisor, esta no requiere conocer los factores de n. Sin embargo, implica el cálculo del máximo común divisor de n y todo número entero positivo menor que n, lo que es suficiente para proporcionar la factorización de todos modos.

Suma de sus divisores editar

La propiedad establecida por Gauss,[14]​ de que

 

donde la suma es sobre todos los divisores positivos d de n, se puede demostrar de varias maneras (véase función aritmética para conocer las convenciones de la notación).

Una prueba es notar que φ(d) también es igual al número de posibles generadores del grupo cíclico Cd; específicamente, si Cd = ⟨g con gd= 1, entonces gk es un generador para cada coprimo de k a d. Dado que cada elemento de Cn genera un subgrupo cíclico, y todos los subgrupos CdCn son generados precisamente por elementos φ(d) de Cn, la fórmula es la siguiente.[15]​ De manera equivalente, la fórmula se puede derivar mediante el mismo argumento aplicado al grupo multiplicativo de las raíces de unidad n-ésimas raíces de la unidad y d-ésimas primitivas.

La fórmula también se puede derivar de la aritmética elemental.[16]​ Por ejemplo, sea n = 20 y considérense las fracciones positivas hasta 1 con denominador 20:

 

Reduciéndolas a términos mínimos:

 

Estas veinte fracciones son todas las k/d ≤ 1 positivas cuyos denominadores son los divisores d = 1, 2, 4, 5, 10, 20. Las fracciones con 20 como denominador son aquellas con numeradores relativamente primos a 20, a saber, 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20 y 19/20. Por definición, se trata de las φ(20) fracciones con denominador 20. De manera similar, hay φ(10) fracciones con denominador 10 y φ(5) fracciones con denominador 5, etc. Por lo tanto, el conjunto de veinte fracciones se divide en subconjuntos de tamaño φ(d) para cada d que divide 20. Se aplica un argumento similar para cualquier n.

La fórmula de inversión de Möbius aplicada a la fórmula de la suma del divisor da

 

donde μ es la función de Möbius, la función multiplicativa definida por   y   para cada primo p y k ≥ 2. Esta fórmula también se puede derivar de la fórmula del producto multiplicando   para obtener  

Un ejemplo:

 

Algunos valores editar

 
Representación gráfica de los 100 primeros valores. Nótese que el límite inferior marcado por la recta y = 4n/15 no es el límite inferior de la función de manera global, sino para múltiplos de 30.

Los 99 primeros valores de la función vienen escritos en la siguiente tabla, así como gráficamente.

  +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Teorema de Euler editar

El teorema de Euler establece que si a y n son números coprimos, entonces

 

El caso especial donde 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 enteros módulo n.

El sistema de encriptado RSA se basa en este teorema: implica que el inverso de la función aae mod n, donde e es el exponente de cifrado (público), es la función bbd 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 números primos grandes (elegidos al azar) p y q. Solo n se divulga públicamente y, dada la dificultad de factorizar números muy largos, se tiene la garantía de que nadie más conocerá la factorización.

Otras fórmulas editar

  •  
  •   (   ,   ) : Sea   . Entonces tenemos que:

  . Luego, por el Teorema de Lagrange,   divide a   .

 Pero   si   , y además   .

 Por lo tanto,  

  •   , donde  

 Nótense los casos especiales:

  •  
  •  
  •  

  Compárese esto con la fórmula   (véanse mínimo común múltiplo (mcm) y máximo común divisor (mcd)).

  • φ(n) es par para n ≥ 3. Además, si n tiene r factores primos impares distintos, 2r | φ(n)
  • Para cualquier a > 1 y n > 6 tal que 4 ∤ n existe un l ≥ 2n tal que l | φ(an − 1).
  •   ,

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

  •  [17]
  •  
  •   ([18]​ citado en[19]​)
  •  [18]
  •  [20]
  •  [20]​ ,

 donde γ es la constante de Euler-Mascheroni.

  •   ,

 donde m > 1 es un entero positivo y ω(m) es el número de factores primos distintos de m.[21][22]

Identidad de Menon editar

En 1965, P. Kesava Menon demostró que

  ,

donde d(n) = σ0(n) es el número de divisores de n.

Fórmulas que involucran la proporción áurea editar

Schneider[23]​ encontró un par de identidades que conectan la función totiente, el número áureo y la función de Möbius μ(n). En esta sección, φ(n) es la función totiente y ϕ = 1 + 5/2 = 1.618... es la proporción áurea.

Se tiene que:

 

y

 

Si se restan, se obtiene

 

La aplicación de la función exponencial a ambos lados de la identidad anterior produce una fórmula de producto infinito vinculada a e:

 

La demostración se basa en las dos fórmulas siguientes

 

Funciones generadoras editar

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

 

donde el lado izquierdo converge para  .

La función generadora de la serie de Lambert es[25]

 

que converge para | q | < 1.

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

Tasa de crecimiento editar

En palabras de Hardy & Wright, el orden de φ(n) es "siempre «casi n»".[26]

Primero[27]

 

pero como n tiende a infinito,[28]​ para todo δ > 0

 

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

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

 

verdadera para n > 1, está probada.

También se tiene que[29]

 

Aquí γ es la constante de Euler, γ = 0.577215665..., entonces eγ = 1.7810724... y eγ = 0.56145948....

Probar esto no requiere del todo el teorema de los números primos.[30][31]​ Dado que log log n tiende a infinito, esta fórmula muestra que

 

Y de hecho, se comprueban más propiedades,[32][33][34]​ como

 

y

 

La segunda desigualdad fue demostrada por Jean-Louis Nicolas. Ribenboim señaló que: "El método de prueba es interesante, ya que la desigualdad se muestra primero bajo el supuesto de que la hipótesis de Riemann es verdadera, y luego bajo el supuesto contrario".[34]: 173 

Para el orden promedio, se tiene que[18][35]

 

Este resultado, debido a Arnold Walfisz, se demostró explotando las estimaciones sobre sumas exponenciales debidas a I. M. Vinogradov y N. M. Korobov.

Mediante una combinación de los métodos de van der Corput y Vinogradov, H.-Q. Liu (Sobre la función de Euler. Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) mejoró el término de error hasta

 

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

Este resultado se puede usar para demostrar[36]​ que la probabilidad de que dos números elegidos al azar sean primos relativos es 6/π2.

Relación entre valores consecutivos editar

En 1950, Somayajulu probó[37][38]​ que

 

En 1954 Schinzel y Sierpiński fortalecieron esta proposición, probando[37][38]​ que el conjunto

 

es denso en los números reales positivos. También probaron[37]​ que el conjunto

 

es denso en el intervalo (0,1).

Números totientes editar

Un número totiente es un valor de la función totiente de Euler: es decir, un m para el que hay al menos un n para el que φ(n) = m. La valencia o multiplicidad de un número totiente m es el número de soluciones de esta ecuación.[39]​ Un número no totiente es un número natural que no es un número totiente. Todo entero impar que exceda de 1 es trivialmente un número no totiente. También hay un número infinito de no totientes pares,[40]​ y, de hecho, cada entero positivo tiene un múltiplo que es un no totiente par.[41]

La cantidad de números totientes hasta un límite dado x es

 

para una constante C = 0.8178146....[42]

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

 

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

Se sabe que la multiplicidad de m supera a mδ infinitamente a menudo para cualquier δ < 0.55655.[44][45]

Teorema de Ford editar

Ford (1999) demostró que para todo entero k ≥ 2 existe un número totiente m de multiplicidad k: es decir, para el cual la ecuación φ(n) = m tiene exactamente k soluciones; este resultado había sido previamente conjeturado por Wacław Sierpiński,[46]​ y se había obtenido como consecuencia de la hipótesis H de Schinzel.[42]​ De hecho, cada multiplicidad que se produce, lo hace infinitamente a menudo.[42][45]

Sin embargo, no se conoce ningún número m con multiplicidad k = 1. La conjetura de la función totiente de Carmichael es la afirmación de que no existe tal m.[47]

Números totientes perfectos editar

Los números totientes perfectos son aquellos que son iguales a la suma de sus totientes sucesivos. Existe una familia de estos números relacionados con las potencias de tres, así como con los productos de estas potencias por algunos números primos.

Aplicaciones editar

Ciclotomía editar

En la última sección de las Disquisitiones,[48][49]​ Gauss demostró[50]​ que un n-ágono regular se puede construir con regla y compás si φ(n) es una potencia de 2. Si n es una potencia de un número primo impar, la fórmula para el totiente dice que su totiente puede ser una potencia de dos solo si n es una potencia primera y n − 1 es una potencia de 2. Los números primos que son uno más que una potencia de 2 se llaman números primos de Fermat y solo se conocen cinco: 3, 5, 17, 257 y 65537. Fermat y Gauss conocían estos datos, y posteriormente nadie ha podido comprobar si hay más de estos números.

Por lo tanto, un n-ágono regular tiene una construcción con regla y compás si n es un producto de números primos de Fermat distintos y cualquier potencia de 2. Los primeros n son[51]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (sucesión A003401 en OEIS).

Teorema de los números primos para progresiones aritméticas editar

El criptosistema RSA editar

Configurar un sistema RSA implica elegir dos números primos grandes p y q, calcular n = pq y k = φ(n) y encontrar dos números e y d tales que ed ≡ 1 (mod k). Los números n y e (la "clave de cifrado") se divulgan al público y d (la "clave de descifrado") se mantiene en privado.

Un mensaje, representado por un número entero m, donde 0 < m < n, se cifra calculando S = me (mod n).

Y se descifra calculando t = Sd (mod n). El teorema de Euler se puede usar para demostrar que si 0 < t < n, entonces t = m.

La seguridad de un sistema RSA se vería comprometida si el número n pudiera factorizarse eficientemente o si φ(n) pudiera calcularse eficientemente sin factorizar n.

Problemas no resueltos editar

Conjetura de Lehmer editar

Si p es primo, entonces φ(p) = p − 1. En 1932 Derrick Henry Lehmer planteó la cuestión de si hay algún número compuesto n tal que φ(n) divida a n − 1. No se conoce ninguno.[52]

En 1933 demostró que si existe tal n, debe ser impar, sin cuadrados y divisible por al menos siete números primos (es decir, ω(n) ≥ 7). En 1980 Cohen y Hagis probaron que n > 1020 y que ω(n) ≥ 14.[53]​ Además, Hagis demostró que si 3 divide a n, entonces n > 101937042 y ω(n) ≥ 298848.[54][55]

Conjetura de Carmichael editar

Este enunciado establece que no hay ningún número n con la propiedad de que para todos los demás números m, mn, φ(m) ≠ φ(n). Véase el teorema de Ford más arriba.

Como se indica en el artículo principal, si hay un solo contraejemplo a esta conjetura, debe haber un número infinito de contraejemplos, y el más pequeño tiene al menos diez mil millones de dígitos en base 10.[39]

Hipótesis de Riemann editar

La hipótesis de Riemann es verdadera si y solo si la desigualdad

 

es cierta para todo np120569#, donde γ es la constante de Euler-Mascheroni y p120569# es el producto de los primeros 120569 números primos.[56]

Véase también editar

Referencias editar

  1. «Euler's totient function». Khan Academy. Consultado el 26 de febrero de 2016. 
  2. Long (1972, p. 85)
  3. Pettofrezzo y Byrkit (1970, p. 72)
  4. L. Euler "Theoremata arithmetica nova methodo demonstrata" (An arithmetic theorem proved by a new method), Novi commentarii academiae scientiarum imperialis Petropolitanae (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), 8 (1763), 74–104. (La obra fue presentada en la Academia de San Petersburgo el 15 de octubre de 1759. Una obra con el mismo título fue presentada en la Academia de Berlín el 8 de junio de 1758). Disponible en línea en: Ferdinand Rudio, ed., Leonhardi Euleri Commentationes Arithmeticae, volume 1, in: Leonhardi Euleri Opera Omnia, series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), pages 531–555. On page 531, Euler defines n as the number of integers that are smaller than N and relatively prime to N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), que es la función fi, φ(N).
  5. a b Sandifer, p. 203
  6. Graham et al. p. 133 note 111
  7. L. Euler, Speculationes circa quasdam insignes proprietates numerorum, Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (La obra fue presentada en la Academia de San Petersburgo el 9 de octubre de 1775).
  8. Both φ(n) and ϕ(n) are seen in the literature. These are two forms of the lower-case Greek letter φ.
  9. Gauss, Disquisitiones Arithmeticae article 38
  10. Cajori, Florian (1929). A History Of Mathematical Notations Volume II. Open Court Publishing Company. §409. 
  11. J. J. Sylvester (1879) "On certain ternary cubic-form equations", American Journal of Mathematics, 2 : 357-393; Sylvester coins the term "totient" on page 361.
  12. "totient". Oxford English Dictionary (2nd ed.). Oxford University Press. 1989.
  13. Schramm (2008)
  14. Gauss, DA, art 39
  15. Gauss, DA art. 39, arts. 52-54
  16. Graham et al. pp. 134-135
  17. Dineva (en referencias externas), prop. 1
  18. a b c Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (en alemán) 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003. 
  19. Lomadse, G. (1964), «The scientific work of Arnold Walfisz», Acta Arithmetica 10 (3): 227-237, doi:10.4064/aa-10-3-227-237 .
  20. a b Sitaramachandrarao, R. (1985). «On an error term of Landau II». Rocky Mountain J. Math. 15 (2): 579-588. doi:10.1216/RMJ-1985-15-2-579. 
  21. Bordellès in the external links
  22. «Number theory - Reference for Euler totient function identity?». 
  23. Todas las fórmulas en la sección son de Schneider (en los enlaces externos)
  24. Hardy y Wright, 1979, thm. 288
  25. Hardy y Wright, 1979, thm. 309
  26. Hardy y Wright, 1979, intro to § 18.4
  27. Hardy y Wright, 1979, thm. 326
  28. Hardy y Wright, 1979, thm. 327
  29. Hardy y Wright, 1979, thm. 328
  30. De hecho, el teorema de Chebyshov (Hardy y Wright, 1979, thm.7) y el tercer teorema de Mertens es todo lo que se necesita.
  31. Hardy y Wright, 1979, thm. 436
  32. Theorem 15 of Rosser, J. Barkley; Schoenfeld, Lowell (1962). «Approximate formulas for some functions of prime numbers». Illinois J. Math. 6 (1): 64-94. doi:10.1215/ijm/1255631807. 
  33. Bach & Shallit, thm. 8.8.7
  34. a b Ribenboim (1989). «How are the Prime Numbers Distributed? §I.C The Distribution of Values of Euler's Function». The Book of Prime Number Records (2nd edición). New York: Springer-Verlag. pp. 172-175. ISBN 978-1-4684-0509-5. doi:10.1007/978-1-4684-0507-1_5. 
  35. Sándor, Mitrinović & Crstici (2006) pp.24–25
  36. Hardy y Wright, 1979, thm. 332
  37. a b c Ribenboim, p.38
  38. a b Sándor, Mitrinović & Crstici (2006) p.16
  39. a b Guy (2004) p.144
  40. Sándor & Crstici (2004) p.230
  41. Zhang, Mingzhi (1993). «On nontotients». Journal of Number Theory 43 (2): 168-172. ISSN 0022-314X. Zbl 0772.11001. doi:10.1006/jnth.1993.1014. 
  42. a b c Ford, Kevin (1998). «The distribution of totients». Ramanujan J. Developments in Mathematics 2 (1–2): 67-151. ISBN 978-1-4419-5058-1. ISSN 1382-4090. Zbl 0914.11053. arXiv:1104.3264. doi:10.1007/978-1-4757-4507-8_8. 
  43. Sándor et al (2006) p.22
  44. Sándor et al (2006) p.21
  45. a b Guy (2004) p.145
  46. Sándor & Crstici (2004) p.229
  47. Sándor & Crstici (2004) p.228
  48. Gauss, DA. The 7th § is arts. 336–366
  49. Gauss probó que si n satisface ciertas condiciones, entonces se puede construir con regla y compás el correspondiente n-ágono. En 1837 Pierre Wantzel demostró el enunciado recíproco, es decir, que si el n-ágono es construible, entonces n debe satisfacer las condiciones de Gauss.
  50. Gauss, DA, art 366
  51. Gauss, DA, art. 366. Esta lista es el último párrafo en las Disquisitiones
  52. Ribenboim, pp. 36–37.
  53. Cohen, Graeme L.; Hagis, Peter, Jr. (1980). «On the number of prime factors of n if φ(n) divides n − 1». Nieuw Arch. Wiskd. III Series 28: 177-185. ISSN 0028-9825. Zbl 0436.10002. 
  54. Hagis, Peter, Jr. (1988). «On the equation M·φ(n) = n − 1». Nieuw Arch. Wiskd. IV Series 6 (3): 255-261. ISSN 0028-9825. Zbl 0668.10006. 
  55. Guy (2004) p.142
  56. Broughan, Kevin (2017). Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents (First edición). Cambridge University Press. ISBN 978-1-107-19704-6.  Corollary 5.35

Bibliografía editar

Las Disquisitiones Arithmeticae han sido traducidas del latín al inglés y al alemán. La edición alemana incluye todos los artículos de Gauss sobre teoría de números: todas las pruebas de la reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre la reciprocidad bicuadrática y notas inéditas.

Las referencias a las Disquisitiones son de la forma Gauss, DA, art. nnn.

Enlaces externos editar