Estudiar sin beca

https://youtu.be/z0Katkl-nTY

Vigilados

sábado, 9 de febrero de 2013

La función phi de Euler es multiplicativa

ESTA ENTRADA ESTÁ EN CONSTRUCCIÓN A LA ESPERA DE ENCONTRAR MÁS INFORMACIÓN. SI ALGÚN LECTOR CONOCE ENLACES O REFERENCIAS BIBLIOGRÁFICAS, ME LAS PUEDE DEJAR EN LOS COMENTARIOS.
En principio pensaba hacer un informe sobre la función $\phi$ de Euler, pero conforme he ido recopilando información, he decidido, en un primer momento al menos, concentrarme en la propiedad multiplicativa de dicha función.
Lo primero que he hecho, es recabar información en Internet. Hay bastante información, pero la mayor parte está en documentos pdf que tratan en general de teoría de números, y hay que buscar el apartado o sección  que se ocupe de la función $\phi $ o función indicatriz de Euler

Otros documentos más específicos sobre la función indicatriz no traen demostraciones.
Como no estoy satisfecho con la información que he encontrado en la red, me planteo elaborar una especie de informe con  los contenidos que me parece debe poseer una introducción a la función $ \phi $
El contenido, a mi parecer, debe ser el siguiente:

Definición.
Propiedades más sencillas
Propiedad clave: la función $\phi$ es multiplicativa.
Fórmula para hallar la función $\phi$ a partir de la descomposición en factores primos.
Otras propiedades y aplicaciones de la función indicatriz de Euler
Bibliografía y enlaces a documentos utilizados.(DE MOMENTO NO LA INCLUYO, LA PONDRÉ MÁS ADELANTE)

Sin embargo, me parece interesante que, como motivación se puede poner al principio el teorema de Fermat y su generalización por Euler, en el que aparece por primera vez en teoría de números la función indicatriz.

Me daré a mí mismo un plazo de semanas ( o meses) para completar el esquema, mientras también espero nueva información que me puedan aportar lo lectores.(Además, en breve entraré en un período en el que previsiblemente apenas tendré tiempo para escribir en este blog)

Ahora comentaré lo que he encontrado en la red.
Una buena introducción está en el blog gaussianos en este enlace
Está muy bien, pero no contiene demostraciones
 Reflexionando sobre el tema, creo que como mínimo hay que incluir la demostración de la propiedad clave, que la función indicatriz es multiplicativa.Todo lo demás es sencillo excepto esta propiedad crucial  $ \phi (a\cdot{ b}) = \phi (a)  \cdot { \phi (b) } $ (siempre que sean primos entre sí $(a,b)=1$ )
He visto varias demostraciones de este hecho, que son esencialmente dos (aunque con múltiples variantes)
A ver si las reproduzco.
Una de ellas es la que usa explícitamente el teorema chino del resto, mientras que la otra lo elude (aunque hace un razonamiento similar.)
De todas maneras, aquí va una de ellas, que depende explícitamente del teorema chino del resto:
http://planetmath.org/ProofThatEulerPhiIsAMultiplicativeFunction.html  (Enunciado y prueba)

Como se basa en el teorema chino del resto, aquí va el enunciado http://planetmath.org/encyclopedia/Cne hineseRemainderTheorem.html  (Enunciado)
y aquí una demostración  http://planetmath.org/ChineseRemainderTheoremProof.html (La prueba).

Voy a exponer la versión de la demostración de la propiedad multiplicativa que NO usa explícitamente el teorema chino del resto

COMIENZA LA DEMOSTRACIÓN

La función $ \phi $ es la que hace corresponder a cada entero positivo el número de enteros positivos menores que el número de partida y primos con él.
Una función de teoría de números se dice multiplicativa si cumple que para cada par de números enteros positivos primos entre sí $a$ y $b$ entonces  $ f(a\cdot{b}) = f(a)\cdot{f(b)}$ 

Vamos a probar que la función $\phi$ es multiplicativa, aunque antes habrá que probar un par de resultados.

Lema:  Si (a,m)=1 y $ a \equiv b \, (mod \,  m) $ entonces (b,m)=1 
DEMOSTRACIÓN: 
            Si $ a \equiv b \, (mod \,  m) $    entonces $ m / a-b $, es decir, para algún entero k  $a-b=mk $ y $ a=b+mk $  
Si (b,m)>1 entonces existe algún número primo p>1 que es divisor común de b y m    y por tanto divisor de $ a=b+mk $ y de m, contra hipótesis de ser (a,m)=1, y en consecuencia (b,m)=1.


