fbpx
Wikipedia

Función φ de Euler

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

Los primeros mil valores de .

donde |·| significa la cardinalidad del conjunto descrito.

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.

Primeras propiedades y cálculo de la función

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

  1.   si   es primo.
  2.   si p es primo y k es un número natural.
  3.   es una función multiplicativa: si m y n son primos entre sí, entonces  .

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

Para la segunda propiedad debemos observar que si   es primo solo sus múltiplos ( ) menores que   presentan un máximo 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 1 y   solo tiene de divisor en común con   a la unidad. Esto es,  . Nótese que esta segunda propiedad se cumple porque   es primo. En efecto, si hubiera un   distinto de 1 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, sabemos que:

 

con pi primo, por tanto:

 .

Como  , entonces ninguno de los primos   y   son iguales y la descomposición en primos de   no se ve alterada, es decir, si   y   entonces la descomposición en primos será  , lo cual implica que

 

por lo tanto,   si   y   son primos relativos.

Con esto, el valor de φ(n) puede calcularse empleando el teorema fundamental de la Aritmética: si

 

donde los pj son números primos distintos, entonces

 

Esta última fórmula es un producto de Euler y a menudo se escribe como

 

donde los p son los distintos primos que dividen a n.

Ejemplo de cálculo

 

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.

Algunos valores

 
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

Propiedades

  • φ(n) también es igual al número de generadores del grupo cíclico Cn (y por ello también es igual al grado del polinomio ciclotómico Φn). Como cada elemento de Cn genera un subgrupo cíclico y los subgrupos de Cn son de la forma Cd donde d divide a n (notación: d|n), se tiene que
 

     donde la suma es de todos los divisores positivos d de n.

     De esta manera, se puede emplear la fórmula de inversión de Möbius para «invertir» esta suma y obtener otra fórmula para φ(n):

 

     donde μ es la usual función de Möbius definida sobre los enteros positivos.

 

Véase también

Referencias

Enlaces externos

  •   Datos: Q190026
  •   Multimedia: Totient function

