Función Phi de Euler

Descargar como Notebook

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