La herencia de Euclides (5) La función indicatriz de Euler

Esta es la última entrada del curso 2011-12. Felices vacaciones para quienes las tengan. A los amigos del hemisferio Sur les deseamos paciencia. En Septiembre volvemos.

Terminamos esta serie sobre las aplicaciones encadenadas del algoritmo extendido de Euclides con la presentación de la función j(n) (indicatriz o indicador de Euler) como el cardinal del conjunto de elementos inversibles en Z_n

Sólo nos interesará por ahora este aspecto de la función j(n)

Todas las propiedades de j(n) las tienes en multitud de libros y páginas web. Entre ellas puedes consultar

http://gaussianos.com/la-funcion-phi-de-euler-otra-genialidad-del-maestro/
http://hojamat.es/sindecimales/divisibilidad/teoria/teordivi.pdf
http://hojamat.es/parra/funesp.pdf
http://mathworld.wolfram.com/TotientFunction.html

Aquí sólo destacaremos que j(n) es el cardinal del grupo de inversibles Z*_n, (ver nuestra anterior entrada) es decir, el conjunto de números menores que n y primos con él, contando el 1. Esta definición nos desemboca inmediatamente en su carácter multiplicativo.

En efecto, en la entrada anterior explicábamos que el Teorema Chino de los Restos  nos garantizaba que existía un isomorfismo entre el anillo Z_m×Z_n y el anillo Z_mn cuando m y n son coprimos. También vimos que este isomorfismo se podía restringir a los grupos de inversibles, es decir, que el grupo Z*_m×Z*_n es isomorfo a Z*_mn.

Pues ya lo puedes tener claro…el cardinal del primero es j(m). j(n) y el cardinal del segundo j(m.n), luego…

¡Ya hemos llegado a donde queríamos después de más de un mes!

La función indicatriz de Euler es multiplicativa, porque si m y n son coprimos, se cumple que


j(m). j(n) = j(m.n)

No estaría mal que buscaras otra demostración de esta importante propiedad.

En la hoja euclides.xlsm  o en la euclides.ods (http://hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm),
en el apartado del isomorfismo, puedes comprobar esta propiedad en casos concretos.

Es curioso que sea multiplicativa una función que cuenta “huecos” (los que no tienen factores comunes con n), que proceden de un cribado, pero si los cuentas como los elementos inversibles de un anillo, los que sobran son los otros, los divisores de cero.

Si has leído las páginas recomendadas o si nos sigues con atención no tendrás problemas en entender que

Si p es primo, j(p)=p-1

¡Pues claro! ¿Qué número va a tener divisores con p, salvo él mismo?

Si n=p^k con p primo(es decir, es un número primario), j(n)=p^k(1-1/p)

Aquí nos detenemos algo más: Los números menores que p^k que tienen divisores comunes con él sólo pueden ser p, p², p³,…p^k, es decir, son en total p^k-1 números, luego

j(n)=p^k - p^k-1 = p^k(1-1/p)

¿Y si n no es primo ni primario?

En ese caso viene en nuestra ayuda la propiedad multiplicativa:

Si N=p^aq^br^cs^d, siendo p,q,r,s divisores primos de N, entonces se tendrá j(N)=N(1-1/p) (1-1/q) (1-1/r) (1-1/s)

Lo ponemos en limpio:

Implementación de la función en hoja de cálculo

Podemos definir la función de dos formas, por su definición o mediante la fórmula anterior. En el primer caso nos resultará un código sencillo y fácil de entender, pero que se vuelve insoportablemente largo para números grandes. Sería este:

Mediante su definición


Definimos en primer lugar el MCD mediante el algoritmo de Euclides

Public Function mcd(a1, b1)
Dim a, b, r


r = 1
a = a1
b = b1
If b = 0 Then b = 1
If a = 0 Then a = 1
While r <> 0
r = a - b * Int(a / b)
If r <> 0 Then a = b: b = r
Wend
mcd = b
End Function

Después vamos contando los números menores que N coprimos con él

Public Function euler(a)
Dim  n, eu, s


If a = 0 Then a = 1
n = 1: s = 0
If a = 1 Then
s = 0
Else
While n < a
If mcd(a, n) = 1 Then s = s + 1
n = n + 1
Wend
End If
euler = s
End Function

Esta función no va mal para números pequeños, pero es más rápida en general esta otra:

Public Function euler(n)
Dim f, a, e
Dim recoge As Boolean


a = n ‘se copia porque se va a alterar su valor en el algoritmo
f = 3 ‘variable de búsqueda de factores primos
e = n ‘valor inicial de la indicatriz
If n / 2 = Int(n / 2) Then e = e / 2 ‘si es par, la indicatriz se divide entre 2
While f <= a ‘se van buscando los factores primos
If esprimo(f) Then
recoge = True
While esmultiplo(a, f)
a = a / f ‘se divide para ahorrar tiempo (algoritmo voraz)
If recoge Then e = e * (f - 1) / f: recoge = False ’sólo se recoge el factor una vez
Wend
End If
f = f + 2 ‘recorre los impares
Wend
euler = e
End Function

El código está basado en la fórmula que hemos obtenido: por cada factor primo p se multiplica por p-1 y se divide entre p.

Hemos efectuado pruebas, y para números del orden de 10⁵ el tiempo de cálculo se reduce en más de una quinta parte respecto a la primera versión de la función. Así que adoptaremos esta.

También la tenemos implementada en el Buscador de Naturales con el nombre de EULER(N), pero por ahora en la versión lenta.

Te proponemos una búsqueda: Elige un número cualquiera y busca todos sus divisores con el Buscador (http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm) y evalúa j(N) en cada uno de ellos. Observa la suma: ¿qué obtienes?

Hemos buscado los divisores de 1228, le hemos sumado los valores de la indicatriz y hemos obtenido como suma en el Evaluador otra vez el número 1228

La explicación, si tenemos ánimos, se queda para el curso que viene.