Angel "Java" Lopez en Blog

Publicado el 8 de Julio, 2010, 14:40

Hace un tiempo escribía:

La función indicatriz de Euler

sobre la función

que era 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. Luego, en otro post, deducía una fórmula para calcularla:

Calculando la función indicatriz de Euler

La fórmula que habíamos conseguido es:

que los p recorreren los primos que dividen a n. Curiosamente, aparecen fracciones, aunque el resultado es entero. Es fácil ver por qué: los p dividen a n. También notamos que no depende tanto de la potencia de cada p: cada primo aparece una vez sola en la multiplicación. De alguna forma, cada p que aparece, "retira" 1/p números de los que van quedando. Veamos gráficamente.

Veamos de calcular la función para n=12. Sean los números iniciales:

Luego, el primer divisor es 2. Marcamos/tachamos los divisibles por 2 (algo parecido al algoritmo de la "criba de Eratóstenes") los marcamos en azul

Y ahora, quitamos los siguientes, tachamos los rojos que quedaron que sean divisibles por 3 (marcados en verde):

Notamos que YA hay números divisibles por 3 YA tachados por haber sacado los pares. Pero igual, de los que quedan, justamente retiramos 1/3. Y los que quedaban por marcar, eran un número divisible por 3.

Tenemos que estudiar todas las propiedades de esta función, ver funciones parecidas, definir funciones aritméticas, definir multiplicación apropiada de estas funciones (usando convolución de Dirichlet), y al fin, llegar a ver dónde se usan en teoría de números. Ya vimos, en el post

Congruencias módulo m

un uso de la indicatriz para lo que se llama el teorema de Euler-Fermat:

Nos leemos!

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