función, euler, función, euler, también, llamada, función, indicatriz, euler, función, importante, teoría, números, número, entero, positivo, entonces, define, como, número, enteros, positivos, menores, iguales, coprimos, decir, formalmente, puede, definir, co. La funcion f de Euler tambien llamada funcion indicatriz de Euler es una funcion importante en teoria de numeros Si n es un numero entero positivo entonces f n se define como el numero de enteros positivos menores o iguales a n y coprimos con n es decir formalmente se puede definir como Los primeros mil valores de f n displaystyle scriptstyle varphi n f n m N m n m c d m n 1 displaystyle varphi n m in mathbb N m leq n land mathrm mcd m n 1 donde significa la cardinalidad del conjunto descrito La funcion f es importante principalmente porque proporciona el tamano del grupo multiplicativo de enteros modulo n Mas precisamente f n displaystyle varphi n es el orden del grupo de unidades del anillo Z n Z displaystyle mathbb Z n mathbb Z En efecto junto con el teorema de Lagrange de los posibles tamanos de subgrupos de un grupo proporciona una demostracion del teorema de Euler que dice que a f n 1 mod n displaystyle a varphi n equiv 1 pmod n para todo a coprimo con n La funcion f juega tambien un papel clave en la definicion del sistema de cifrado RSA Indice 1 Primeras propiedades y calculo de la funcion 1 1 Ejemplo de calculo 2 Algunos valores 3 Propiedades 4 Vease tambien 5 Referencias 6 Enlaces externosPrimeras propiedades y calculo de la funcion EditarSe sigue de la definicion que f 1 1 displaystyle varphi 1 1 pues el elemento 1 solo puede ser coprimo consigo mismo Para otros numeros se cumple que f p p 1 displaystyle varphi p p 1 si p displaystyle p es primo f p k p 1 p k 1 displaystyle varphi p k p 1 p k 1 si p es primo y k es un numero natural f displaystyle varphi es una funcion multiplicativa si m y n son primos entre si entonces f m n f m f n displaystyle varphi mn varphi m varphi n La primera propiedad se demuestra facilmente porque un numero primo es coprimo con todos sus anteriores Y por tanto existen p 1 elementos coprimos con p En otras palabras como p es primo solo tendra de divisores a si mismo y a la unidad la cual esta presente en los p 1 numeros anteriores a p Para la segunda propiedad debemos observar que si p displaystyle p es primo solo sus multiplos n p displaystyle np menores que p k displaystyle p k presentan un maximo comun divisor con p k displaystyle p k distinto de uno Esto es 1 p 2 p 3 p p k 1 p displaystyle 1p 2p 3p p k 1 p son los unicos numeros m displaystyle m tales que mcd p k m 1 displaystyle operatorname mcd p k m neq 1 Como en total hay p k 1 displaystyle p k 1 numeros que satisfacen esta propiedad el resto de numeros entre 1 y p k displaystyle p k solo tiene de divisor en comun con p k displaystyle p k a la unidad Esto es f p k p k p k 1 p 1 p k 1 displaystyle varphi p k p k p k 1 p 1 p k 1 Notese que esta segunda propiedad se cumple porque p displaystyle p es primo En efecto si hubiera un m n p displaystyle m neq np distinto de 1 tal que mcd p k m a 1 displaystyle operatorname mcd p k m a neq 1 entonces a displaystyle a seria divisor de p k p p p displaystyle p k p cdot p p k displaystyle k veces es decir a displaystyle a seria una potencia y por consiguiente multiplo de p displaystyle p contradiciendo la suposicion inicial m n p displaystyle m neq np Para demostrar la tercera propiedad sabemos que f n n p i n 1 1 p i displaystyle varphi n n prod p i n left 1 frac 1 p i right con pi primo por tanto f n f m m n p i n 1 1 p i q i m 1 1 q i displaystyle varphi n varphi m mn prod p i n left 1 frac 1 p i right prod q i m left 1 frac 1 q i right Como mcd m n 1 displaystyle operatorname mcd m n 1 entonces ninguno de los primos p i displaystyle p i y q i displaystyle q i son iguales y la descomposicion en primos de m n displaystyle mn no se ve alterada es decir si m q 1 b 1 q 2 b 2 q k b 1 displaystyle m q 1 beta 1 q 2 beta 2 q k beta 1 y n p 1 a 1 p 2 a 2 p j a j displaystyle n p 1 alpha 1 p 2 alpha 2 p j alpha j entonces la descomposicion en primos sera m n q 1 b 1 q 2 b 2 q k b 1 p 1 a 1 p 2 a 2 p j a j displaystyle mn q 1 beta 1 q 2 beta 2 q k beta 1 p 1 alpha 1 p 2 alpha 2 p j alpha j lo cual implica que f m n m n p i n 1 1 p i q i m 1 1 q i displaystyle varphi mn mn prod p i n left 1 frac 1 p i right prod q i m left 1 frac 1 q i right por lo tanto f m n f m f n displaystyle varphi mn varphi m varphi n si m displaystyle m y n displaystyle n son primos relativos Con esto el valor de f n puede calcularse empleando el teorema fundamental de la Aritmetica si n p 1 k 1 p r k r displaystyle n p 1 k 1 cdots p r k r donde los pj son numeros primos distintos entonces f n p 1 1 p 1 k 1 1 p r 1 p r k r 1 displaystyle varphi n p 1 1 p 1 k 1 1 cdots p r 1 p r k r 1 Esta ultima formula es un producto de Euler y a menudo se escribe como f n n p n 1 1 p displaystyle varphi n n prod p n left 1 frac 1 p right donde los p son los distintos primos que dividen a n Ejemplo de calculo Editar f 36 f 3 2 2 2 36 1 1 3 1 1 2 36 2 3 1 2 12 displaystyle varphi 36 varphi left 3 2 2 2 right 36 left 1 frac 1 3 right left 1 frac 1 2 right 36 cdot frac 2 3 cdot frac 1 2 12 Tambien f 36 f 3 2 2 2 3 1 3 2 1 2 1 2 2 1 2 3 1 2 12 displaystyle varphi 36 varphi left 3 2 2 2 right 3 1 3 2 1 2 1 2 2 1 2 cdot 3 cdot 1 cdot 2 12 Se puede comprobar manualmente que los numeros 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 Algunos valores Editar Representacion grafica de los 100 primeros valores Notese que el limite inferior marcado por la recta y 4n 15 no es el limite inferior de la funcion de manera global sino para multiplos de 30 Los 99 primeros valores de la funcion vienen escritos en la siguiente tabla asi como graficamente f n displaystyle varphi n 0 1 2 3 4 5 6 7 8 90 1 1 2 2 4 2 6 4 610 4 10 4 12 6 8 8 16 6 1820 8 12 10 22 8 20 12 18 12 2830 8 30 16 20 16 24 12 36 18 2440 16 40 12 42 20 24 22 46 16 4250 20 32 24 52 18 40 24 36 28 5860 16 60 30 36 32 48 20 66 32 4470 24 70 24 72 36 40 36 60 24 7880 32 54 40 82 24 64 42 56 40 8890 24 72 44 60 46 72 32 96 42 60Propiedades EditarEl valor de f n es igual al orden del grupo de las unidades del anillo Z nZ vease aritmetica modular Esto junto con el teorema de Lagrange proporciona una demostracion del teorema de Euler f n tambien es igual al numero de generadores del grupo ciclico Cn y por ello tambien es igual al grado del polinomio ciclotomico Fn Como cada elemento de Cn genera un subgrupo ciclico y los subgrupos de Cn son de la forma Cd donde d divide a n notacion d n se tiene que d n f d n displaystyle sum d mid n varphi d n donde la suma es de todos los divisores positivos d de n De esta manera se puede emplear la formula de inversion de Mobius para invertir esta suma y obtener otra formula para f n f n d n d m n d displaystyle varphi n sum d mid n d mu n d donde m es la usual funcion de Mobius definida sobre los enteros positivos La siguiente formula es de una serie de Dirichlet que genera un grupo ciclico f n n 1 f n n s z s 1 z s displaystyle sum n 1 infty frac varphi n n s frac zeta s 1 zeta s Vease tambien EditarTeorema de Euler Funcion de Carmichael Funcion indicatriz de Jordan Funcion suma indicatrizReferencias EditarEnlaces externos EditarWeisstein Eric W Euler s Totient Function En Weisstein Eric W ed MathWorld en ingles Wolfram Research EulerPhifunction en PlanetMath Wikilibros alberga un libro o manual sobre Implementaciones de la funcion f de Euler Datos Q190026 Multimedia Totient functionObtenido de https es wikipedia org w index php title Funcion f de Euler amp oldid 133273649, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos