Angel "Java" Lopez en Blog

Publicado el 1 de Julio, 2010, 2:09

En el anterior post

La función indicatriz de Euler, primeros pasos

estuvimos revisando la función indicatriz de Euler:

 

Recordemos: es la cantidad de números naturales 1 <= a <= n, tales que (a , n) = 1, su máximo común divisor. Es decir, los primos con n.

Quisiera hoy visitar afirmaciones de ese post, que quedaron pendientes de demostración ¿Cómo podemos calcular φ(n) para cualquier n? Vayamos por partes. Primero, es fácil ver que:

 

cuando p es primo > 1. Es evidente.

Dividí luego la cuestión en dos caminos.

Primero si n = mp, con p primo, p no divide a m entonces

Veamos primero este caso. Pongamos un caso concreto, n = 6 = 3*2. Sea p=2.

Recordemos los primos con 3:

Los primos con 3 los marcábamos en rojo.

Ahora, pasemos a 6 = 3*2, y supongamos que este tramo que se agrega tiene el mismo "patrón" de dos en rojo, uno en azul:

Pero nos equivocaríamos: hay dos números que siguen siendo primos con 3, pero con el nuevo n=6. Los marqué en verde:

El resultado final, que vimos ayer para n=6, es:

Ahora que vimos un caso concreto, vemos que hay que quitar dos elementos:

2 = 1*2

4 = 2*2

¿Cuáles son esos elementos? Son los φ(m) elementos que era primos con m=3, pero ahora multiplicados por el nuevo p=2. Son de la forma

Donde los mi son los φ(m) elementos primos con m. Todos esos ai son primos con m, por ser p primo con m, y cada mi . Entonces, todos "caen" en los φ(m)* p  elementos que supusimos que son primos con m, y supusimos que eran primos con n. Esto nos da que los realmente primos con n son:


como queríamos demostrar.

Veamos el caso n=mp, p primo divide a m. Un caso concreto, n=9=3*3.

Partimos nuevamente de 3:

Lo repetimos 3 veces, e ingenuamente, repetimos también el patrón: dos rojos, uno azul:

Esta vez no nos equivocamos: no aparecen nuevos números que sean primos con 9. De alguna forma, los del tipo:

Ya no son primos con n, porque p divide a m, y por lo tanto, p es divisor común de n y de los candidatos ai. Queda entonces:

Tomando estos resultados, se puede ir calculando todos los valores de la función indicatriz. Por ejemplo, para cuando n es potencia de p primo, haciendo algunos cálculos, nos queda

Para cualquier n, será



Esta última expresión da para resultados interesantes. Pero eso ya daría para otro post.

Basado en este resultado, mientras tanto, tratar de probar


Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez