|
|
|
|
| |
El teorema de Euler, también conocido como teorema de Euler-Fermat, es una generalización del pequeño teorema de Fermat, y como tal afirma una proposición sobre divisibilidad de números. 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
Función φ de Euler
Si n es un número entero, la cantidad de enteros entre 1 y n que son primos relativos con 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 |
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 |
| 90+ |
24 |
72 |
44 |
60 |
46 |
72 |
32 |
96 |
42 |
60 |
|
A la función φ se le conoce como función φ de Euler. Tal función es multiplicativa: si m y n son primos relativos, entonces
- φ(mn)=φ(m)φ(n).
Podemos verificarlo con la tabla dada arriba:
- φ(30) = φ(6)φ(5) =2·4 = 8
Prueba del teorema de Euler
La prueba original del teorema de Euler, en notación moderna, se desarrolla en los siguientes pasos.
| Pasos generales |
Ejemplo con n = 8, a = 3 |
| Consideremos el conjunto P de los enteros menores que n y coprimos con n |
Consideremos el conjunto P = {1,3,5,7} |
| Multipliquemos cada elemento del conjunto P por a para formar el conjunto Q |
Construimos el conjunto Q = {3,9,15,21} |
| Los elementos del conjunto Q son congruentes a los del elemento P (en diferente orden). |
3≡3 (mod 8 ), 9≡1 (mod 8 ), 15≡7 (mod 8 ), 21≡5 (mod 8 ) |
| Sea u el producto de los elementos de P, y sea v el producto de los elementos de Q |
u= 1·3·5·7 = 105, v=3·9·15·21=8505 |
| Los números u y v son congruentes pues sus factores son congruentes: u≡v (mod n) |
105≡8505 (mod 8 ) |
| El entero v es igual a u multiplicado por aφ(n): v=u·aφ(n) |
v= 3·9·15·21 = (3·1)(3·5)(3·7)(3·9) = 34· (1·3·5·7) = 3φ(8)·105 |
| Cancelamos el factor u en la congruencia u≡v (mod n): u≡u·aφ(n) (mod n) |
105≡3φ(8)·105 (mod 8 ) |
| Concluimos 1≡aφ(n) (mod n) |
1≡3φ(8) (mod 8 ) |
Es importante recalcar que la cancelación sólo 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) sólo puede obtenerse debido a que a y n son primos relativos.
Aplicación del teorema de Euler
Una aplicación del teorema de Euler es en la resolución de ecuaciones de congruencia.
Por ejemplo, se desea encontrar todos los números x que satisfacen
-
- 5x ≡ 2 (mod 12)
en otras palabras, todos los números que al multiplicarlos por 5, dejan residuo 2 en la división por 12. O de otra forma, todos los números 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 ecuación por 53:
-
- 53 · 5x ≡53·2 =250 ≡ 10 (mod 12)
- 54 x ≡ 10 (mod 12)
- x≡10 (mod 12)
Entonces, la conclusión es que, cualquier número que al dividirse por 12 tenga residuo 10, será una solución de la ecuación. Se puede verificar con un ejemplo. Si se divide 34 entre 12, el residuo es 10, por lo que x=34 debe funcionar como solución. Para verificarlo, se divide 34·5=170 entre 12, obtenemos un cociente 14 y un residuo 2, como se esperaba.
|
|
|
|
|
|
| |
Hoy habia 15 visitantes (17 clics a subpáginas) ¡Aqui en esta página!
|
|
|
|
|
|
|
|
