Teorema de euler

Para el teorema referido a las relaciones numéricas en un poliedro, véase Teorema de poliedros de Euler.
Para el teorema referido a las funciones homogéneas, véase Teorema de Euler sobre funciones homogéneas.
Leonhard Euler (1707-1783).

En teoría de números el teorema de Euler, también conocido como teorema de Euler-Fermat, es una generalización del pequeño teorema de Fermat, y como talafirma una proposición sobre la divisibilidad de los números 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 más común encontrarlo con notación 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 función φ de Euler

Contenido
[ocultar]

1 Función φ de Euler
2 Congruencias
3 Prueba del teorema de Euler
4 Aplicación del teorema de Euler
5 Relación con el Teorema de Fermat
6 Referencias

[editar] Función φ de Euler
Artículo principal: Función φ de Euler

Si n es un número entero, la cantidad de enteros entre 1 y n que son primos relativoscon n se denota como φ(n):
Valor de n Coprimos con n entre 1 y n Función φ(n)
1 1 1
2 1 1
3 1,2 2
4 1,3 2
5 1,2,3,4 4
6 1,5 2
7 1,2,3,4,5,6 6
8 1,3,5,7 4
9 1,2,4,5,7,8 6
10 1,3,7,9 4

φ(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+ 1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 2016 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
90+ 24 72 44 60 46 72 32 96 42 60

A la función φ se le conoce como las sigts función φ de Euler. Tal función es multiplicativa: si m y nson primos relativos, entonces

φ(mn)=φ(m)φ(n).

Podemos verificarlo con la tabla dada arriba:

φ(30) = φ(6)φ(5) =2·4 = 8

[editar] Congruencias
Artículo principal: Congruencia

El otro concepto involucrado en el teorema de Euler es el de congruencia. En teoría de números, se dice que dos números a, b son congruentes respecto a un módulo n, cuando n divide al entero a-b. Lacongruencia de a, b respecto al módulo n se simboliza como a ≡ b (mod n).

La congruencia de números se comporta de manera similar a una igualdad (formalmente, es una relación de equivalencia):

Si a≡b (mod n) entonces: a+c≡b+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 relación.Si a≡b (mod n) y b≡c (mod n) entonces a≡c (mod n). Es otras palabras, la relación es transitiva.

Un ejemplo sencillo para entender la aritmética con congruencias lo proporciona un reloj de manecillas, ya que las horas en un reloj se comportan como congruencias módulo 12. Por ejemplo, las 15 y las 3 horas son indicadas por la misma posición en el reloj; esta equivalencia se escribiría como15 ≡ 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 común es que, aunque podemos sumar o multiplicar una misma cantidad a ambos lados de una congruencia preservándola, nopodemos hacer lo mismo con una división:

6· 4 ≡ 3·4 (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 cancelación: cuando el factor y el módulo son primos relativos:

Dado que 5·4 ≡ 5·10 (mod 6) y el máximo común divisor de 5 y 6 es 1 (es decir, son primos relativos), entonces podemos...