Función φ de Euler

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,para todo a coprimo con n. La función φ juega también un papel clave en la definición del sistema de cifrado RSA.[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".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.Cuenta el número de enteros positivos menores o iguales aLuego, por el Teorema Chino del Resto existe una biyección entreEl totiente es la transformada de Fourier discreta del mcd, evaluado en 1.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 Cd ⊆ Cn son generados precisamente por elementos φ(d) de Cn, la fórmula es la siguiente.[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.Un ejemplo: Los 99 primeros valores de la función vienen escritos en la siguiente tabla, así como gráficamente.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.En esta sección, φ(n) es la función totiente y ϕ = 1 + √5/2 = 1.618... es la proporción áurea.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.[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.Todo entero impar que exceda de 1 es trivialmente un número no totiente.[44]​[45]​ 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.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.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.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.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. Si p es primo, entonces φ(p) = p − 1.[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).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.Las referencias a las Disquisitiones son de la forma Gauss, DA, art.