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 factores 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 es el segundo post de una serie de cinco 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.

2 comentarios

  1. Hi Marge!nAhhh…France…that’s our next trip, along with England. We’ll have to chat more about this move that you’re contemplating. If you’re ever out here, let me know! Click http://link.mx/hool08200

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

A %d blogueros les gusta esto: