Teorema de Euler, Wilson y Fermat.
En esta sección estudiaremos algunos resultados clásicos de la teoría de los números, que pueden verificarse fácilmente utilizando las técnicas de la teoría de grupos discutidas en la sección anterior. Primero definiremos ciertas propiedades básicas de la teoría de números , para posteriormente enunciar el teorema de Euler, seguido del pequeño teorema de Fermat y el teorema de Wilson.
Para iniciar estudiaremos los enteros y discutiremos muchas de sus propiedades elementales, para evitar repeticiones convendremos que los símbolos de esta sección escritos en letras minúsculas representaran números enteros.
Dados $a$ y $b$ con $0<b<a$, podemos encontrar $r$ y $q$ tales que $a=q\cdot b+r$ donde $0<r<b$, es este hecho es conocido como el algoritmo de la división o el algoritmo de Euclides, donde $r$ representa el residuo al dividir $a$ por $b$ y $q$ el cociente. Suponemos que el lector esta familiarizado con este hecho.
Si $b|_{a}$ ($b$ divide a $a$), esto implica que $r=0$ por lo tanto $a=q\cdot b$ para algún $q$ y llamamos a $b$ un divisor de $a$.
Definición:Se dice que un entero positivo $d$ es el máximo común divisor de $a$ y $b$ si:
i) $d$ es divisor de $a$ y de $b$.
ii) Cualquier divisor de $a$ y $b$ es divisor de $d$.
Utilizaremos la notación $(a,b)$ para representar el máximo común divisor de $a$ y $b$.
Definición: Dos enteros $a$ y $b$ se dicen primos relativos si $(a,b)=1$.
Definición: Un número entero $p>1$ se dice que es primo si sus únicos divisores son $\pm 1$ y $\pm p$.
Definición: Si $m$ es un número entero positivo, entonces la función $\varphi$ de Euler aplicada a $m$ se define como:
$\varphi(m)=\{n\in \mathbb{Z}, 0<n<m$ / $(n,m)=1\}$
Es decir, $\varphi(m)$ es el numero de enteros positivos menores que $m$, los cuales son primos relativos con $m$.
Ejemplo:
$\varphi(16)=8$ ya que hay 8 números naturales menores que 16 que son primos relativos con 16 los cuales son: $\{1,3,5,7,9,11,13,15\}$.
Dado que el $1$ es primo relativo consigo mismo, tenemos que $\varphi(1)=1$ para otros números se cumple que:
i) Si $p$ es un número primo, entonces $\varphi(p)=p-1$, ya que será primo relativo con todo los número naturales menores que él.
ii) Si $p$ es un número primo, entonces $\varphi(p^m)=(p-1)p^{m-1}$.
iii) Si $(m,n)=1$, entonces $\varphi(m\cdot n)=\varphi(m)\cdot \varphi(n)$
iv) $\varphi(n)=n\prod_{p|_n}(1-\frac{1}{p})$
Definición:Sea $ n>0 $ un número entero, definimos $a\equiv b$ mod$(n)$ si $n|_{b-a}$, leído como $a$ es congruente con $b$ modulo $n$.
Ejemplo:
$13\equiv 5$ mod$(2)$ ya que $2|_{13-5}$
Esta relación de congruencia tiene las siguientes propiedades:
i) La relación de congruencia modulo $n$ define una relación de equivalencia sobre el conjunto de los números enteros.
ii) Esta relación de equivalencia posee $n$ disitintas clases de equivalencia.
iii) Si $a\equiv b$ mod$(n)$ y $c\equiv d$ mod$(n)$, entonces $a+c\equiv b+d$ mod$(n)$.
iv) Si $a\cdot c\equiv a\cdot b$ mod$(n)$ y $(a,n)=1$, entonces $c\equiv b$ mod$(n)$.
Como mencionamos previamente que la relación de equivalencia modulo $n$ es un caso particular de la relación vista en el capitulo 5, de lo cual se deduce que define una relación de equivalencia sobre el conjunto de los números enteros.
Denotemos $[a]$ la clase de equivalencia de $a$ y la llamaremos clase de congruencia modulo $n$. Para verificar ii) consideremos un entero $a$ arbitrario, se tiene por el algoritmo euclidiano $a=k\cdot n+r$ donde $0\leq r<n$, por lo cual $a\equiv r$ mod$(n)$ y $a\in [r]$, luego $[a]=[r]$ y como hay $n$ distintos residuos $r$, entonces hay $n$ distintas clases de congruencia modulo $n$ las cuales son: $[0],[1],[2],...,[n-1]$.
Dejaremos la verificación de iii) y iv) al lector.
Consideremos ahora el conjunto $\mathbb{Z}_n$ de todas las clases de equivalencia modulo $n$, es decir:
$\mathbb{Z}_n=$$[0],[1],[2],...,[n-1]$.
Dados dos elementos $[i]$ y $[j]$ definimos sobre $\mathbb{Z}_n$ la siguiente ley de composición interna:
$[i]+[j]=[i+j]$
Esta "suma" se verifica que esta bien definida ya que si $[i]=[i´]$ y $[j]=[j´]$ entonces
$[i]+[j]=$$[i+j]=$$[i´+j´]$$=[i´]+[j´]$. Finalmente se puede verificar que esta operación es asociativa e invertiva cuyo elemento neutro es $e=[0]$, por lo cual $(\mathbb{Z}_n,+)$ es un grupo, el cual es denominado el grupo de las clases residuales.
Ahora consideremos el conjunto $U_n$ de clases de equivalencia modulo $n$ las cuales son primos relativos con $n$, es decir, si $[a]\in U_n$ entonces $(a,n)=1$. Por ejemplo $U_4=\{[1],[3]\}$ ya que $(1,4)=1$ y $(3,4)=1$.
Ahora surge la pregunta ¿cuantos elementos posee $U_n$?, debido a que sus elementos son las clases cuyos elementos son primos relativos con $n$, entonces $U_n$ posee $\varphi(n)$ elementos.
Dados dos elementos $[i]$ y $[j]$ definimos sobre $U_n$ la siguiente operación:
$[i]\cdot [j]=[i\cdot j]$
Verifiquemos que esta bien definida esta operación.
Si $[i]=[i´]$ y $[j]=[j´]$ entonces $[i]\cdot [j]=[i\cdot j]=[i´\cdot j´]=[i´]\cdot [j´]$, por lo tanto esta bien definida. Es fácil verificar que esta operación es asociativa cuyo elemento neutro es $[1]$ así que verifiquemos que todo elemento posee inverso y es cerrada en $U_n$.
Si $[a]\in U_n$ entonces $(a,n)=1$, por lo tanto existen enteros $x,y$ tales que
$a\cdot x+n\cdot y=1$
$a\cdot x -1=-n\cdot y$
Luego $a\cdot x\equiv 1$ mod$n$ por lo tanto $[a\cdot x]=[a]\cdot [x]=[1]$ y como$(x,n)=1$ de lo cual $[x]\in U_n$. Entonces todo $[a]\in U_n$ posee elemento inverso.
Si $[a],[b]\in U_n$ entonces $(a,n)=1$ y $(b,n)=1$, luego $(ab,n)=1$ y $[a\cdot b]\in U_n$ como se quería verificar.
Con todo lo anterior llegamos a que $(U_n,\cdot)$ es un grupo, un resultado que sera de gran utilidad al momento de demostrar el teorema de Euler.
Teorema de Euler: SI $a$ y $n$ son primos relativos, entonces $n$ divide a $a^{\varphi(n)}-1$.
Dms:
Veamos que $a^{\varphi(n)}\equiv 1$ mod$(n)$.
Consideremos al grupo $U_n$, y ya que $a$ y $n$ son primos relativos entonces $[a]\in U_n$, dado que $O(U_n)=\varphi(n)$, luego $[a]^{\varphi(n)}=[1]$ ya que todo elemento elevado al orden del grupo da como resultado al neutro, por lo tanto $a^{\varphi(n)}\equiv 1$ mod$(n)$ como se quería verificar.
Teorema de Fermat: Si $p$ es un número primo y $a$ es un entero primo
Dms:
Como $(a,p)=1$ por el teorema de Euler se tiene que $p$ divide a $a^{\varphi(p)}-1$ y como $\varphi(p)=p-1$ ya que $p$ es primo, luego $p$ divide a $a^{p-1}-1$.La ecuación $a^{\varphi(p)}-1\equiv 1$ mod$(p)$, la cual se obtiene mediante el teorema de Fermat, nos proporciona un criterio para determinar si un número $p$ es primo, ya que si un numero entero $p$ no satisface esta ecuación de congruencia implica que $p$ es compuesto.
Por ejemplo consideremos a $p=2$ y $a=6$, como $2$ no divide $6^{2-1}-1$ determinamos que $6$ es compuesto.
Veamos ahora otro criterio para determinar la primalidad de cierto numero entero que es menos practico que el anterior.
Teorema de Wilson: Un número $p$ es primo si y solo si $(p-1)!\equiv -1$ mod$(p)$.
Dms:
$\Rightarrow$
Si $p=2$ el resultado es evidente así que supongamos que $p>2$.
Consideremos al grupo $U_p$, ya que $p$ es primo entonces $U_p=\{[1],[2],..[p-1]\}$.
Como cada elemento $x\in U_p$ posee un único inverso $y$ tal que $x\cdot y\equiv 1$ mod$(p)$, si $x=y$ por ser $p$ primo implica que $x=1$ o $x=p-1$ por lo cual $1$ y $p-1$ son inversos el uno del otro. Por tanto para cualquier otro elemento del grupo distinto de éstos se tiene que su inverso también es distinto de éstos. En consecuencia podemos agrupar el resto de elementos por parejas (cada uno junto a su inverso) para que se cumpla lo siguiente:
$2\cdot 3\cdot ...\cdot(p-2)\equiv 1$ mod$(p)$ esto es $(p-2)!\equiv 1$ mod$(p)$
y como $(p-1)\equiv -1$ mod $(p)$, multiplicando a ambos lados de la ecuación queda que
$(p-1)(p-2)!\equiv -1\cdot 1$ mod$(p)$
$(p-1)!\equiv -1$ mod$(p)$.
Obteniendo el resultado buscado.
$\Leftarrow$
Razonando por contradicción supongamos que $p$ es compuesto. Entonces sus divisores positivos se encuentran entre los enteros $1,2,...,p-1$ de lo cual $p$ posee un divisor $d>1$. Como $(p-1)!\equiv -1$ mod$(p)$ y $d$ divide a $p$ entonces $d$ también divide a $(p-1)!$ y por la congruencia $d$ divide $(p-1)!+1$ Por tanto $d$ divide a $1$, hecho que nos lleva a una contradicción ya que $d>1$. En consecuencia $p$ es primo siempre que $(p-1)!\equiv -1$ mod$(p)$.
0 comentarios:
Publicar un comentario