Números Primos: Una fórmula para generarlos.

Sabido es que los números primos (números enteros solo divisibles en sí mismos y en la unidad) son los ladrillos  que forman al edificio matemático, lo que se manifiesta claramente en el El Teorema Fundamental de la Aritmética : todo número positivo se puede descomponer, de forma única, en su factores primos. Dada la importancia de los números primos, cabe la siguiente pregunta:

¿Existe alguna fórmula o procedimiento que permita obtener números primos?

Sí!!!, aunque sea  increíble, existe una  fórmula mediante la cual podemos obtener todos los números primos que querramos. Hmmm!!! … quiero ver:

Sean dos números cualquiera y , calculamos lo siguiente:

y luego:

Cualquiera sea el valor de y , el valor de que se obtenga de la última fórmula será siempre primo. Asimismo, cada número primo será un valor de para algún par de valores de y . Esta fórmula, créase o no, genera todos los números primos. Es fácil armar una planilla de cálculo excel con una lista de números primos generados de esta manera. Hasta aquí con este post ya tengo ganada la inmortalidad matemática.

Por desgracia para mi hambre de gloria, la realidad es que para la mayor parte de los valores de y encontramos que . Con un poco de paciencia otros números primos van apareciendo. Por ejemplo para y obtenemos ; para y resulta ; si y  obtenemos . Para obtener , hay que ser muy pero muy paciente, dado que no aparece hasta tratar con y .

Parece claro a esta altura, que esta forma de generar números primos no es muy eficiente que digamos, dado que  casi siempre el resultado de aplicar estas fórmulas será (si alguien se anima, que por favor me pase los valores de y para ). Quizás lo más importante de esta fórmula sea demostrar que los números primos son capaces de ser generados u obtenidos a partir de una fórmula, no obstante de manera ineficiente.

Es muy importante formular métodos eficientes para testear si cualquier número dado es o no un número primo. El método más simple y obvio es, dado un número, analizar los números más pequeños y chequear si éstos dividen exactamente o no al número bajo análisis (excepto el 1, que divide a todos), este tipo de test elemental se puede efectuar perfectamente con una PC mientras el número involucrado no sea muy grande, pero se vuelve totalmente ineficiente para números muy grandes de cientos y más dígitos.

Todos los test de primalidad que se utilizan hoy en día parten de la misma idea, la que se remonta al matemático aficionado del Siglo XVII, Pierre de Fermat, el cual mostró que si se toma un número que sea primo, con , entonces el número es exactamente divisible en . Para números muy grandes , es mucho más rápido y fácil de calcular el número y ver si es divisible en , que buscar factores de . Si no divide a este número, entonces con seguridad no es un número primo. Este test rápidamente nos dice si no es primo. Lamentablemente no se puede concluir tan rápido si divide a que entonces sea necesariamente primo. Probablemente lo sea, pero hay muchos números que no son primos y son divisibles siguiendo los pasos de este último test.

Volviendo a la fórmula planteada inicialmente, ¿de dónde sale? ¿cómo se obtiene?. Para ello hay que remontarse nuevamente al Siglo XVIII para revisar un resultado atribuido a un tal Sir John Wilson y denominado en su honor  Teorema de Wilson:

Para un número entero positivo , es un número primo si (1)

Ejemplo: sea , entonces ( o sea 7) es primo dado que .

Otras maneras de plantear el mismo teorema son las siguientes:

1) Si es un número primo, entonces

2) Si es primo entonces es factor de

Sucede con frecuencia, en la historia de las matemáticas, que los nombres asignados a las conjeturas, teoremas y principios olvidan a personajes que tuvieron la idea original o hicieron una contribución fundamental a los mismos. El Teorema de Wilson, en este sentido, no es una excepsión. Este teorema fue descubierto por un matemático hindú llamado Bhaskara en el siglo VII, luego explicado por Ibn al-Haytham en el año 1000 DC, el teorema era conocido por Leibniz un siglo antes de nacer Wilson, el inglés Edward Waring lo planteó por primera vez en una publicación matemática llamada  Meditationes Algebraicae y finalmente fue demostrado por el matemático francés Joseph-Louis Lagrange en 1770, ¿cuál fue entonces el mérito de Wilson?.

Supongamos que se quiere obtener un número primo . Definimos , entonces por el Teorema de Wilson (1) es primo si . Esto significa que es divisible en , por lo que debe existir un número entero tal que , en la primera parte del procedimiento descripto  al comienzo, se da entonces que .

Ejemplo: Si , tenemos que y .

Pero ahora tenemos que:. Así la fórmula arroja cada número primo.

Si elegimos un número tal que no es primo, tenemos que: y, cualquiera sea el número que seleccionemos, . Así y obtendremos el número primo 2.

Esto explica porqué la fórmula entrega frecuentamente el valor .  Sin embargo, la fórmula dará todos valores primos y ningún otro, de manera muy ineficiente, cada vez que tanto como varíen.

Referencias:

# Prime Beef – Keith Devlin – Mathematical Spectrum Volume 18 1985/1986 Number 2 pp 33-34.

# Seconds of Prime Beef – Mathematical Spectrum Volume 19 1986/1987 Number 1 pp 19-20.

# Wilson’s Theorem – Encyclopedia Britannica Online (Consulta del 04/04/2010).

# Wilson’s Theorem – Wapedia (Accedido el 05/04/2010).

(Esta entrada se propone para la tercera edición del Carnaval de Matemáticas el próximo 19/04/2010 en el blog Geometría Dinámica).