Un antiguo Teorema Chino

_matteo_ricci_05

El Pequeño Teorema de Fermat establece que:

Si \displaystyle \mathit{\mathbf {p}} es un número primo, entonces para cada número \displaystyle \mathit{\mathbf {a}} el número  \displaystyle \mathit{\mathbf {a^p-a}}   es divisible en \displaystyle \mathit{\mathbf {p}} .

Para \displaystyle\mathit{\mathbf{a=2}}, el Pequeño Teorema de Fermat nos dice que la expresión \displaystyle\mathit{\mathbf{2^p-2}} es divisible en \displaystyle\mathit{\mathbf{p}} si \displaystyle\mathit{\mathbf{p}} es un número primo. Es natural, entonces, preguntarse si el recíproco de esta afirmación es válida tambien, o sea:

Si un númeto entero positivo \displaystyle \mathit{\mathbf {n>1}} divide la expresión \displaystyle \mathit{\mathbf {2^n-2}} ´¿es \displaystyle \mathit{\mathbf {n}}  un número primo?.

Hace 2500 años los chinos llegaron a la conclusión que la afirmación era válida, para ello chequearon infinidad de valores de \displaystyle \mathit{\mathbf {n}} y luego cálculos posteriores confirmaron que para  \displaystyle\mathit{\mathbf{1<n<300}} los únicos valores de \displaystyle\mathit{\mathbf{n}} que dividen la expresión  \displaystyle \mathit{\mathbf {2^n-2}}  son números primos.

No es difícil demostrar que este antiguo teorema chino es incorrecto. El número \displaystyle\mathit{\mathbf{n=341}} proporciona un contraejemplo. Al ser 341 el resultado de hacer 11  veces  31, el número 341 no es primo, pero divide la expresión \displaystyle \mathit{\mathbf {2^{341}-2}}. Esto último se puede demostrar fácilmente partiendo del hecho que toda expresión de la forma \displaystyle\mathit{\mathbf{x^m-y^m}} tiene como factor a \displaystyle\mathit{\mathbf{x-y}} para cualquier número positivo \displaystyle\mathit{\mathbf{m}}. Entonces tenemos que:

\displaystyle\mathit{\mathbf{2^{341}-2=2(2^{340}-1)}}

\displaystyle\mathit{\mathbf{2^{341}-2=2[(2^{10})^{34}-1^{34}]}}

\displaystyle\mathit{\mathbf{2^{341}-2=2[(2^{10}-1)(....)]}}

\displaystyle\mathit{\mathbf{2^{341}-2=2[(1023)(....)]}}

\displaystyle\mathit{\mathbf{2^{341}-2=2[3(341)(....)]}} entonces los números enteros \displaystyle\mathit{\mathbf{n}} como el 341, que no son números primos pero dividen la expresión \displaystyle \mathit{\mathbf {2^n-2}} se denominan “números pseudoprimos“.

Diversas preguntas respecto de los números pseudoprimos se pueden plantear: ¿es 341 el único número pseudoprimo?, ¿hay infinitos números pseudoprimos?. Resulta que para cada número pseudoprimo impar existe un número pseudoprimo impar mayor, por lo tanto a partir del 341 existen infinitos números pseudoprimos impares.

Otra pregunta que se deriva naturalmente del párrafo anterior es ¿existen números pseudoprimos pares?. En el año 1950 el americano D.H. Lehmer descubrió el número pseudoprimo par 161038 y si bien el descubrimiento en sí fue dificultoso es fácil demostrar que 161038 es un número pseudoprimo. Partimos del análisis de los facores primos que lo forman: 2 . 73 . 1103 y a partir de los mismos tenemos que:

\displaystyle\mathit{\mathbf{2^{161038}-2=2(2^{161037}-1)}}

Por lo tanto es necesario demostrar solamente que tanto el número 73 como el 1103 dividen a la expresión \displaystyle\mathit{\mathbf{(2^{161037}-1)}}.

