Archive for the ‘Teoría de números’ Category

Articles

Demostración del Teorema de Euler con teoría de grupos.

In Teoría de grupos,Teoría de números on diciembre 8, 2011 por Tanius

En esta entrada se ofrece la demostración de un resultado básico, pero importante de la teoría de números, a saber, el teorema de Euler (algunos lo identifican también como el pequeño teorema de Fermat):

Teorema de Euler: Si a y n son primos relativos con n>1 entonces n divide a a^{\phi (n)}-1.
(Aquí \phi (n) es la función de Euler, es decir, \phi (n) representa el número de divisores positivos de n relativamente primos con n).

Para demostrar el teorema anterior, haremos uso de unos resultados básicos de la teoría de grupos.

En realidad, la base de que esta demostración resulte tan elegante es consecuencia del teorema de Lagrange que daremos por hecho:

Teorema de Lagrange: Si G es un grupo finito y H es un subgrupo de G, entonces la cardinalidad de H divide a la cardinalidad de G.
Recordemos la definición de un semigrupo:

Definición: Dado un conjunto no vacío G y una operación cerrada en G, decimos que G es un semigrupo si dicha operación es asociativa.

Demostraremos ahora los siguiente dos lemas:

Lema 1: Sea G un semigrupo finito con cancelación izquierda y derecha, es decir, que si a,x,y\in G y xa=ya entonces x=y y si ax=ay entonces x=y. Entonces G es un grupo.

Demostración del lema 1: Basta demostrar que G tiene neutro (por la derecha) y cada elemento tiene inverso (por la derecha).
Sea x\in G un elemento cualquiera de G, el cual existe por ser G no vacío.
Si el x que hemos escogido satisface que yx=y para todo y\in G, ya hemos terminado pues entonces x es el neutro de G.

Supongamos entonces que x no actúa como el neutro de G. Note que esto implica que x^2\neq x.

Considere el conjunto A=\left\{{x^n:n\in{\mathbb{N}}}\right\}=\left\{{x,x^2,...,x^n,...}\right\}\subseteq{G}. Si ocurriera que para toda n> 2 se tiene que x^n\neq x, el conjunto A sería infinito, pero G es finito.

De esta forma, existe n>2 tal que x^n=x. Es claro que el neutro debe ser x^{n-1}.
En efecto, sea y\in G, simplemente note que yx^{n-1}x=yx, cancelando obtenemos yx^{n-1}=y.

Así G tiene neutro. Llamémosle e a este elemento.

El hecho de que cada elemento de G tiene inverso se sigue de la construcción anterior. Sea h\in G. Si h=e ya terminamos. Si h^2=h se tiene que h es su propio inverso. Si no sucede ninguna de las opciones anteriores, existe n >2 tal que h^n=h=h\cdot e, cancelando, esto es lo mismo que h^{n-1}=e. Es decir, h\cdot h^{n-2}=e. Se sigue que h^{n-2} es el inverso de h.

Por lo tanto G es un grupo y terminamos la demostración del lema 1.

Recordemos que dado un grupo G y un elemento x\in G, se define el orden de x como el mínimo número natural n para el cual x^n=1. Denotaremos a este número como |x|.

Recordemos también que si x\in G con G un grupo, entonces x genera un subgrupo cíclico G  de cardinalidad |x|. De acuerdo al teorema de Lagrange, |x| dividirá a la cardinalidad de G si G es finito.

Lema 2: Sea G un grupo de cardinalidad n. Si x\in G entonces x^n=1.

Demostración del lema 2: Basta tener en cuenta que por el teorema de Lagrange, x^n=x^{|x|\cdot k} = 1 para algún número natural k.

Demostración del teorema de Euler: Si n\ge 2, definimos una relación en \mathbb{Z} mediante a\sim{b} si y sólo si n divide a a-b. Ésta es una relación de equivalencia. Por cada a\in \mathbb{Z}, denotamos por \overline{a} a su clase de equivalencia, y en este mismo contexto, definimos \mathbb{Z} _n= \left\{{\overline{a} : a\in \mathbb{Z}}\right\}.

Asimiso, si n\ge 2definimos la suma y multiplicación en \mathbb{Z} _n mediante \overline{a} + \overline{b}= \overline{a+b} y \overline{a}\cdot\overline{b}=\overline{ab} para cualesquiera \overline{a} , \overline{b}\in \mathbb{Z} _n.

En general, si n\ge 2, no sucede que \mathbb{Z} _n sea un grupo con la multiplicación definida antes.

Consideremos el subconjunto A_n\subseteq{}\mathbb{Z} _n definido por

A_n=\left\{{\overline{a} \in \mathbb{Z} _n: (a,n)=1}\right\}

en donde (a,n) denota el máximo común divisor de los enteros a y n.

De la definición de A_n, se sigue que la cardinalidad de A_n es precisamente \phi (n) . Ya que, en principio en A_n están todos los  enteros a tales que 1\le a<n(a,n) = 1. Y si hay algún a tal que 1>a o bien a>n con (a,n)=1 , por el algoritmo de la división siempre podemos asegurar la existencia de un a' tal que n divida a a-a'1\le a' <n. Entonces a\sim a', es decir, \overline{a}=\overline{a'}.

Casi para terminar, demostraremos que A_n es un grupo (n\ge 2), con la multiplicación heredada por \mathbb{Z} _n.
Sean \overline{a} , \overline{b}\in A_n. Entonces (a,n)=(b,n)=1. Por un resultado básico de divisibilidad, se sigue que (ab,n)= 1. Por tanto \overline{a} \cdot \overline{b} \in{A_n}.

De la asociatividad de \mathbb{Z} con la multiplicación usual, se sigue inmediatamente que A_n es un semigrupo (además conmutativo).

Por tanto, basta ver que se satisfacen las hipótesis del lema 1. Demostraremos que A_n es un semigrupo con cancelación por la izquierda. De la conmutatividad se seguirá la cancelación por la derecha.
En efecto, sea, \overline{a},\overline{b},\overline{c}\in A y supongamos que \overline{a} \cdot \overline{b} = \overline{a}\cdot \overline{c} . Esto es equivalente a que \overline{a(b-c)} = \overline{0}. Por cómo hemos definido la relación de equivalencia, se sigue que n divide a a(b-c). Siendo n primo relativo con a, se tendrá que n divide a b-c. Por lo tanto \overline{b-c}= \overline{0} y hemos terminado.

De acuerdo al lema 1, A_n es un grupo para todo n\ge 2.

Sea pues n\ge 2 y a cualquier entero primo relativo con n. Entonces \overline{a}\in A_n. Por el lema 2, se tiene que \overline{a}^{\phi (n)} = \overline{1}, de donde \overline{a^{\phi (n)} -1} = \overline{0}. Es decir, n divide a a^{\phi (n)} -1. Pero esto es precisamente la conclusión del teorema de Euler y hemos terminado.

Anuncios