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 Zn
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 Zm×Zn y el anillo Zmn 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=pk con p primo(es decir, es un número primario), j(n)=pk(1-1/p)
Aquí nos detenemos algo más: Los números menores que pk que tienen divisores comunes con él sólo pueden ser p, p2, p3,…pk, es decir, son en total pk-1 números, luego
j(n)=pk - pk-1 = pk(1-1/p)
¿Y si n no es primo ni primario?
En ese caso viene en nuestra ayuda la propiedad multiplicativa:
Si N=paqbrcsd, 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 105 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.