(#) Comenzamos con en número 73, para ello descomponemos en sus factores primos a 161037 de la siguiente manera: \displaystyle\mathit{\mathbf{3^{2} . 29 . 617}} por lo tanto tenemos que:

\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{9})^{29617}-1^{29617}}}

\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{9}-1)(....)}}

\displaystyle\mathit{\mathbf{2^{161037}-1=(511)(....)}}

\displaystyle\mathit{\mathbf{2^{161037}-1=7(73)(....)}}

Así demostramos que la expresión \displaystyle\mathit{\mathbf{(2^{161037}-1)}} es divisible en 73.

(#) Análisis similar hacemos para el número 1103:

\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{29})^{9617}-1^{9617}}}

\displaystyle\mathit{\mathbf{2^{161037}-1=(2^{29}-1)(....)}}

\displaystyle\mathit{\mathbf{2^{161037}-1=1103(486737)(....)}}

También demostramos, entonces, que la expresión \displaystyle\mathit{\mathbf{(2^{161037}-1)}} es divisible en 1103.

Por lo tanto dado que 73 y 1103 son ambos números primos, que la divisibilidad de uno no afecta la devisibilidad del otro y a la vez ambos son divisores de la expresión \displaystyle\mathit{\mathbf{(2^{161037}-1)}}, entonces 161308 es un númeto pseudoprimo par.

En el año 1951 el holandés N.G.W. Beeger demostró que existen, también, infinitos números pseudoprimos pares.

Notas:

(1) Este es post es una traducción y resumen de parte del capitulo 1 del libro Mathematical Gems (ver referencia) y el segundo post de una serie de cinco posts a publicar sobre el tema.

Serie Teoría de Números:

Post N° 1:  El Pequeño Teorema de Fermat – Una demostración directa y simple.

(2) Número Pseudoprimo ( Pseudoprime ).

(3) Se pueden ver tablas de números pseudoprimos aquí.

Referencias:

 # Mathematical Gems I – Ross Honsberger – Mathematical Association of America – 1973 – (Colección: The Dolcialni Mathematical Expositions Vol. 1) – Chapter 1 – pp 3-4.

Maravilloso libro, lleno de gemas matemáticas como su título así lo indica. Todo lo que escribió Ross Honsberger es un placer de leer y trabajar al mismo tiempo. Casi todos sus libros estan colgados en alguna parte de internet y se puede acceder a ellos.

# Pseudoprime  – Wolfram Math World.

Blog: Division by Zero

Imagen

Este blog: Division by Zero es un blog de matemáticas, juegos matemáticos, educación matemática y tecnología educativa mantenido por el profesor Dave Richeson que es Profesor Asociado de Matemáticas en el Dickinson College y autor de Euler’s Gem: The Polyhedron Formula and the Birth of Topology publicado por Princeton University Press.

El blog tiene muchisima información y la calidad de los posts es excelente, con un inglés básico se pueden leer sin problemas. Muy destacable son los posts sobre el uso de programas y tecnologías en la educación matemática.

Se puede consultar la página personal del Prof. Richeson aquí y la página del libro aquí.

 

El Pequeño Teorema de Fermat – Una demostración directa y simple

Fermat

En una carta a Bernard Frenicle de Bessy in 1640, el gran teórico de los números francés Pierre de Fermat propuso el siguiente teorema (en realidad no era un teorema propiamente dicho sino más bien una conjetura):

Si \displaystyle \mathit{\mathbf {p}} es un número primo, entonces para cada número \displaystyle \mathit{\mathbf {a}} el número  \displaystyle \mathit{\mathbf {a^p-a}}   es divisible en \displaystyle \mathit{\mathbf {p}} .

Ejemplo: Tomamos \displaystyle p=23 un número primo, entonces \displaystyle a^p-a es divisible en \displaystyle p sea \displaystyle a un número entero cualquiera (positivo, negativo o cero).

