Ejemplo 2: Trabajo del alumno
TRABAJOS DE CLASE DE
MATEMTICAS
Demostracin del teorema de Euler-Fermat
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 1
Ejemplo 2: Trabajo del alumno
NDICE
Trabajos de clase de matemticas 3
Introduccin 3
El Teorema 3
La funcin fi de Euler 3
El pequeo teorema de Fermat 4
Demostracin del pequeo teorema de Fermat 5
Demostracin del teorema de Euler-Fermat 7
Aplicaciones 9
Conclusin 9
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 2
Ejemplo 2: Trabajo del alumno
TRABAJOS DE CLASE DE
MATEMTICAS
Demostracin del teorema de Euler-Fermat
Introduccin
Mi inters por Euler como matemtico surgi inicialmente mientras resolva un crucigrama
de la revista The Listener: en l, el mensaje oculto deca Lea a Euler; l es, de entre todos
nosotros, el maestro, as que cuando vi su nombre en la lista de sugerencias no tuve ms
remedio que buscar ms informacin acerca de l. Euler fue un matemtico del siglo
XVIII y es el autor de las primeras demostraciones de muchsimas conjeturas y problemas.
Centrndonos nicamente en teora de nmeros, entre sus logros se encuentran la
demostracin del teorema de Fermat sobre la suma de dos cuadrados y del pequeo
teorema de Fermat. Adems llev a cabo un ingente trabajo que aos ms tarde conducira
a la primera demostracin del teorema de los cuatro cuadrados. El logro en el que me voy
a centrar no es tan conocido como los anteriores: es la generalizacin del pequeo teorema
de Fermat y se conoce con el nombre de teorema de Euler-Fermat.
El teorema
El teorema de Euler-Fermat1 establece que si a y n son dos nmeros primos entre s
(primos relativos), entonces:
an 1 (mod n)
donde n es la funcin fi de Euler (tambin denominada funcin indicatriz de Euler).
La funcin fi de Euler
La funcin fi de Euler2, o n, indica cuntos nmeros hay menores que n que sean primos
relativos a n. Por ejemplo: 10 es igual a 4, puesto que hay cuatro nmeros menores de
diez que son primos relativos (o coprimos) a 10: {1, 3, 7, 9}. 11 es igual a 10 porque 11 es
primo, con lo que todos los nmeros inferiores a l son primos relativos a 11. Por otro
lado, 6 es igual a 2, dado que 1 y 5 son primos relativos a 6, pero 2, 3 y 4 no lo son.
1
[Link]
2
[Link]
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 3
Ejemplo 2: Trabajo del alumno
A continuacin se muestra una tabla con los valores que tiene la funcin fi de Euler hasta
N=20.
N N
2 1
3 2
4 2
5 4
6 2
7 6
8 4
9 6
10 4
11 10
12 4
13 12
14 6
15 8
16 8
17 16
18 6
19 18
20 8
Los ejemplos siguientes servirn para ilustrar el teorema de Euler.
Sea n = 10 y a = 3. Ntese que 10 y 3 son primos relativos. En la tabla 10 = 4. Luego, 34
= 81 1(mod 10).
Tambin, si n = 15 y a = 2 vemos que 28 = 256 1 (mod 15).
3 [Link]
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 4
Ejemplo 2: Trabajo del alumno
El pequeo teorema de Fermat
El teorema de Euler-Fermat es una generalizacin del pequeo teorema de Fermat3 y se
cumple para todos los enteros n que sean coprimos (es decir, primos relativos) con a. El
pequeo teorema de Fermat slo se cumple cuando a y p son coprimos (primos entre s) y
adems p es primo. Dicho teorema establece que:
ap a (mod p)
ap-1 1 (mod p)
Queda inmediatamente patente que esta igualdad es un caso particular del teorema de
Euler-Fermat cuando p es primo, dado que hemos visto que, en esos casos, p es siempre
igual a p-1.
A modo de introduccin al teorema de Euler-Fermat pasar a demostrar el pequeo
teorema de Fermat.
Demostracin del pequeo teorema de Fermat
Se trata de demostrar que: ap a (mod p)
Tomemos dos nmeros a y p que sean coprimos (primos entre s), y donde p sea primo.
Consideremos el conjunto formado por los mltiplos de a {a, 2a, 3a, 4a, 5a ..... (p-1)a }
Consideremos tambin el conjunto de nmeros {1, 2, 3, 4, 5 ..... (p-1)}
Si se toma su valor mdulo p, cada elemento del primer conjunto resulta ser congruente
con un elemento del segundo conjunto, existiendo entonces una correspondencia biyectiva
entre los dos conjuntos, tal y como se demuestra en el Lema 1.
Si tomamos ahora el producto del primer conjunto { a x 2a x 3a x 4a x 5a ...... (p-1)a } y el
producto del segundo conjunto { 1 x 2 x 3 x 4 x 5 ..... (p-1) } podemos ver que son
congruentes entre s (puesto que se cumple que cada elemento del primer conjunto es
congruente con un elemento del segundo conjunto).
Por lo tanto, { a x 2a x 3a x 4a x 5a ...... (p-1)a } { 1 x 2 x 3 x 4 x 5 ..... (p-1) } (mod p)
En el lado izquierdo, podemos sacar fuera el factor ap-1:
De este modo, tenemos: ap-1 {1 x 2 x 3 x 4 x 5..... (p-1)} {1 x 2 x 3 x 4 x 5..... (p-1)} (mod p)
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 5
Ejemplo 2: Trabajo del alumno
Si dividimos cada lado entre {1 x 2 x 3 x 4 x 5 ..... (p-1)}, lo cual es vlido puesto que p es
primo, obtenemos: ap-1 1 (mod p)
ap a (mod p)
COMO QUERAMOS DEMOSTRAR
Lema 1: Cada nmero del primer conjunto tiene que ser congruente con un nmero (y
slo con uno) del segundo conjunto y cada nmero del segundo conjunto ha de ser
congruente con un nmero (y slo con uno) del primer conjunto. Puede que esto no
resulte obvio en un primer momento, pero se puede demostrar en tres pasos lgicos.
(1) Cada nmero del primer conjunto ha de ser congruente con uno de los elementos del
segundo conjunto, puesto que todas las congruencias posibles (excepto 0) estn
presentes, y ningn elemento va a ser congruente con 0 puesto que a y p son coprimos
(primos entre s).
(2) Un nmero del primer conjunto no puede ser congruente con dos nmeros del
segundo conjunto, dado que un nmero slo puede ser congruente con nmeros cuya
diferencia sea un mltiplo de p. Teniendo en cuenta que todos los elementos del
segundo conjunto son menores que p, concluimos que un nmero dado slo puede ser
congruente con uno de estos integrantes del segundo conjunto.
(3) No existen dos nmeros en el primer conjunto (nmeros que denominaremos ba y ca)
que puedan ser congruentes con el mismo nmero del segundo conjunto. De haberlos,
estos dos nmeros habran de ser congruentes entre s ba ca (mod p) lo que, a su vez,
implicara que b c (mod p), lo cual no es cierto, puesto que estos dos nmeros son
diferentes y son ambos menores que p.
Por lo tanto, con estos tres pasos queda demostrado el Lema 1.
Demostracin del teorema de Euler-Fermat
Teniendo en cuenta que el pequeo teorema de Fermat es un caso particular del teorema de
Euler-Fermat (donde n es primo), no resulta extrao que las dos demostraciones sean bastante
parecidas. De hecho, slo es necesario introducir unas ligeras modificaciones a la demostracin
del pequeo teorema de Fermat para poder demostrar el teorema de Euler-Fermat4.
4
[Link]
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 6
Ejemplo 2: Trabajo del alumno
Se trata de demostrar que: an 1 (mod n)
Tomemos dos nmeros a y n que sean coprimos (primos entre s).
Consideremos tambin el conjunto N de nmeros que son primos relativos a n {1, n1,
n2...nn}
Este conjunto contiene n elementos (n se define como el nmero de nmeros que son
primos relativos a n)
Consideremos ahora el conjunto aN, donde cada elemento es el producto de a por un
elemento de N { a, an1, an2... ann }
Cada elemento del conjunto aN es congruente con un elemento del conjunto N (mod n),
(esto se puede demostrar aplicando el mismo razonamiento expuesto en el Lema 1), por lo
que podemos concluir que los dos conjuntos son congruentes entre s.
Por lo tanto: { a x an1 x an2 x ... x ann } { 1 x n1 x n2 x ... x nn } (mod n)
Si en el lado izquierdo sacamos fuera el factor an, obtenemos que:
an {1 x n1 x n2 x ... x nn} {1 x n1 x n2 x ... x nn} (mod n)
Si a continuacin dividimos ambos lados entre {1 x n1 x n2 x ... x nn} (lo cual es vlido
puesto que todos los elementos son primos relativos a n) obtendremos que:
an 1 (mod n)
COMO QUERAMOS DEMOSTRAR
Aplicaciones
A diferencia de otros trabajos de Euler en teora de nmeros (p. ej., su demostracin del
teorema de Fermat sobre la suma de dos cuadrados), el teorema de Euler-Fermat tiene
usos y aplicaciones muy concretos en el mundo real, aunque, como sucede con gran parte
de la teora de nmeros, stos quedan circunscritos casi exclusivamente al mundo de la
criptografa y el criptoanlisis. Tanto el pequeo teorema de Fermat como el teorema de
Euler-Fermat se utilizan para el cifrado (codificacin) y el descifre (descodificacin) de
datos; ms especficamente, se emplean para el sistema de cifrado RSA5, cuya proteccin
est basada en el hecho de que resulta complicado descomponer en factores nmeros
primos altos elevados a potencias grandes.
5
[Link]
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 7
Ejemplo 2: Trabajo del alumno
Conclusin
Es posible que este teorema no sea el trabajo matemtico ms elegante de Euler
(personalmente, mi preferido es su demostracin del teorema de Fermat sobre la suma de
dos cuadrados, basada en el descenso infinito) y que, por aquel entonces, no se considerase
como su trabajo ms importante; sin embargo, al menos en teora de nmeros, se trata de
su trabajo ms til para el mundo actual.5
Esta demostracin me ha dado la oportunidad de vincular algunos de los trabajos que he
realizado en reas temticas tan distantes como son las unidades opcionales de Matemtica
discreta y de Conjuntos, relaciones y grupos. Estas dos unidades de opcionales son, a mi
modo de ver, los dos apartados de matemticas ms puros que he estudiado. Sin embargo,
por alguna razn, rara vez se los relaciona en clase. Este proyecto me ha permitido
explorar los vnculos que existen entre estas dos unidades y me ha dado la oportunidad de
utilizar los conocimientos que aporta una aplicados a la otra, ampliando as mi perspectiva
de las matemticas.
Demostracin del teorema de Euler-Fermat
Material de ayuda al profesor de Matemticas NM y NS 8