Función totient de Euler
En la teoría de números , la función totient de Euler cuenta los números enteros positivos hasta un número entero dado n que son primos relativos a n . Se escribe usando la letra griega phi como o , y también puede llamarse 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 se denominan 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 a 9, pero los otros tres números en este rango, 3, 6 y 9 no son , ya que mcd(9, 3) = mcd(9, 6) = 3 y mcd(9, 9) = 9 . Por lo tanto, φ (9) = 6 . Como otro ejemplo, φ (1) = 1 ya que para n = 1 el único número entero en el rango de 1 a n es el mismo 1, y mcd(1, 1) = 1 .
La función totient de Euler es una función multiplicativa , lo que significa que si dos números m y n son primos relativos, entonces φ ( mn ) = φ ( m ) φ ( n ) . [4] [5] Esta función da el orden del grupo multiplicativo de enteros módulo n (el grupo de unidades del anillo ). [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ó más la función, 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". [10] Esta definición varía de la definición actual de 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 de Gauss de 1801Disquisitiones Arithmeticae , [12] [13] 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, JJ Sylvester acuñó el término totient para esta función, [14] [15] por lo que también se conoce como la función totient de Euler , el totient de Euler o el totient de Euler . El totient de Jordan es una generalización del de Euler.
El cociente de n se define como n − φ ( n ) . Cuenta el número de enteros positivos menores o iguales a n que tienen al menos un factor primo en común con n .
