Pequeño Teorema de Fermat (Fermatito)

Avatar de Usuario
Ivan

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

Pequeño Teorema de Fermat (Fermatito)

Mensaje sin leer por Ivan » Vie 15 Oct, 2010 7:45 pm

Pequeño Teorema de Fermat:
Si [math] es primo y [math] es un entero entonces [math]. En otras palabras, [math] es múltiplo de [math].
1  
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)

Daniel
Mensajes: 2
Registrado: Mié 24 Nov, 2010 7:05 pm

Re: Fermatito

Mensaje sin leer por Daniel » Mié 24 Nov, 2010 7:23 pm

Consideremos primero el caso en que [math] no es múltiplo de [math]. Consideremos el conjunto de números
[math]. Por otra parte consideremos el conjunto de números [math]. (A los conjuntos los miramos módulo [math], es decir, solo nos importa el resto de los números en la división por [math]). Es claro que los números del segundo conjunto son [math] números, ninguno divisible por [math], pues [math] no lo era. Veamos que son todos distintos. Si [math] con [math] entonces [math] y dado que [math] es coprimo con [math] tenemos que [math]. Si nos fijamos el rango de [math] concluimos que [math]. Esto nos dice que los números del segundo conjunto son todos distintos módulo [math], deben ser, en algún orden, exactamente los números del primer conjunto.
Ahora la idea va a ser multiplicar los números de cada conjunto, como son iguales los conjuntos, tenemos que:
[math]
Reagrupando los términos de manera amigable, nos queda que
[math] y como claramente [math] es coprimo con [math] podemos "cancelarlo" en la congruencia. Luego nos queda que [math]. Si multiplicamos la congruencia por [math] a ambos lados nos queda lo que queríamos.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 607
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Pequeño Teorema de Fermat (Fermatito)

Mensaje sin leer por Gianni De Rico » Dom 24 Jun, 2018 10:39 pm

Dejo otra casi sin usar congruencias
Spoiler: mostrar
Si $p\mid a$ entonces $p\mid a^p-a$ y estamos
Si $p\not \mid a$ lo probamos por inducción en $a$ para $a\in \mathbb{N}$
El caso base $a=1$ es cierto pues $1^p-1=0$ y $p\mid 0\forall p$
Como hipótesis inductiva supongamos que vale para $a=n$, veamos que vale para $n+1$
Por el Binomio de Newton tenemos
$(n+1)^p=\sum \limits_{k=0}^p \binom{p}{k}n^{p-k}=\binom{p}{0}n^{p-0}+\binom{p}{p}n^{p-p}+\sum \limits_{k=1}^{p-1}\binom{p}{k}n^{p-k}=n^p+1+\sum \limits_{k=1}^{p-1}\binom{p}{k}n^{p-k}$
Luego $(n+1)^p-(n+1)=n^p-n+\sum \limits_{k=1}^{p-1}\binom{p}{k}n^{p-k}$
Por HI tenemos que $p\mid n^p-n$, entonces si probamos que $p\mid \sum \limits_{k=1}^{p-1}\binom{p}{k}n^{p-k}$ tendremos que $p\mid (n+1)^p-(n+1)$ y la inducción estará completa

Con esta fórmula se ve que si $\binom{t-1}{r-1}$ y $\binom{t-1}{r}$ son enteros entonces $\binom{t}{r}$ es entero $\forall 0<r<t$, y se verifica a mano que es cierto para los primeros casos. Por inducción en $t$, obtenemos que $\binom{t}{r}$ es entero $\forall 0<r<t$
Como $\binom{p}{r}=\frac{p!}{(p-r)!r!}$ tenemos $(p-r)!r!\mid p!$, como $0<r<p$ entonces $0<p-r<p$ y $(p-r)!r!\not \mid p$ ya que es primo. Por lo tanto $(p-r)!r!\mid (p-1)!\Rightarrow p\mid \binom{p}{r}\forall 0<r<p$
Entonces $p\mid \sum \limits_{k=1}^{p-1}\binom{p}{k}n^{p-k}$
$\therefore p\mid a^p-a\forall a\in \mathbb{N}$

Si $a$ es negativo lo escribimos como $-x$ siendo $x$ positivo, queremos ver $(-x)^p\equiv -x(p)$, si $p=2$ tenemos $m^2\equiv m(2)\forall m\in \mathbb{Z}$, si $p\neq 2$ entonces $p$ es impar, luego $(-x)^p=-x^p$ por lo que queremos ver que $-x^p\equiv -x(p)$, pero esto es una consecuencia inmediata de multiplicar por $-1$ el resultado obtenido para $a\in \mathbb{N}$
[math]

Responder