Publicado el 1 de Julio, 2010, 2:09
|
En el anterior post La función indicatriz de Euler, primeros pasos
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: 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: 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 |
