Número de números enteros coprimos y no superiores a n
En teoría de números , la función totient de Euler cuenta los números enteros positivos hasta un entero dado n que son primos relativos con n . Se escribe usando la letra griega phi como o , y también puede denominarse función phi de Euler . En otras palabras, es el número de enteros k en el rango 1 ≤ k ≤ n para los cuales el máximo común divisor mcd( n , k ) es igual a 1. [2] [3] Los enteros k de esta forma a veces son denominados totales de n .
Por ejemplo, los totales de n = 9 son los seis números 1, 2, 4, 5, 7 y 8. Todos son primos relativos con respecto a 9, pero los otros tres números en este rango, 3, 6 y 9, no lo son. , ya que mcd(9, 3) = mcd(9, 6) = 3 y mcd(9, 9) = 9 . Por tanto, φ (9) = 6 . Como otro ejemplo, φ (1) = 1 ya que para n = 1 el único número entero en el rango de 1 an es el propio 1, y mcd(1, 1) = 1 .
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 π para denotarla: escribió πD para "la multitud de números menores que D , y que no tienen ningún divisor común con él". [10] Esta definición varía de la definición actual para la función totient en D = 1, pero por lo demás es la misma. La notación ahora estándar [8] [11] φ ( A ) proviene del tratado Disquisitiones Arithmeticae de Gauss de 1801 , [12] [13] aunque Gauss no usó paréntesis alrededor del argumento y escribió φ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 totient para esta función, [14] [15] por lo que también se la conoce como función totient de Euler , totient de Euler o totient de Euler . El paciente de Jordan es una generalización del de Euler.
El cotociente de n se define como n − φ ( n ) . Cuenta el número de enteros positivos menores o iguales que n que tienen al menos un factor primo en común con n .
Una formulación equivalente es dónde está la factorización prima de (es decir, son números primos distintos).
La prueba de estas fórmulas depende de dos hechos importantes.
Phi es una función multiplicativa
Esto significa que si mcd( m , n ) = 1 , entonces φ ( m ) φ ( n ) = φ ( mn ) . Esquema de prueba: Sean A , B , C los conjuntos de números enteros positivos que son coprimos y menores que m , n , mn , respectivamente, de modo que | Un | = φ ( m ) , etc. Entonces hay una biyección entre A × B y C según el teorema del resto chino .
Valor de phi para un argumento de potencia prima
Si p es primo y k ≥ 1 , entonces
Prueba : Dado que p es un número primo, los únicos valores posibles de mcd( p k , m ) son 1, p , p 2 , ..., p k , y la única forma de tener mcd( p k , m ) > 1 es si m es un múltiplo de p , es decir, m ∈ { p , 2 p , 3 p , ..., p k − 1 p = p k } , y hay p k − 1 tales múltiplos no mayores que paquete . Por lo tanto, los otros números p k − p k − 1 son todos primos relativos de p k .
Prueba de la fórmula del producto de Euler
El teorema fundamental de la aritmética establece que si n > 1 hay una expresión única donde p 1 < p 2 < ... < p r son números primos y cada k i ≥ 1 . (El caso n = 1 corresponde al producto vacío). Usando repetidamente la propiedad multiplicativa de φ y la fórmula para φ ( p k ) se obtiene
Esto proporciona ambas versiones de la fórmula del producto de Euler.
Una prueba alternativa que no requiere la propiedad multiplicativa utiliza el principio de inclusión-exclusión aplicado al conjunto , excluyendo los conjuntos de números enteros divisibles por los divisores primos.
Ejemplo
En palabras: los distintos factores primos de 20 son 2 y 5; la mitad de los veinte números enteros del 1 al 20 son divisibles por 2, quedando diez; una quinta parte de ellos son divisibles por 5, lo que deja ocho números coprimos con 20; estos son: 1, 3, 7, 9, 11, 13, 17, 19.
La fórmula alternativa utiliza sólo números enteros:
donde x k = mcd( k , n ) para k ∈ {1, ..., n } . Entonces
La parte real de esta fórmula es
Por ejemplo, usando y : A diferencia del producto de Euler y la fórmula de la suma del divisor, ésta no requiere conocer los factores de n . Sin embargo, implica el cálculo del máximo común divisor de n y de cada entero positivo menor que n , lo que de todos modos es suficiente para proporcionar la factorización.
suma divisoria
La propiedad establecida por Gauss, [17] de que
donde la suma es sobre todos los divisores positivos d de n , se puede demostrar de varias maneras. (Consulte Función aritmética para conocer las convenciones de notación).
Una prueba es observar que φ ( d ) también es igual al número de posibles generadores del grupo cíclico C d ; específicamente, si C d = ⟨ g ⟩ con g d = 1 , entonces g k es un generador para cada k coprimo de d . Dado que cada elemento de C n genera un subgrupo cíclico , y cada subgrupo C d ⊆ C n es generado precisamente por φ ( d ) elementos de C n , la fórmula sigue. [18] De manera equivalente, la fórmula se puede derivar mediante el mismo argumento aplicado al grupo multiplicativo de las n -ésimas raíces de la unidad y las primitivas d -ésimas raíces de la unidad .
La fórmula también se puede derivar de la aritmética elemental. [19] Por ejemplo, sea n = 20 y considere las fracciones positivas hasta 1 con denominador 20:
Póngalos en términos más bajos:
Estas veinte fracciones son todas positivas k/d ≤ 1 cuyos denominadores son los divisores d = 1, 2, 4, 5, 10, 20 . Las fracciones con 20 como denominador son aquellas que tienen numeradores relativamente primos con respecto a 20, es decir 1/20 , 3/20 , 7/20 , 9/20 , 11/20 , 13/20 , 17/20 , 19/20 ; por definición, esto es φ (20) fracciones. 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 a 20. Un argumento similar se aplica a cualquier n.
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
Los primeros 100 valores (secuencia A000010 en la 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 un límite superior válido para todos los n distintos de uno, y se alcanza si y sólo si n es un número primo. Un límite inferior simple es , que es bastante vago: de hecho, el límite inferior del gráfico es proporcional a norte/registro registro sustantivo, masculino— . [20]
El criptosistema 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 (privado) ) exponente de descifrado, es el inverso multiplicativo de e módulo φ ( n ) . La dificultad de calcular φ ( n ) sin conocer la factorización de n es, por tanto, la dificultad de calcular d : esto se conoce como el problema RSA que puede resolverse 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 . Sólo 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.
La siguiente propiedad, que forma parte del «folclore» (es decir, aparentemente inédita como resultado específico: [25] véase la introducción de este artículo en la que se afirma que es «conocida desde hace mucho tiempo») tiene consecuencias importantes. Por ejemplo, descarta la distribución uniforme de los valores de en el módulo de progresiones aritméticas para cualquier número entero .
Para cada entero positivo fijo , la relación se cumple para casi todos , es decir, para todos menos los valores de as .
Esta es una consecuencia elemental del hecho de que la suma de los recíprocos de los números primos congruentes con 1 módulo diverge, lo que a su vez es un corolario de la demostración del teorema de Dirichlet sobre progresiones aritméticas .
Ambos se prueban mediante manipulaciones de series elementales y las fórmulas para φ ( n ) .
Tasa de crecimiento
En palabras de Hardy y Wright, el orden de φ ( n ) es "siempre 'casi n '". [28]
Primero [29]
pero como n tiende al infinito, [30] para todo δ > 0
Estas dos fórmulas se pueden probar usando poco más que las fórmulas para φ ( n ) y la función de suma divisoria σ ( n ) .
De hecho, durante la prueba de la segunda fórmula, la desigualdad
cierto para n > 1 , está demostrado.
También tenemos [20]
Aquí γ es la constante de Euler , γ = 0,577215665... , entonces e γ = 1,7810724... y e − γ = 0,56145948 ....
Demostrar esto no requiere del todo el teorema de los números primos . [31] [32] Dado que log log n tiende al infinito, esta fórmula muestra que
De hecho, hay más cosas ciertas. [33] [34] [35]
y
La segunda desigualdad la demostró Jean-Louis Nicolas . Ribenboim dice: "El método de prueba es interesante porque 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". [35] : 173
Para el pedido promedio, tenemos [22] [36]
debido a Arnold Walfisz , su prueba explota 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 (Sobre la función de Euler. Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) mejoró el término de error a
(esta es actualmente la estimación más conocida de este tipo). La " O grande " representa una cantidad que está limitada por una constante multiplicada por la función de n dentro del paréntesis (que es pequeña en comparación con n 2 ).
En 1954 Schinzel y Sierpiński reforzaron esto, demostrando [38] [39] que el conjunto
es denso en los números reales positivos. También demostraron [38] que el conjunto
es denso en el intervalo (0,1).
Números de pacientes
Un número totiente es un valor de la función totiente de Euler: es decir, un m para el cual hay al menos un n para el cual φ ( n ) = m . La valencia o multiplicidad de un número totiente m es el número de soluciones de esta ecuación. [40] Un no paciente es un número natural que no es un número de paciente. Todo número impar superior a 1 es trivialmente un no paciente. También hay infinitos no-tocientes pares, [41] y de hecho cada número entero positivo tiene un múltiplo que es un no-tociente par. [42]
El número de números de pacientes hasta un límite dado x es
para una constante C = 0,8178146... . [43]
Si se cuenta de acuerdo con la multiplicidad, el número de números tocientes hasta un límite dado x es
donde el término de error R es de orden como máximo X/( logx ) k para cualquier k positivo . [44]
Se sabe que la multiplicidad de m excede m δ infinitamente a menudo para cualquier δ < 0,55655 . [45] [46]
teorema de ford
Ford (1999) demostró que para cada 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 conjeturado previamente por Wacław Sierpiński , [47] y se había obtenido como consecuencia de la hipótesis H de Schinzel . [43] De hecho, cada multiplicidad que ocurre, lo hace infinitamente a menudo. [43] [46]
Un número totiente perfecto es un número entero que es igual a la suma de sus totientes iterados. Es decir, aplicamos la función totient a un número n , la aplicamos nuevamente al totient resultante, y así sucesivamente, hasta llegar al número 1, y sumamos la secuencia de números resultante; si la suma es igual a n , entonces n es un número perfecto.
Aplicaciones
ciclotomía
En la última sección de las Disquisitiones [49] [50] Gauss demuestra [51] que se puede construir un n -gón regular con regla y compás si φ ( n ) es una potencia de 2. Si n es una potencia de un número impar número primo la fórmula para el totiente dice que su totiente puede ser una potencia de dos sólo si n es una primera potencia y n − 1 es una potencia de 2. Los primos que son uno más que una potencia de 2 se llaman primos de Fermat , y sólo se conocen cinco: 3, 5, 17, 257 y 65537. Fermat y Gauss los conocían. Nadie ha podido demostrar si hay más.
Por lo tanto, un n -gón regular tiene una construcción de regla y compás si n es un producto de distintos primos de Fermat y cualquier potencia de 2. Los primeros n son [52]
Teorema de los números primos para progresiones aritméticas
El criptosistema RSA
Configurar un sistema RSA implica elegir 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 hacen públicos y d (la "clave de descifrado") se mantiene privado.
Un mensaje, representado por un número entero m , donde 0 < m < n , se cifra calculando S = m e (mod n ) .
Se descifra calculando t = S d (mod n ) . El teorema de Euler se puede utilizar 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
la conjetura de lehmer
Si p es primo, entonces φ ( p ) = p − 1 . En 1932, DH Lehmer preguntó si existen números compuestos n tales que φ ( n ) divida a n − 1 . No se conoce ninguno. [53]
En 1933 demostró que si existe tal n , debe ser impar, sin cuadrados y divisible por al menos siete primos (es decir, ω ( n ) ≥ 7 ). En 1980 Cohen y Hagis demostraron que n > 10 20 y que ω ( n ) ≥ 14 . [54] Además, Hagis demostró que si 3 divide a n, entonces n > 10 1937042 y ω ( n ) ≥ 298848 . [55] [56]
La conjetura de Carmichael
Esto establece que no existe ningún número n con la propiedad de que para todos los demás números m , m ≠ n , φ ( m ) ≠ φ ( n ) . Vea el teorema de Ford arriba.
Como se indica en el artículo principal, si hay un solo contraejemplo para esta conjetura, debe haber infinitos contraejemplos, y el más pequeño tiene al menos diez mil millones de dígitos en base 10. [40]
^ "Función totiente de Euler". Academia Khan . Consultado el 26 de febrero de 2016 .
^ Largo (1972, pág.85)
^ Pettofrezzo y Byrkit (1970, pág.72)
^ Largo (1972, pág.162)
^ Pettofrezzo y Byrkit (1970, pág.80)
^ Ver el teorema de Euler.
^ L. Euler "Theoremata arithmetica nova Methodo demonstrata" (Un teorema aritmético demostrado mediante un nuevo método), Novi commentarii academiae scientiarum imperialis Petropolitanae (Nuevas memorias de la Academia Imperial de Ciencias de San Petersburgo), 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 on-line en: Ferdinand Rudio , ed. , Leonhardi Euleri Commentationes Arithmeticae , volumen 1, en: Leonhardi Euleri Opera Omnia , serie 1, volumen 2 (Leipzig, Alemania, BG Teubner, 1915), páginas 531–555. En la página 531, Euler define n como el número de números enteros menores que N y relativamente primos con N (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi,...), que es el phi función, φ(norte).
^ ab Sandifer, pág. 203
^ Graham y col. pag. 133 nota 111
^ L. Euler, Speculationes circa quasdam insignes proprietates numerorum , Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), págs. 18–30, u Opera Omnia, Serie 1, volumen 4, págs. 105–115. (La obra fue presentada en la Academia de San Petersburgo el 9 de octubre de 1775).
^ Tanto φ ( n ) como ϕ ( n ) se ven en la literatura. Estas son dos formas de la letra griega minúscula phi .
^ Gauss, Disquisitiones Arithmeticae artículo 38
^ Cajori, Florián (1929). Una historia de las notaciones matemáticas Volumen II . Compañía editorial Open Court. §409.
^ JJ Sylvester (1879) "Sobre ciertas ecuaciones de forma cúbica ternaria", American Journal of Mathematics , 2 : 357-393; Sylvester acuña el término "totiente" en la página 361.
^ Lomadse, G. (1964), "El trabajo científico de Arnold Walfisz" (PDF) , Acta Arithmetica , 10 (3): 227–237, doi :10.4064/aa-10-3-227-237
^ ab Sitaramachandrarao, R. (1985). "Sobre un término de error de Landau II". Montañas Rocosas J. Matemáticas . 15 (2): 579–588. doi : 10.1216/RMJ-1985-15-2-579 .
^ Pollack, P. (2023), "Dos problemas sobre la distribución de la función lambda de Carmichael", Mathematika , 69 : 1195–1220, arXiv : 2303.14043 , doi : 10.1112/mtk.12222
^ Hardy y Wright 1979, thm. 288
^ Hardy y Wright 1979, thm. 309
^ Hardy y Wright 1979, introducción al § 18.4
^ Hardy y Wright 1979, thm. 326
^ Hardy y Wright 1979, thm. 327
^ De hecho, todo lo que se necesita es el teorema de Chebyshev (Hardy y Wright 1979, thm.7) y el tercer teorema de Mertens.
^ Hardy y Wright 1979, thm. 436
^ Teorema 15 de Rosser, J. Barkley; Schoenfeld, Lowell (1962). "Fórmulas aproximadas para algunas funciones de números primos". Illinois J. Matemáticas . 6 (1): 64–94. doi : 10.1215/ijm/1255631807 .
^ Bach y Shallit, thm. 8.8.7
^ ab Ribenboim (1989). "¿Cómo se distribuyen los números primos? §IC La distribución de valores de la función de Euler". El libro de registros de números primos (2ª ed.). Nueva York: Springer-Verlag. págs. 172-175. doi :10.1007/978-1-4684-0507-1_5. ISBN978-1-4684-0509-5.
^ Sándor, Mitrinović y Crstici (2006) págs. 24-25
^ Hardy y Wright 1979, thm. 332
^ abc Ribenboim, p.38
^ ab Sándor, Mitrinović y Crstici (2006) p.16
^ ab Guy (2004) p.144
^ Sándor y Crstici (2004) p.230
^ Zhang, Mingzhi (1993). "Sobre los no pacientes". Revista de teoría de números . 43 (2): 168-172. doi : 10.1006/junio.1993.1014 . ISSN 0022-314X. Zbl 0772.11001.
^ abc Ford, Kevin (1998). "La distribución de los pacientes". Ramanujan J. Desarrollos en Matemáticas. 2 (1–2): 67–151. arXiv : 1104.3264 . doi :10.1007/978-1-4757-4507-8_8. ISBN978-1-4419-5058-1. ISSN 1382-4090. Zbl 0914.11053.
^ Sándor et al (2006) p.22
^ Sándor et al (2006) p.21
^ ab Guy (2004) p.145
^ Sándor y Crstici (2004) p.229
^ Sándor y Crstici (2004) p.228
^ Gauss, DA. El § 7º son los arts. 336–366
^ Gauss demostró que si n satisface ciertas condiciones, entonces se puede construir el n -gon. En 1837, Pierre Wantzel demostró lo contrario: si el n -gon es construible, entonces n debe satisfacer las condiciones de Gauss.
^ Gauss, DA, artículo 366
^ Gauss, DA, arte. 366. Esta lista es la última frase de las Disquisiciones
^ Ribenboim, págs. 36-37.
^ Cohen, Graeme L.; Hagis, Peter Jr. (1980). "Sobre el número de factores primos de n si φ ( n ) divide n − 1 ". Nuevo Arco. Wiskd . III Serie. 28 : 177–185. ISSN 0028-9825. Zbl 0436.10002.
^ Hagis, Peter Jr. (1988). "Sobre la ecuación M ·φ( n ) = n − 1 ". Nuevo Arco. Wiskd . Serie IV. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
^ Chico (2004) p.142
^ Broughan, Kevin (2017). Equivalentes de la hipótesis de Riemann, volumen uno: equivalentes aritméticos (Primera ed.). Prensa de la Universidad de Cambridge. ISBN978-1-107-19704-6.Corolario 5.35
Referencias
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 .
Bach, Eric ; Shallit, Jeffrey (1996), Teoría algorítmica de números (Vol I: Algoritmos eficientes) , Serie de MIT Press sobre los fundamentos de la informática, Cambridge, MA: The MIT Press , ISBN 0-262-02405-5, Zbl 0873.11070
Dickson, Leonard Eugene, "Historia de la teoría de los números", vol 1, capítulo 5 "Función de Euler, generalizaciones; serie Farey", Chelsea Publishing 1952
Ford, Kevin (1999), "El número de soluciones de φ( x ) = m ", Annals of Mathematics , 150 (1): 283–311, doi :10.2307/121103, ISSN 0003-486X, JSTOR 121103, MR 1715326 , Zbl 0978.11053.
Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (Segunda edición) , traducido por Maser, H., Nueva York: Chelsea, ISBN 0-8284-0191-8
Guy, Richard K. (2004), Problemas no resueltos en teoría de números , Libros de problemas en matemáticas (3.ª ed.), Nueva York, NY: Springer-Verlag , ISBN 0-387-20860-7, Zbl 1058.11001
Sandifer, Charles (2007), Las primeras matemáticas de Leonhard Euler , MAA, ISBN 978-0-88385-559-1
Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006), Manual de teoría de números I , Dordrecht: Springer-Verlag , págs. 9–36, ISBN 1-4020-4215-9, Zbl 1151.11300
Sándor, Jozsef; Crstici, Borislav (2004). Manual de teoría de números II . Dordrecht: Académico Kluwer. págs. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001.
Schramm, Wolfgang (2008), "La transformada de Fourier de funciones del máximo común divisor", Electronic Journal of Combinatorial Number Theory , A50 (8(1)).