Entrada destacada

Juego del Caos cambiando el dado al orden del Genoma

martes, 27 de junio de 2017

Función Phi de Euler


Antes de definirla recordemos que dos números enteros positivos se dicen coprimos o primos relativos entre sí, si el máximo común divisor entre ambos es 1. En Mathematica se tiene el comando GCD[ ] para el máximo común divisor y CoprimeQ[ ] para decidir si son (True) o no (False) primos relativos.

GCD[4, 6]
2

CoprimeQ[4, 6]
False

GCD[4, 9]
1

CoprimeQ[4, 9]
True

Ahora, dado un entero positivo n, la función Φ(n) nos da el número de enteros positivos menores o iguales a n que son primos relativos con él. Calculemos Φ(12): de la lista de los enteros de 1 a 12, vamos a seleccionar los que son coprimos con 12 y los contamos.

Range[12]
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

Select[Range[12], CoprimeQ[12, #] &]
{1, 5, 7, 11}

Length[%]
4

Así,  Φ(12) = 4.

Propiedades

1. Es claro que: Φ(1)=1

2. Para un número primo p se tiene que: Φ(p)=p-1

3. Para un número primo p y un número entero positivo k, se tiene que: Φ(p^k)=(p-1)p^(k-1)

4. Para n,m números enteros positivos: Φ(n m)=Φ(n) Φ(m).

Ahora, el Teorema Fundamental de la Aritmética nos dice:

Si n es un entero positivo mayor o igual a 2, entonces existen números primos p y  números enteros positivos α tales que se puede expresar de forma única, salvo el orden del producto, n como:


Por tanto, de las propiedades de la Función Phi de Euler y el Teorema Fundamental de la Aritmética tenemos el Producto de Euler:

Si la factorización de n como producto de primos es como él resultado anterior, entonces



En Mathematica

Diferentes formas de calcular la función Phi de Euler:

Forma 1

Como realizamos el calculo en el ejemplo, de forma funcional

phi[n_] := Length@Select[Range[n], CoprimeQ[n, #] &]

phi[12]
4

Forma 2

De forma procedimental

euler[n_] := 
 Module[{ee = {}}, Do[If[CoprimeQ[k, n], AppendTo[ee, k]], {k, n}]; 
  Length[ee]]

euler[12]
4

Forma 3

Utilizando el producto de Euler, sabemos que el Teorema Fundamental de la Aritmética lo representa la función FactorInteger[ ], que nos muestra una lista de parejas donde el primer número es el factor primo y el segundo su correspondiente exponente:

FactorInteger[20!]
{{2, 18},{3, 8},{5, 4},{7, 2},{11, 1},{13, 1},{17, 1},{19, 1}}

Escribiéndolo en forma multiplicativa:

CenterDot @@ (Superscript @@@ %)



Por tanto,






phieuler[12]
4

Forma 4

De última la más sencilla, Mathematica tiene incorporada la función EulerPhi[ ] :

EulerPhi[12]
4

En entradas futuras haremos referencia y uso de esta función.


Para aprender más sobre Mathematica ingrese aquí sitio de aprendizaje de Wolfram o en mi website ustamathematica.wixsite.com/basicas


No hay comentarios.:

Publicar un comentario