Teorema de Fermat-Euler

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Teorema de Fermat-Euler

Mensaje sin leer por Nacho »

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}$.
1  
"Though my eyes could see I still was a blind man"
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Teorema de Fermat-Euler

Mensaje sin leer por Ivan »

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$)
Avatar de Usuario
Johanna

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2017 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 65
Registrado: Lun 22 Oct, 2012 9:38 pm
Medallas: 9
Nivel: Exolímpico

Re: Teorema de Fermat-Euler

Mensaje sin leer por Johanna »

Como calcularias [math] ?
Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

Re: Teorema de Fermat-Euler

Mensaje sin leer por Martín Vacas Vignolo »

Johanna escribió:Como calcularias [math] ?
http://omaforos.com.ar/viewtopic.php?f=7&t=1785
[math]
Responder