Implementación de algoritmos de teoría de números/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 natural, 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:

$\varphi (m)=|\{n\in \mathbb {N} |n\leq m\land \mathrm {mcd} (m,n)=1\}|$

donde |·| significa la cantidad de números que cumplen la condición.

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

$n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$

donde los p_j son números primos distintos, entonces

$\varphi (n)=(p_{1}-1)p_{1}^{k_{1}-1}\cdots (p_{r}-1)p_{r}^{k_{r}-1}.$

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

$\varphi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)$

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

Descripción formal

Versión iterativa

De la definición general,

$\varphi (n):=\sum _{{1\leq k\leq n} \atop {\operatorname {mcd} (k,n)=1}}1$

y tomando por convenio que φ(0)=1, se obtiene la versión iterativa.

función $\varphi (n)\,$
  devolver $1$ si $n=0\,$
  $j\leftarrow 0$
  para $k\in 1..n$ hacer
     $j\leftarrow j+1$ si $\operatorname {mcd} (n,k)=1$   
  devolver $j$

Esta versión tiene fácil implementación en una computadora, pero no es eficiente para valores grandes de n.

Versión por factorización

Se basa en la definición de la función mediante el producto de Euler

$\varphi (n):=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)$

y utiliza algún algoritmo de factorización eficiente de propósito general como puede ser la criba general del cuerpo de números (GNFS).

Implementación en distintos lenguajes de programación

Matlab/Octave

En Matlab/Octave el algoritmo queda como sigue. Esta función gráfica los primeros m valores de la función (solo depende del número m).

function [] = phi(m),
con=0;
l=zeros(m,1);

for i=1:1:m,

	for j=1:1:i,
		if(gcd(i,j) == 1)
			con++;
		endif
	endfor

	l(i)=con;
	con=0;
endfor

plot(1:m,l,'.');

endfunction

Referencias

• Octavian Cira, Florentin Smarandache, Solving Diophantine Equations, Infinite Study, ISBN 1599733072, pp:64-68