Fermat sostenía que tenía una demostración del teorema, pero según le cuenta a Frenicle de Bessy, esta era demasiado extensa para incluirla en la carta. El primero en demostrar el teorema fue Gottfried Leibniz en un manuscrito en 1683 que no llegó a publicar. La primera demostración publicada, casi cien años después, es de Leonhard Euler, quien en 1736 la presentó en un artículo titulado Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio.

Hasta los inicios del siglo XX este teorema era conocido como “teorema de Fermat” , en 1913 el matemático Kurt Hensel en su libro Zahlentheorie lo rebautiza como “pequeño teorema de Fermat” tal como se conoce actualmente.

Si bien parace que demostrar este teorema requiere de una matemática avanzada, es sorprendente encontrar que puede demostrarse de manera sencilla y directa utilizando nada más que inducción matemática y el teorema del binomio.

A continuación el desarrollo la demostración:

(1) Sea \displaystyle p un número primo:

  • Si \displaystyle a=0 \longrightarrow \displaystyle 0^p-0=0 divisible en \displaystyle p
  • Si \displaystyle a=1 \longrightarrow \displaystyle 1^p-1=0 divisible en \displaystyle p

(2) Suponemos que si para todos los valores positivos de \displaystyle a tenemos que \displaystyle a^p-a es divisible en \displaystyle p por inducción matemática la hipótesis es válida también para \displaystyle a+1, entonces tenemos que:

  • \displaystyle a^p-a es divisible en \displaystyle p
  • \displaystyle (a+1)^p-(a+1) es divisible en \displaystyle p

Por Teorema del Binomio sabemos que:

\displaystyle (a+1)^p = a^p+ \binom{p}{1} a^{p-1}+ \binom{p}{2} a^{p-2}+...+\binom{p}{p-1} a+1

Hacemos pasaje de términos y obtenemos:

\displaystyle (a+1)^p-a^p-1 = \binom{p}{1} a^{p-1}+ \binom{p}{2} a^{p-2}+...+\binom{p}{p-1} a

\displaystyle (a+1)^p-(a^p+1) = \binom{p}{1} a^{p-1}+ \binom{p}{2} a^{p-2}+...+\binom{p}{p-1} a   (1)

En el lado derecho de la ecuación (1) encontramos que cada coeficiente \displaystyle \binom{p}{k} con \displaystyle k=1,2,3,...,p-1 es divisible en \displaystyle p. Por la propia definición de \displaystyle \binom{p}{k} tenemos que:

\displaystyle \binom{p}{k}k!=p(p-1)(p-2)...(p-k-1)  aquí \displaystyle p divide la parte derecha de la ecuación. Para todos los coeficientes de la expresión, \displaystyle k es un valor menor a \displaystyle p, entoces el factor primo \displaystyle p no ocurre en el producto \displaystyle k! , por lo tanto \displaystyle p divide a \displaystyle \binom{p}{k}.

Entonces como \displaystyle p divide a cada coeficiente del lado derecho de la ecuanción (1), debe dividir también a la expresión completa del lado derecho y consecuentemente divide también el lado izquierdo \displaystyle \longrightarrow (a+1)^p-(a^p+1).

A partir de la hipótesis inductiva que \displaystyle p divide a \displaystyle a^p-a, tenemos que:

  • \displaystyle [(a+1)^p-a^p-1]+[a^p-a] \displaystyle = \displaystyle (a+1)^p-\not{a^p} -1+\not{a^p} -a
  • \displaystyle [(a+1)^p-a^p-1]+[a^p-a] \displaystyle = \displaystyle \mathbf {(a+1)^p-(a+1)}

Por lo  tanto por inducción matemática la hipótesis es valida para todos los valores positivos de \displaystyle a.

(3) La demostración se completa considerando los valores negativos de \displaystyle a. Entonces definimos a los valores negativos de \displaystyle a como  \displaystyle\mathbf {-a}.

- Si \displaystyle p es igual a \displaystyle 2 , tenemos que:

\displaystyle (-a)^p-(-a)=(-a)^p+a=a^2+a=\mathbf{a(a+1)}