Corolario: Si los "menores restos positivos" módulo m de 
             $$ r_1 , r_2 ,..., r_{m-1} , r_m $$    (1)
son una permutación de 1,2,..., m-1, m   entonces en la lista (1) hay exactamente  $\phi(m)$ números primos con
DEMOSTRACIÓN: Simple aplicación del lema.

Estos eran los resultados previos. Podemos pasar al teorema principal

Teorema:  $\phi$ es multiplicativa

DEMOSTRACIÓN: Hay que probar que si (n,m)=1 entonces $\phi(n\cdot{m})=\phi(n)\cdot{\phi(m)}$

Escribimos los números de 1 a $m\cdot{n}$ de la siguiente manera.
Como m y n han de ser diferentes (por ser primos entre sí) suponemos m>n

1      m+1       2m+1       3m+1          ...   ....      (n-2)m+1        (n-1)m+1
2      m+2       2m+2       3m+2         ....  .....      (n-2)m+2        (n-2)m+2
3      m+3      3m+3       3m+3          ....  ....       (n-2)m+3        (n-2)m+3
.         .              .               .               .....  ....             .                     .
.         .              .               .               ..... .....             .                     .
.         .              .               .               ..... .....             .                     .
.         .              .               .               ..... .....             .                     .
.         .              .               .               ..... .....             .                     .
.         .              .               .               ..... .....             .                     .
m     2m        3m            4m            ....   .....        (n-1)m               nm

Supongamos que   (m,r)=d>1 siendo r  un número entero comprendido entre 1 y m
Afirmamos que ningún elemento de la r-ésima fila del cuadro anterior 
    $$ r ,\: m+r , \: 2m+r , \: 3m+r , \:  ...   (n-2)\cdot{m} +r ,\: (n-1)\cdot{m} +r  $$
es primo relativo con $m \cdot{n}$.
Esto se debe a que $d/m$ y $d/r$ implica que $d/m\cdot{n}$ y $ d/km+r $ y esto quiere decir que ningún elemento de la fila en cuestión puede ser primo con $m\cdot{n}$
En consecuencia "tachamos" todas las filas cuyo primer elemento no sea primo con m, y sólo tomaremos en consideración aquellas filas cuyo primer elemento sea primo con m. Hay precisamente $\phi(m)$ filas con r  (  $1\leq r \leq m-1$ ) y en ellas nos concentramos descartando las $m-\phi(m)$ restantes.

Sabemos que todos los números primos con $m\cdot{n}$ se encuentran en alguna de las filas sin tachar. También sabemos que todos los números de las filas sin tachar son primos con m, porque si d es un divisor común a m y a km+r, debería ser divisor común a m y r, contra hipótesis de ser (m,r)=1.
En consecuencia los elementos de las filas no tachadas contienen todos los números enteros positivos primos con m . n (y menores que m . n) (y posiblemente algunos que no sean primos con m . n) y además son todos primos con m


Si logramos probar que en cada una de nuestras filas supervivientes hay exactamente k  números primos con $m\cdot{n}$ entonces tendremos que entre los números $1,2,....m\cdot{n}$ hay $\phi(m)\cdot{k}$ números primos con $m\cdot{n}$, es decir que $\phi(m\cdot{n})=\phi(m)\cdot{k}$
Nos interesa probar que esto es así y que $k=\phi(n)$.
Ahora escribo una cualquiera de las $\phi(m)$ filas supervivientes. Se cumple $(r,m)=1$


$$ r ,\: m+r , \: 2m+r , \: 3m+r , \:  ...   (n-2)\cdot{m} +r ,\: (n-1)\cdot{m} +r  $$
¿Cuántos de estos números son primos con $m\cdot{n}$?


Para responder a esta pregunta, en primer lugar veremos que la fila anterior es una permutación de $1,2,3,...,n-1,n$ 

Como son n números, si demostramos que son incongruentes dos a dos entonces estará claro que cada uno tiene que ser congruente con uno de los  $1,2,3,...,n-1,n$

Como los números de la fila son de la forma $xm+r$ con x número entero positivo entre 0 y n-1  probaremos por reducción al absurdo que dos cualesquiera de ellos no pueden ser congruentes módulo n.
Si $km+r \equiv{lm+r}(mod\:n)$ (como son distintos podemos suponer l<k siendo ambos menores que n, también lo es k-l) entonces $km \equiv{lm}(mod\:n)$ como (m,n)=1  entonces $k \equiv{l}(mod\:n)$ y por tanto n es divisor  de k-l, lo cual es imposible al ser k-l menor que n.

