(MT:AL) Teorema de Fermat

Título: Teorema de Fermat
Autor: luis esc

Hilo original: http://foro.migui.com/smf/index.php/topic,9876.0.html

Lema 1.

Sea $p$ un número natural primo fijo.

$\forall m \in \mathbb{N}$ , la implicación siguiente es cierta:

$0<m<p$ implica que $p \mid \binom{p}{m}$ .

Demostración:

-Primera manera.Gracias a Púrpura.

Tenemos que $\binom{p}{m} = \dfrac{p!}{(p-m)! m!}$ , por lo tanto,

$\binom{p}{m} (p-m)! m! = p!$ .

Claramente, $p$ divide a $p!$ por lo que:

$p$ ha de dividir a $\binom{p}{m} (p-m)! m!$ .

Como $p$ es un número primo, por definición de número primo, si se tiene que $p \mid ab$ entonces necesariamente $p \mid a$ o $p \mid b$ .

En nuestro caso, como $p \mid \binom{p}{m} (p-m)! m!$ , entonces:

$p \mid \binom{p}{m}$ o $p \mid (p-m)!$ o $p \mid m!$ .

Como $p-m;m<p$ se sigue que $p$ no divide ni a $m!$ ni a $(p-m)!$ .

Por lo que entonces:

$p \mid \binom{p}{m}$ .

-Segunda manera.

Procedemos por el método de inducción matemática sobre $m$ .

Si $m=1$ , entonces $\binom{p}{m}=p$ luego efectivamente $p \mid \binom{p}{m}$ .

Asumamos la hipótesis de inducción, es decir, $p \mid \binom{p}{m}$ y sea $m+1<p$ .

Veámos que $p \mid \binom{p}{m+1}$ .

Tenemos:

$\binom{p}{m+1}=\dfrac{p!}{(m+1)! (p-m-1)!}=\dfrac{p-m}{m+1} \dfrac{p!}{m! (p-m)!}=\dfrac{p-m}{m+1} \binom{p}{m}$ .

Así pues, por hipótesis de inducción, sabemos que $p \mid (p-m) \binom{p}{m}$ y como $(m+1,p)=1$ , entonces la divisibilidad se conserva al dividir entre $m+1$ , es decir, finalmente tenemos que $p \mid \binom{p}{m+1}$ .

$Q.E.D.$

Bien, lo que no acabo de entender es aquello de que "como $(m+1,p)=1$ , entonces la divisibilidad se conserva al dividir entre $m+1$ ".

Yo sé por hipótesis de inducción que $(p-m) \binom{p}{m}$ es un múltiplo de $p$ .
Además, los coeficientes binomiales son siempre números naturales, entonces, ¿por qué es necesario asumir que $(m+1,p)=1$ ?

A ver, yo pienso lo siguiente.
Como $(p-m) \binom{p}{m}$ es un múltiplo de $p$ , entonces $(p-m) \binom{p}{m} = kp$ , para cierto natural $k$ .
El hecho de que los números $m+1,p$ sean coprimos, nos asegura que, para que el coeficiente binomial $\binom{p}{m+1}$ sea un número natural, $m+1$ tenga que dividir al número $k$ , ya que $m+1$ no puede dividir a $p$ , ya que estos dos números son coprimos y por tanto el divisor mas grande común es justo el $1$ y esta claro que $m+1 \neq 1$ ya que $m>0$ . Por tanto $m+1$ ha de dividir a $k$ y no a $p$ .
Así, nos aseguramos que el coeficiente binomial $\binom{p}{m+1}$ sea efectivamente un múltiplo de $p$ que era lo que buscábamos.

Lema 2.

Sea $p$ un número natural primo.
Entonces, $\forall n \in \mathbb{N} : p \mid n^p - n$ .

Demostración:

De nuevo, procedemos por el método de inducción matemática sobre $n$ .

Para $n=1$ , tenemos que $1^p - 1 = 0$ , luego efectivamente $p \mid n^p - n$ .

Asumamos la hipótesis de inducción, es decir, que $p \mid n^p - n$ .

Probemos que $p \mid (n+1)^p - (n+1)$ .

$\dfrac{(n+1)^p - (n+1)}{p}=\dfrac{n^p - n + \sum_{k=1}^{p-1} \binom{p}{k} n^{p-k}}{p} = \dfrac{n^p - n}{p} + \dfrac{\sum_{k=1}^{p-1} \binom{p}{k} n^{p-k}}{p} = t + s \in \mathbb{Z}$ .

Para ciertos enteros $t,s$ ; donde en la última igualdad he usado la hipótesis de inducción y el Lema 1.

$Q.E.D.$

Teorema.Fermat.

Si $p$ es un número primo, entonces, para cada número natural $n$ coprimo con $p$ , se tiene que $n^{p-1} \equiv 1 ; mod(p)$ .

Demostración:

Usando el Lema 2, sabemos que $n^p - n=\dot{p}$ .

Sacando factor común $n$ tenemos que,

$n( n^{p-1} - 1 ) = \dot{p}$ .

Ahora, tomamos clases de equivalencia módulo $p$ .

$[n( n^{p-1} - 1 )] = [\dot{p}]$ y además $[\dot{p}]$ es nulo por ser $\dot{p}$ múltiplo de $p$ , es decir,

$[n][ n^{p-1} - 1 ] = 0$ .

Hay que tener en cuenta que, como $p$ es un número primo, entonces $\mathbb{Z}_p$ es cuerpo, luego en particular es dominio de integridad, por lo tanto, no hay divisores de cero.

Luego, si $[n][ n^{p-1} - 1 ] = 0$ , entonces,

o bien $[n]=0$ o bien $[ n^{p-1} - 1 ]=0$ .

Si queremos que $[n]$ sea distinto de $0$ , entonces debemos imponer que $n$ no sea múltiplo de $p$ . Entonces, podemos imponer que $(n,p)=1$ .

En este caso, tenemos lo que queríamos, que $[n]$ sea distinto de $0$ , y por lo tanto debe ser $[ n^{p-1} - 1 ] = 0$ .

Así pues,

$[n^{p-1}] - [1] = 0$ ,

$[n^{p-1}] = [1]$ ,

de donde se obtiene finalmente que:

$n^{p-1} \equiv 1;mod(p)$ .

$Q.E.D.$

Notar que si no hubiésemos impuesto que $(n,p)=1$ , entonces, tomando por ejemplo $n=p=3$ tendríamos que el teorema no se cumpliría.