Teorema de Fermat-Euler
Teorema de Fermat-Euler
Nos definimos $\varphi (m)$ como la cantidad de números coprimos y menores a $m$. El Teorema de Fermat-Euler nos dice que si $a$ es un entero coprimo con $m$ se cumple que:$$a^{\varphi (m)}\equiv 1\pmod{m}$$Demostración:
Sea $S=\{x_1,\ldots ,x_{\varphi (m)}\}$ el conjunto de los números coprimos con $m$ y menores a él. Si multiplico a todos los números por algún $a\in S$ vamos a obtener nuevamente todos números coprimos con $m$. Además, notemos que estos números que vamos a obtener son distintos entre sí módulo $m$ pues$$ax_i\equiv ax_j\pmod{m}\iff a(x_i - x_j)\equiv 0\pmod{m}\iff x_i \equiv x_j\pmod{m}$$pero ambos son menores a $m$ por lo tanto $x_i=x_j$.
Entonces, $\{ax_1,\ldots ,ax_{\varphi (m)}\}$ es una permutación de $S$ si miramos a todos los números módulo $m$. Luego, si multiplicamos a todos los elementos de ambos conjuntos y miramos módulo $m$ vamos a obtener lo mismo:$$x_1\cdot \ldots \cdot x_{\varphi (m)}\equiv ax_1\cdot \ldots \cdot ax_{\varphi (m)}\equiv a^{\varphi (m)}x_1\cdot \ldots \cdot x_{\varphi (m)}\pmod{m}$$Pero recordemos la propiedad de las congruencias que nos dice que si $n$ es un entero coprimo con $m$ existe un número $n'$ llamado inverso multiplicativo de $n$ módulo $m$ tal que $n\cdot n'\equiv 1\pmod{m}$.
Si multiplicamos a ambos lados por el inverso multiplicativo de cada uno de los $x_i$ obtenemos:$$a^{\varphi (m)}\equiv 1\pmod{m}$$Que es lo que queríamos demostrar. $\blacksquare$
NOTA: vale la pena aclarar que usamos que $a$ es coprimo cuando lo tomamos de $S$ y que el teorema no vale si $a$ no es coprimo con $m$. Un ejemplo sería ver $2^4$ módulo $8$.
Algo interesante es que el inverso de $a$ módulo $m$ es $a^{\varphi (m) -1}$ ya que $a\cdot a^{\varphi (m)-1}\equiv a^{\varphi (m)}\equiv 1\pmod{m}$.
Sea $S=\{x_1,\ldots ,x_{\varphi (m)}\}$ el conjunto de los números coprimos con $m$ y menores a él. Si multiplico a todos los números por algún $a\in S$ vamos a obtener nuevamente todos números coprimos con $m$. Además, notemos que estos números que vamos a obtener son distintos entre sí módulo $m$ pues$$ax_i\equiv ax_j\pmod{m}\iff a(x_i - x_j)\equiv 0\pmod{m}\iff x_i \equiv x_j\pmod{m}$$pero ambos son menores a $m$ por lo tanto $x_i=x_j$.
Entonces, $\{ax_1,\ldots ,ax_{\varphi (m)}\}$ es una permutación de $S$ si miramos a todos los números módulo $m$. Luego, si multiplicamos a todos los elementos de ambos conjuntos y miramos módulo $m$ vamos a obtener lo mismo:$$x_1\cdot \ldots \cdot x_{\varphi (m)}\equiv ax_1\cdot \ldots \cdot ax_{\varphi (m)}\equiv a^{\varphi (m)}x_1\cdot \ldots \cdot x_{\varphi (m)}\pmod{m}$$Pero recordemos la propiedad de las congruencias que nos dice que si $n$ es un entero coprimo con $m$ existe un número $n'$ llamado inverso multiplicativo de $n$ módulo $m$ tal que $n\cdot n'\equiv 1\pmod{m}$.
Si multiplicamos a ambos lados por el inverso multiplicativo de cada uno de los $x_i$ obtenemos:$$a^{\varphi (m)}\equiv 1\pmod{m}$$Que es lo que queríamos demostrar. $\blacksquare$
NOTA: vale la pena aclarar que usamos que $a$ es coprimo cuando lo tomamos de $S$ y que el teorema no vale si $a$ no es coprimo con $m$. Un ejemplo sería ver $2^4$ módulo $8$.
Algo interesante es que el inverso de $a$ módulo $m$ es $a^{\varphi (m) -1}$ ya que $a\cdot a^{\varphi (m)-1}\equiv a^{\varphi (m)}\equiv 1\pmod{m}$.
"Though my eyes could see I still was a blind man"
Re: Teorema de Fermat-Euler
Este teorema es una generalización del Pequeño Teorema de Fermat, ya que si [math] es primo se tiene [math].
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
- Martín Vacas Vignolo
- Mensajes: 404
- Registrado: Mié 15 Dic, 2010 6:57 pm
- Nivel: Exolímpico
Re: Teorema de Fermat-Euler
http://omaforos.com.ar/viewtopic.php?f=7&t=1785Johanna escribió:Como calcularias [math] ?
[math]