Al haber probado que los números $$ r ,\: m+r , \: 2m+r , \: 3m+r , \:  ...   (n-2)\cdot{m} +r ,\: (n-1)\cdot{m} +r  $$ una permutación de $1,2,3,...,n-1,n$  entonces concluimos que esta fila de números contiene $\phi(n)$ números primos con n.

Entonces tenemos en total $\phi(m)\cdot{\phi(n)}$ númmeros que son a la vez primos con m y con n. Estos números son a la vez primos con m y con n y por tanto primos con m . n 

¿Hay algún número más entre 1 y m. n que sea primo con m.n? Ese número tendría que estar dentro de las filas que hemos salvado y además tendría que ser primo con n, luego estaría incluído entre los $\phi(n)$ seleccionados de alguna de las filas seleccionadas.
Esto nos dice que no hay más primos con m.n que los $\phi(m)\cdot{\phi(n)}$ que hemos seleccionado.
Por tanto $\phi(m\cdot{n})=\phi(m)\cdot{\phi(n)}$



AQUÍ ACABA LA DEMOSTRACIÓN

Continuamos la exposición y comentarios sobre el informe que estamos elaborando


Aquí  hay una exposición de, entre otras cosas, las congruencias y los temas de los que trata esta entrada.

Otros enlaces: http://boards5.melodysoft.com/canalingenio/la-funcion-phi-de-euler-225.html

                     http://www.youtube.com/watch?v=lvE-ZHJTPeU

                     http://www.youtube.com/watch?v=-ZBEJFlAMg0

                   http://memorandummatematico.wordpress.com/2012/09/20/funciones-aritmeticas-la-indicatriz-de-euler/

                   http://ajlopez.zoomblog.com/archivo/2010/06/30/la-funcion-indicatriz-de-Euler-primero.html

   
                 http://ajlopez.zoomblog.com/archivo/2010/07/01/calculando-la-funcion-indicatriz-de-Eu.html

                http://www.unizar.es/analisis_matematico/teornumeros/guion.pdf

               En este enlace aparte de explicar, el autor pone enlaces a varias páginas con información sobre la función indicatriz de Euler

                http://www.unirioja.es/cu/jvarona/libroTN.html


                  http://hojamat.es/parra/prop2011.pdf


                http://mate.dm.uba.ar/~pdenapo/teoria_analitica_de_numeros/clase1.pdf

               http://hojamat.es/publicaciones/multifun.pdf

En este enlace  aparece una buena explicación sobre la función indicatriz de Euler y sus propiedades, y forma parte del blog  http://memorandummatematico.wordpress.com/2013/08/04/sistemas-de-residuos-y-la-funcion-phi-de-euler/  cuya página de inicio es  http://memorandummatematico.wordpress.com/

Esta exposición que acabo de mencionar ha sido muy inspiradora.
En particular, es revelador sacar a la luz la idea de que, siendo m y n primos entre si, dados un resto $ r_n $  de $Z´_n$ y otro $r_m$ de $Z´_m$  podemos conseguir el resto correspondiente módulo $ m \cdot{n}$
mediante $m r_n + n r_m $
Me pareció clarificadora la conexión con los sistemas completos de restos y los sistemas reducidos de restos ($Z_n$ y $Z´_n$)
Por otra parte, si tenemos un resto de $Z´_{m \cdot{n}}$, digamos k, obtenemos un par de $Z´_m   x  Z´_n$ simplemente considerando los restos de k módulo m y módulo n
Sin embargo ambos procedimientos no son inversos uno del otro, es decir, que si partes de una clase de congruencia módulo $m\cdot{n}$(elemento de  y obtenemos el par de elementos de $Z´_m   x  Z´_n$  y a partir de ese par por el método descrito volvemos al elemento de $Z´_{m \cdot{n}}$, reulta que no volvemos al mismo
EJEMPLO
CONTINUARÁ
Espero sugerencias tanto enlaces a documentos con más información como opiniones sobre el esquema del informe que propongo y sobre la demostración que incluyo, si es o no correcta, si se puede simplificar, etc.
Gracias de antemano por la colaboración.
Hasta la próxima entrada

1 comentario:

  1. Hola. En el libro "An introduction to the theory of numbers" de Hardy se da una prueba un poco más simplificada, que creo sería muy interesante desarrollar también. La relación de esta función con los sistemas completos y reducidos de residuos creo que puede ser más que bienvenida, ya que guarda una relación profunda con los mismos.

    Saludos.

    ResponderEliminar

Tu opinión respetuosa con elementales normas de cortesía y convivencia, será siempre bienvenida