Teorema de Euler
Teorema de Euler
En teora de nmeros el teorema de Euler, tambin conocido como teorema de Euler-Fermat, es una generalizacin del pequeo teorema de Fermat, y como tal afirma una proposicin sobre la divisibilidad de los nmeros enteros. El teorema establece que: Si a y n son enteros primos relativos, entonces n divide al entero a(n)- 1 Leonhard Euler (1736) sin embargo, es ms comn encontrarlo con notacin moderna en la siguiente forma: Si a y n son enteros primos relativos, entonces a(n) 1 (mod n). Leonhard Euler (1736) donde (n) es la funcin de Euler
Funcin de Euler
Si n es un nmero entero, la cantidad de enteros entre 1 y n que son primos relativos con n se denota como (n):
Leonhard Euler (1707-1783).
Valor de n Coprimos con n entre 1 y n Funcin (n) 1 2 3 4 5 6 7 8 9 10 1 1 1,2 1,3 1,2,3,4 1,5 1,2,3,4,5,6 1,3,5,7 1,2,4,5,7,8 1,3,7,9 1 1 2 2 4 2 6 4 6 4
(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 0+ 10+ 4 20+ 8 30+ 8 1 1 2 2 4 8 2 8 6 4 6 18
10 4
12 6
16 6
12 10 22 8
20 12 18 12 28
30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42 50+ 20 32 24 52 18 40 24 36 28 58 60+ 16 60 30 36 32 48 20 66 32 44 70+ 24 70 24 72 36 40 36 60 24 78 80+ 32 54 40 82 24 64 42 56 40 88
Teorema de Euler
2
90+ 24 72 44 60 46 72 32 96 42 60
A la funcin se le conoce como las sigts funcin de Euler. Tal funcin es multiplicativa: si m y n son primos relativos, entonces (mn)=(m)(n). Podemos verificarlo con la tabla dada arriba: (30) = (6)(5) =24 = 8
Congruencias
El otro concepto involucrado en el teorema de Euler es el de congruencia. En teora de nmeros, se dice que dos nmeros a, b son congruentes respecto a un mdulo n, cuando n divide al entero a-b. La congruencia de a, b respecto al mdulo n se simboliza como a b (mod n). La congruencia de nmeros se comporta de manera similar a una igualdad (formalmente, es una relacin de equivalencia): Si ab (mod n) entonces: a+cb+c (mod n) y ac bc (mod n) para cualquier entero c. Es decir, se puede sumar o multiplicar una misma cantidad a ambos lados de una congruencia y se preserva la relacin. Si ab (mod n) y bc (mod n) entonces ac (mod n). Es otras palabras, la relacin es transitiva. Un ejemplo sencillo para entender la aritmtica con congruencias lo proporciona un reloj de manecillas, ya que las horas en un reloj se comportan como congruencias mdulo 12. Por ejemplo, las 15 y las 3 horas son indicadas por la misma posicin en el reloj; esta equivalencia se escribira como 15 3 (mod 12) y se obtiene de que 12 divide a 15-3. Si ahora el reloj marca las 5, dentro de 30 horas marcar las 11, porque 12 divide a 35-11 =24 y as: 5+30 = 35 11 (mod 12). Una particularidad de las congruencias, que la diferencia de la igualdad comn es que, aunque podemos sumar o multiplicar una misma cantidad a ambos lados de una congruencia preservndola, no podemos hacer lo mismo con una divisin: 6 4 34 (mod 6), pues 6 divide a 24-12; sin embargo no es cierto que 6 3 (mod 6). Sin embargo, hay un caso especial en el que s es posible efectuar tal cancelacin: cuando el factor y el mdulo son primos relativos: Dado que 54 510 (mod 6) y el mximo comn divisor de 5 y 6 es 1 (es decir, son primos relativos), entonces podemos cancelar el 5 y obtener 4 10 (mod 6).
Prueba del teorema de Euler
La prueba original del teorema de Euler, en notacin moderna, se desarrolla en los siguientes pasos.
Teorema de Euler
Pasos generales Consideremos el conjunto P de los enteros menores que n y coprimos con n Multipliquemos cada elemento del conjunto P por a para formar el conjunto Q Los elementos del conjunto Q son congruentes a los del elemento P (en diferente orden). Sea u el producto de los elementos de P, y sea v el producto de los elementos de Q Los nmeros u y v son congruentes pues sus factores son congruentes: vu (mod n) El entero v es igual a u multiplicado por a(n): v=ua(n)
Ejemplo con n = 8, a = 3 Consideremos el conjunto P = {1,3,5,7} Construimos el conjunto Q = {3,9,15,21} 33 (mod 8), 91 (mod 8), 157 (mod 8), 215 (mod 8)
u= 1357 = 105, v=391521=8505 8505105 (mod 8) v= 391521 = (31)(33)(35)(37) = 34 (1357) = 3(8)105 3(8)105105 (mod 8) 3(8) 1 (mod 8)
Cancelamos el factor u en la congruencia vu (mod n): ua(n) u (mod n) Concluimos a(n)1 (mod n)
Es importante recalcar que la cancelacin slo es posible puesto que u y n son primos relativos. De manera similar, el tercer paso (los elementos de Q son congruentes a los de P) slo puede obtenerse debido a que a y n son primos relativos.
Aplicacin del teorema de Euler
Una aplicacin del teorema de Euler es en la resolucin de ecuaciones de congruencia. Por ejemplo, se desea encontrar todos los nmeros x que satisfacen 5x 2 (mod 12) en otras palabras, todos los nmeros que al multiplicarlos por 5, dejan residuo 2 en la divisin por 12. O de otra forma, todos los nmeros x tales que 12 divida a 5x-2. El teorema de Euler dice que 5(12) = 54 1 (mod 12) por lo que, multiplicando ambos lados de la ecuacin por 53: 53 5x 532 =250 10 (mod 12) 54 x 10 (mod 12) x10 (mod 12) Entonces, la conclusin es que, cualquier nmero que al dividirse por 12 tenga residuo 10, ser una solucin de la ecuacin. Se puede verificar con un ejemplo. Si se divide 34 entre 12, el residuo es 10, por lo que x=34 debe funcionar como solucin. Para verificarlo, se divide 345=170 entre 12, obtenemos un cociente 14 y un residuo 2, como se esperaba.
Teorema de Euler
Relacin con el Teorema de Fermat
El Teorema de Euler es una generalizacin del teorema de Fermat que establece: Si p es un nmero primo y a es un entero, entonces p divide al nmero ap-1-1 Pierre de Fermat (1640) Fermat estableci tal resultado en una carta a Frnicle de Bessy, pero como era usual en l, omiti la prueba del mismo:
Tout nombre premier mesure infailliblement une des puissances -1 de quelque progression que ce soit, et lexposant de la dite puissance est sous-multiple du nombre premier donn -1. (...) Et cette proposition est gnralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la dmonstration, si je n'apprhendois d'tre trop long. Todo nmero primo mide una de las potencias menos uno de cualquier progresin en la que el exponente es un mltiplo del primo dado menos uno. (...) Y esta proposicin es generalmente cierta para todas las progresiones y todos los nmeros primos; te enviara la prueba, si no temiese que es demasiado larga.
Pierre de Fermat No fue sino hasta que Euler prob su teorema, que qued demostrado el resultado de Fermat, pues es un corolario del teorema de Euler. En notacin de congruencias, el teorema de Fermat establece que Si p es un nmero primo y a es un entero no divisible por p, entonces ap - 1 1 (mod p). Pierre de Fermat (1640) En la afirmacin original de Fermat, no se hace explcita la suposicin de que a y p son primos relativos. Dado que si p es un nmero primo, todos los nmeros {1,2,3,...,p-1} son primos relativos con p, se cumple que (p)=p-1 y por tanto el teorema de Fermat es una consecuencia directa del teorema de Euler. Por sta razn al teorema de Euler se le conoce en ocasiones como teorema de Euler-Fermat.
Referencias
Andrews, George E. (1994). Number Theory. Dover. 0-486-68252-8. Cohn, Harvey (1980). Advanced Number Theory. Dover. 0-486-64023-X. Erds, Paul; Surnyi, Janos (2003). Topics in the theory of numbers (2a ed. edicin). New York: Springer. 0-387-95320. Amabda Bergeron; David White (17). Transcripcin de la carta de Pierre de Fermat a Frnicle de Bessy. [1] (pdf). Consultado el 24 de septiembrede 2007.
Referencias
[1] http:/ / www. cs. utexas. edu/ users/ wzhao/ fermat2. pdf
Fuentes y contribuyentes del artculo
Fuentes y contribuyentes del artculo
Teorema de Euler Fuente: [Link] Contribuyentes: Alfredobi, Belgrano, Elferdo, Erufailon, Farisori, Fcr, Jkbw, Juan Mayordomo, Labor, Lualalsa, Magister Mathematicae, Matdrodes, Netito777, Raulshc, Rondador, Sabbut, 24 ediciones annimas
Fuentes de imagen, Licencias y contribuyentes
Archivo:Leonhard Euler by Handmann .png Fuente: [Link] Licencia: Public Domain Contribuyentes: Beria, Bohme, Boo-Boo Baroo, Ecummenic, Funck77, Leyo, QWerk, Shakko, 2 ediciones annimas
Licencia
Creative Commons Attribution-Share Alike 3.0 //[Link]/licenses/by-sa/3.0/