Los factores \displaystyle\mathbf {a} y \displaystyle\mathbf {(a+1)} son consecutivos, entonces uno de ellos es par y su producto divisible en \displaystyle 2.

- Si \displaystyle p es impar:

\displaystyle (-a)^p-(-a)=-a^p+a=\mathbf{-(a^p-a)}

Sabemos que si \displaystyle a es positivo divide a \displaystyle (a^p-a), por lo tanto tambien divide a \displaystyle -(a^p-a).

\displaystyle \mathbf{Q.E.D} (quod erat demonstrandum).

Notas:

(1) Este post es una traducción y resumen de parte del capitulo 1 del libro Mathematical Gems (ver referencia) y forma parte de una serie de cinco posts a publicar sobre el tema.

(2) El Pequeño Teorema de Fermat se puede enunciar de diferentes maneras:

  • Si \displaystyle p es un número primo, entonces \displaystyle p divide a \displaystyle a^{p-1}-1 para cada número entero \displaystyle a coprimo con \displaystyle p.
  • Si \displaystyle p es un número primo, entonces, para cada número natural \displaystyle a, \displaystyle a^p \equiv a (mod \displaystyle p).
  • Si \displaystyle p es un número primo, entonces, para cada número natural \displaystyle a coprimo con \displaystyle p, \displaystyle a^{p-1} \equiv 1 (mod \displaystyle p).

(3) Se dice que dos números \displaystyle\mathbf a y \displaystyle\mathbf b son números primos entre sí ( coprimoscoprime – o primos relativosrelatively prime – ), si no tienen ningún factor primo en común, o sea no tienen otro divisor común más que 1 o -1.

(4) En un post anterior “Números Primos: Una fórmula para generarlos” explicamos como utilizar el pequeño teorema de Fermat como test de primalidad, o sea un test para definir si un determinado número es primo o compuesto.

 Referencias:

 # Mathematical Gems I – Ross Honsberger – Mathematical Association of America – 1973 – (Colección: The Dolcialni Mathematical Expositions Vol. 1) – Chapter 1 – pp 1-3.

Maravilloso libro, lleno de gemas matemáticas como su título así lo indica. Todo lo que escribió Ross Honsberger es un placer de leer y trabajar al mismo tiempo. Casi todos sus libros estan colgados en alguna parte de internet y se puede acceder a ellos.

# Pequeño Teorema de Fermat – Wikipedia (consultado 07/05/2014).

# Fermat´s Little Theorem  – Wolfram Math World.

 

 

 

Matemática para Todos

9789500740395

Matemática para Todos es el título del nuevo libro de Adrián Paenza (editado por Sudamericana), hoy me lo encontré en la librería y no resistí la tentación de comprarmelo. Como con todos sus libros anteriores Paenza lo colgó en la web en formato pdf y se puede bajar desde aquí. Seguramente se venderá como pan caliente. Una prueba contundente de que al hacerlo disponible en la web no necesariamente implica que el libro no se venda.

Introducción al Pensamieto Matemático

Imagen

La próxima semana arranca en Coursera un curso de siete semanas denominado Introduction to Mathematical Tinking dictado por profesor de la Stanford University, Keith Devlin. Otorgan un Certificado por haber completado el curso. Es una oportunidad espectacular para acceder a material de primer nivel de una universidad top en una plataforma de educación online genial como es Coursera.

Les paso un par de links de weblogs del profesor Devlin con muchísima y jugosa información:

Devlin’s Angle

profkeithdevlin

Teselaciones: Lecturas Recomendadas

images

Uno de los posts más leídos de este blog es uno que escribí sobre Teselaciones, hay mucho material sobre el tema en la web, pero los siguientes artículos son excelentes para profundizar en el tema, aquí van:

# Teselaciones – Federico Ardila y Richard Stanley.

Artículo muy completo sobre el tema de Teselaciones, el artículo está basado en una presentación que hicieron los autores en la Clay Public Lecture en Julio 2004. Se puede bajar desde aquí. El mismo artículo luego publicado en inglés en el número de Diciembre 2010 de la Mathematical Intelligencer se puede consultar aquí.

# The Fascination of Tiling – Doris Schattschneider – Leonardo Vol 25 N° 2/3 pp 341-348 1992.

Excelente artículo de una matemática especialista en el tema y en la obra de M.C. Escher. Un pantallaso general del tema, con numerosos ejemplos. Artículo muy bien escrito que con un inglés básico se lee de corrido. Se puede bajar desde aquí.

# Tiling Rectangles with Polyominoes – Solomon Golomb – Mathematical Intelligencer Vol 18 N° 2 pp 38-47 1996.

El matemático Salomon Golomb fue de alguna forma el creador de los poliminos o poliominos, en este artículo analiza las diferentes variantes que surgen al querer teselar o cubrir el plano (un rectágulo) con poliominos de la manera más eficiente posible, o sea con el mínimo número posible de un n-poliomino dado. El artículo está escrito en un inglés no muy técnico y es fácil de seguir. Se puede bajar desde aquí.

# Mosaicos de Polígonos Convexos – Martin Gardner – Viajes por el Tiempo y Otras Perplejidades Matemáticas – Capítulo 12.

Como no podía ser de otra manera, el genio divulgativo de Martin Gardner trató el tema de las teselaciones extensamente, el capítulo 12 del libro mencionado es de lo más detallado y completo sobre como teselar el plano con figuras convexas. En la versión en inglés del libro,Time Travel and Other Mathematical Bewilderments, se puede consultar el capítulo mencionado aquí.

# In Praise of Amateurs – Doris Schattschneider – Mathematical Recreations: A Collection in Honor of Martin Gardner – pp 140-170.

En su columna Mathematical Games de la revista Scientific American de Julio de  1975 (On Tesseling the Plane with Convex Polygon Tiles), Martin Gardner despierta el interés de una ama de casa llamada Marjorie Rice, que sin ninguna educación adicional a la escuela secundaria, hace una serie de descubrimientos sobre las configuraciones posibles de figuras convexas que teselan el plano. La historia está magníficamente relatada en este artículo de Doris Schattschneider. Se se puede leer con un inglés elemental aquí.

BON APPETIT

Rasguños y Gruñidos

Cuentan las leyendas homéricas que cuando Ulises (Ulysses) deja la tierra de los Cíclopes (Cyclopes), luego de pelear y vencer al monstruo de un solo ojo Polifemo (Polyphemus), el enceguecido gigante se sentaba cada mañana a la entrada de su cueva y de un alto de piedras, tomaba de una por cada oveja que salía a pastar. Al terminar el día, cuando las ovejas regresaban, dejaba caer una piedra por cada oveja que ingresaba a la cueva. De esta manera, agotando las piedras recogidas en la mañana, el gigante se aseguraba que todo su rebaño retornaba sano y salvo.

La historia de Polifemo es una de las referencias más antiguas de la noción de correspondencia uno a uno como base de la operación de contar. La correspondencia entre los objetos pertenecientes a dos o más conjuntos de objetos es uno de los aspectos básicos del proceso de contar: a cada oveja le corresponde una piedra y a cada piedra una oveja. Dicho de otra manera, se plantea una correspondencia biunívoca entre los objetos que forman los conjuntos de ovejas y de piedras.

El artefacto más antiguo, descubierto hasta ahora, utilizado para llevar registros de conteos es el Hueso de Ishango, encontrado por Jean de Heinzelin en 1962 en un sitio de pesca a las orillas del Lago Edward en la República Democrática del Congo, y data de un período entre el 9000 y 6500 A.C. Este hueso contiene pequeñas muescas o rasguños que registran, según se cree, algún tipo de conteo de objetos o animales.

Es muy probable que el primer y más temprano gran momento de las matemáticas ocurrió cuando, hace miles de años, el hombre primitivo comenzó a llevar cuentas o conteos, haciendo marcas en la tierra o rasguños en huesos. La sociedad ha evolucionado desde entonces, al punto que la simple acción de contar se ha vuelto imprescindible. Una tribu, un clan, una familia tenían que distribuir comida entre sus miembros o saber el tamaño de sus rebaños. El proceso de desarrollar un método de conteo y la necesidad de llevar un registro del mismo, empleando el principio matemático de correspondencia uno a uno, marcó probablemente el inicio de la escritura.

Es razonable suponer, que para mantener la cuenta de pequeñas cantidades o colecciones de objetos se utilizaran los dedos de la mano. Quizas luego se desarrollaron gruñidos o sonidos vocales para identificar determinados conteos y así finalmente llegar a los símbolos escritos que evolucionaron a los números como los conocemos hoy.

Toda esta teoría del desarrollo de la habilidad de contar es conjetural, se basa en reportes de antropólogos, de sus estudios en comunidades primitivas actuales y en artefactos desenterrados en diversas partes del mundo. También es la forma en que los niños aprenden a contar. La noción de correspondencia uno a uno, hace mucho tiempo está establecida como la base para contar coleeciones finitas de objetos. En una extraordinaria serie de artículos publicados a partir de 1874, en su mayor parte en las revistas matemáticas Mathematische Annalen y en el Journal für Mathematik, el matemático alemán Georg Cantor aplicó el mismo principio básico de conteo para contar colecciones infinitas, creando así la teoría de los números transfinitos. Pero esa es otra historia.

Referencias:

Este post es una adaptación, resumen y traducción de la Lecture 1 de: # Great Moments in Mathematics before 1650 – Howard Eves – MAA Dolciani Mathematical Expositions N° 5 – 1983 (diponible para consulta en Google Books aquí).

Bibliografía adicional para consultar:

- Numbers Words and Number Symbols, a Cultural History of Numbers – Menninger Karl – MIT – 1969.

- Africa Counts, Numbers and Patterns in Africa Culture – Zaslavsky Claudia – Weber & Smith – 1973.

- African Mathematics: From Bones to Computers – Bangura Abdul, Setati Mamokgethi – University Press of America – 2012 (diponible para consulta en Google Books aquí).

La Partícula de Dios

En el laboratorio de física de partículas CERN, científicos descubrieron o mejor dicho confirmaron la existencia de la partícula llamada “Boson de Higgs” y que para vender períodicos y justificar gastos millonarios algunos denominaron “partícula de Dios”. La búsqueda de esta especie de eslabón perdido de la Teoría Standard de Partículas Elementales llevaba ya varios años y la confirmación de su existencia termina de dar consistencia a dicha teoría. The Economist, publica hoy un gráfico excelente que sitúa en contexto este descubrimiento:

Imagen

Para tener una idea completa de todo esto recomiendo chequear aquí.

Cancelaciones

Cancelando a lo bestia, pero con resultados correctos:

 

\displaystyle \frac{19}{95}=\frac{1\not9}{\not95}=\frac{1}{5}

\displaystyle \frac{3544}{7531}=\frac{3\not544}{7\not5 31}=\frac{344}{731}

\displaystyle \frac{2666}{6665}=\frac{2 \not6 66}{6 \not665}=\frac{266}{665}=\frac{2 \not6 6}{6 \not6 5}=\frac{26}{65}=\frac{2 \not6}{\not65}=\frac{2}{5}

\displaystyle \frac{143185}{17018560}=\frac{143 \not1\not85}{170 \not1\not8560}=\frac{1435}{170560}

Las Matemáticas de Martin Gardner

La Mathematical Association of America tuvo la genial idea de dedicar el número completo de Enero 2012 del College Mathematical Journal, a las matemáticas que Martin Gardner difundió como pocos a través de su columna mensual Juegos Matemáticos (Mathematical Games) que durante poco más de 54 años publicó en la revista Scientific American.

Lo mejor de todo es que este número especial dedicado a Martin Gardner es accesible gratis desde aquí. ¡¡¡A disfrutar!!!

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 28 seguidores