El pequeño teorema de Fermat

El pequeño teorema de Fermat, es un teorema afirmado por el aficionado en matemáticas Pierre de Fermat, relacionado con divisibilidad y números primos. Los chinos conocían en los años 500 que p|(2^p-2) para cada p primo. En una carta enviado a Frenicle de Bessy en 1640, Fermat afirmó tener una prueba de un resultado más general:

Si p es un número primo y a es cualquier entero que no tiene como factor a p, entonces p es un factor de a^{p-1}-1.

Pero como era costumbre, Fermat no incluía la demostración, torturando así a sus interlocutores. Por ejemplo, si p=3 y a=23, entonces 3|(23^{3-1}-1)=528, lo cual es cierto trivialmente. En 1676, Leibniz vio que \forall n\in\mathbb{N}

n^2-n\equiv n(n+1)\equiv{0}\mod{2}

n^3-n\equiv n(n+1)(n+2)\equiv{0}\mod{3}

y de manera similar para 5 y para 7; pero que el resultado correspondiente no es cierto para 9, por ejemplo con n=2.

Leonhard Euler fue el primero en publicar una prueba del pequeño teorema de Fermat, la presentó el 2 de agosto de 1736 ante la Academia de San Petersburgo.

Utilizando el hecho que p|\binom{n}{k} para toda 1\le k\le p-1. Euler demostró el siguiente

Teorema 1. (a+1)^p-(a+1)\equiv {a^p-a}\mod{p}

Lo que se prueba lo siguiente:

Teorema 2. Si p es un número primo y a cualquier entero, entonces p es un factor de a^p-a.

Demostración: Inducimos sobre a. Para a=1 la afirmación es cierta. Suponemos el resultado para k\leq a, es decir, que p|(a^p-a). Por el teorema 1 y la hipótesis de inducción se tiene que:

p|[[(a+1)^p-(a+1)]-(a^p-a)]\equiv (a+1)^p-(a+1)

lo que completa la inducción.

Así, Euler concluye el teorema de Fermat

Teorema 3. Si p es un número primo y a cualquier entero que no tiene como factor a p, entonces p es un factor de a^{p-1}-1.

Demostración: Dado que p|(a^{p}-a)=a(a^{p-1}-1) y no es factor de a, entonces necesariamente p es un factor de a^{p-1}-1.

El trabajo de Euler en relación al Pequeño Teorema de Fermat no se concretó en dar varias demostraciones del mismo, sino que lo generalizaría haciendo uso de la hoy conocida función phi de Euler \phi(^.), cuyo valor en el entero a 1 se define por

\phi(a) := \#\{1 \le m \le a | mcd(a,m) = 1\},

El siguiente resultado lo presentó Euler ante la Academia de St. Petersburgo el 15 de Octubre de 1759 :

Teorema 4. Para cada entero a\ge 1,

\phi(a) = \displaystyle\prod_{p^{\alpha}|a}^{}p^{\alpha-1}(p-1)

Demostración: Para los números primos p, tenemos

\phi(p) =p-1

Si m=p^{\alpha}, entonces los números que tiene un factor común con m son los múltiplos de p: p, 2p,\cdots,p^{\alpha-1}p. Hay p^{\alpha-1} de estos múltiplos, así el número de enteros positivos primos relativos a p^{\alpha} es

\phi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}=p^{\alpha-1}(p-1)

 Por otra parte, si p y q son primos distintos, tenemos que \phi(pq)=\phi(p)\phi(q). En efecto, los números que tiene un factor en común con pq son los múltiplos de p: p, 2p, …, qp, y los múltiplos de q: q, 2q, … , pq. Es decir, el número de enteros positivos que tienen un factor común con pq es p+q-1, luego

\phi(pq)=pq-p-q+1=(p-1)(q-1)=\phi(p)\phi(q).

Por inducción en \alpha y \beta puede demostrarse que \phi(p^{\alpha}q^{\beta})=\phi(p^{\alpha})\phi(q^{\beta}). Por inducción sobre el número de factores primos de a se obtiene el resultado.

Este mismo año, Euler presenta el siguiente

Teorema 5. Para todos los enteros a\geq 1n tales que mcd(a, n)=1, se tiene que

a^{\phi(n)}\equiv 1 \pmod{n}

Demostración: Sean a_1, a_2, ... , a_{\phi(n)} todos los enteros positivos menores que n y primos relativos con n. Como mcd(a,n)=1, entonces cada elemento del conjunto \{aa_1, aa_2, ..., aa_{\phi(n)}\} es congruente módulo n con uno y solo uno del conjunto \{a_1, a_2, ..., a_{\phi(n)}\}. Tomando el producto de estas congruencias se tiene

aa_1aa_2\cdots aa_{\phi(n)}\equiv a_1a_2\cdots a_{\phi(n)} \pmod{n}

por tanto tenemos

a^{\phi(n)}a_1a_2\cdots a_{\phi(n)}\equiv a_1a_2\cdots a_{\phi(n)} \pmod{n}

Como mcd(a_1a_2\cdots a_{\phi(n)},\,n)=1, podemos dividir ambos lados por a_1a_2\cdots a_{\phi(n)}. Con lo que nos da el siguiente resultado

a^{\phi(n)}\equiv 1 \pmod{n}


NOTA: La notación \phi(.), así como la noción de congruencia módulo p se deben a Gauss,  quien las introduce en 1801 en la primera edición de “Disquisitiones arithmeticae”.

Anuncios
Esta entrada fue publicada en Números Primos, Teoría de Números, Teoremas y etiquetada , . Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s