Pequeña demostración del pequeño teorema de Fermat

Pierre de fermatFoto tomada de: http://www-groups.dcs.st-and.ac.uk/~history/PictDisplay/Fermat.html

El famosísimo Pequeño teorema de Fermat cuenta con varias demostraciones, muchas cortas, como pueden verlas en la Wikipedia en inglés. Hoy daremos una demostración basada en combinatoria.

Empezaremos con una definición para entrar en contexto.

Permutación Cíclica. Dada una cadena de símbolos, una permutación es en la cual se toma el primer elemento de la lista y se coloca de último. Por ejemplo, si tenemos la lista

SELBERG

Una permutación cíclica es

ELBERGS

En la cual tomé el primer elemento S y lo coloqué al final. Puedo también pasar de a dos o más elementos al final, de esta forma

\underline{SE}LBERG\to LBERG\underline{SE}

\underline{SEL}BERG\to BERG\underline{SEL}

\underline{SELBE}RG\to RG\underline{SELBE}.

Necesitaremos el siguiente resultado

Lema. Si \omega es una cadena arbitraria de símbolos de longitud p, p un número primo, además, \omega no se compone de un solo símbolo repetido p veces, entonces todas las permutaciones cíclicas de \omega son distintas.


Demostración. Sean a_1a_2, …, a_p, p símbolos. Supongamos que omega se escribe de esta forma

\omega=a_1a_2\cdots a_p.

Sea \varepsilon la siguiente permutación cíclica

\varepsilon=a_{2} a_{3}\cdots a_p a_1.

En la cual solo se ha colocado el primer elemento al final. Supongamos que \omega=\varepsilon, entonces

a_1 a_2 \cdots a_{p-1}a_p

=a_2 a_3\cdots a_p a_1

En otras palabras a_1=a_2a_2=a_3,…, a_{p-1}=a_pa_p=a_1, escrito de otra forma

a_1=a_2=a_3=\cdots=a_{p-1}=a_p=a_1.

Es decir: \omega=a_1a_1a_1\cdots a_1 contradiciendo las hipótesis del teorema, en la cual indica que no es la repetición de un solo símbolo.

Supongamos ahora que \varepsilon=a_3a_4\cdots a_{p-1}a_pa_1a_2 y que \omega=\varepsilon. Entonces

\underline{a_1 a_2}\,\,\underline{a_3 a_4}\cdots \underline{a_{p-3}a_{p-2}}\,\,\underline{a_{p-1}a_p}

=\underline{a_3a_4}\,\,\underline{a_5a_6}\cdots \underline{a_{p-1}a_p}\,\,\underline{a_1a_2}

Si miramos el final, vemos que la sub-cadena a_1a_2 es igual a la subcadena a_{p-1}a_p. Si miramos el incio, la sub-cadena a_1a_2 es a su vez es igual a a_{3}a_{4}, y dado que a_{3}a_4 es igual a a_5a_6, entonces a_1a_2 es igual a a_5a_6 y así sucesivamente. Llegando a que

\omega=\underline{a_1 a_2}\,\,\underline{a_1 a_2}\,\,\cdots \underline{a_1 a_2}\,\,\underline{a_1 a_2}.

Esto indica que la cadena de p símbolos se puede dividir en sub-cadenas de dos símbolos, es decir que 2|p, pero dado que p es un número primo, tenemos que p=2, concluyendo que \omega=a_1a_2 y deduciendo que \varepsilon es la permutación en la cual no se mueve ningún símbolo. Siguiendo este procedimiento con cualquier permutación cíclica, vemos que se debería dar que

\omega=\underline{a_1 \cdots a_k}\,\,\underline{a_1 \cdots a_k}\,\,\cdots \underline{a_1 \cdots a_k}\,\,\underline{a_1 \cdots a_k}.

Concluyendo que k|p, es decir k=p, y finalizando con que \varepsilon es la permutación en la cual no se mueve ningún simbolo.


Con este pequeño lema (cuya demostración parece ser larga pero es solo que me adentré en detalles), podremos demostrar el pequeño teorema de Fermat en pocas líneas.

Teorema. Si a y p son enteros positivos, con p un número primo, entonces

a^{p}\equiv a \mod p.


Demostración. Sea A=\{s_1,s_2,\dots,s_a\} un conjunto arbitrario de símbolos. Formemos todas las posibles cadenas de p elementos del conjunto A. Entonces hay a^p cadenas. Quitemos las cadenas que se conforman de un solo símbolos (por ejemplo la cadena r_1 r_1\cdots r_1 o la cadena r_2 r_2\cdots r_2 y así). Hay a cadenas de este estilo, si las quitamos obtenemos a^p-a. Cada una des estas cadenas tiene longitud p, por el lema que hemos demostrado, tienen p distintas permutaciones cíclicas, todas distintas. Dividamos todas las cadenas en conjuntos, en los cuales, si tomamos un par de elementos en un mismo conjunto, un elemento es la permutación cíclica del otro y viceversa. Entonces, en virtud del primer lema, cada conjunto tiene p elementos. Además, todos los conjuntos son disyuntos, pues si un elemento pertenece a dos conjuntos U_1 y U_2, entonces dichos conjuntos serán el mismo. Supongamos que hay k conjuntos, entonces a^p-a=kp, luego

a^{p}\equiv a \mod p.


Esta demostración es dada a Stephen Kennedy. Existe otra demostración, dada por S. W. Colomb. En las referencias se encuentran un enlace a ambos artículos.


Referencias

  • 78.1 A (Very) Short Proof of Fermat’s Little Theorem, Stephen P. Kennedy, The Mathematical Gazette, Vol. 78, No. 481 (Mar., 1994), p. 48. [URL]
  • Weisstein, Eric W. “Cyclic Permutation.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/CyclicPermutation.html
  • Combinatorial Proof of Fermat’s “Little” Theorem, S. W. Golomb, The American Mathematical Monthly, Vol. 63, No. 10, (Dec., 1956), pp. 718. [URL]

1 Comentario en "Pequeña demostración del pequeño teorema de Fermat"

  1. DANKE! Endlich mal eine SUPER Anleitung zum Anfeuern. Als Neuling war es leider gar nicht so einfach. Zum Räuchern selbst gibt es so viel zu lesen, im Internet oder auch in Büchern. Aber wie man den Ofen richtig auf Hitze bringt, wird nirgends richtig beschrieben. Wir werden es heute nach Deiner Beschreibung ausprobieren.

Deja un comentario.

Tu dirección de correo no será publicada.

*


A %d blogueros les gusta esto: