Los números primos han fascinado a los matemáticos, tanto aficionados como profesionales durante siglos. Los números primos son considerados “las piezas fundamentales de construcción de los números enteros”, y la razón está en que todo entero positivo (Natural) es o bien un número primo o puede ser escrito como el producto de números primos de una forma única. Pocos objetos en matemáticas son tan simples de describir, pero por otra parte pocos poseen tanta profundidad y misterio en su estructura.
Estos números - 2, 3, 5, 7, 11, … - suelen aparecer a primera vista al azar, pero existen sorprendentes patrones subyacentes en su distribución.
En este espacio queremos profundizar en la antigua y moderna teoría de los números primos, desde las simples propiedades (por ejemplo la constatación de “la existencia de una cantidad infinita de números primos”) a difíciles problemas sin solución relacionados con la forma aparentemente caótica en que se distribuyen.
¿Qué son los números primos?
En esta sección vamos a observar algunas propiedades elementales de los números primos y los números compuestos y vamos a introducir algunas herramientas sencillas para trabajar con ellos.
Un número primo es un número que tiene solamente dos divisores, el 1 y él mismo. Por ejemplo, el número 11 es primo.
Para agilizar esta presentación voy a utilizar un software llamado MATHEMATICA que cuenta con varias funciones que permiten hacer cálculos de manera extremadamente rápida.
La primera función que voy a usar es la función PrimeQ[n] que responde Verdadero (True) si el número n es Primo y Falso (False) en caso contrario. Por ejemplo
El 111 no es un número primo porque 111=3·37. Dado que el 3 y el 37 no pueden ser descompuestos de la misma forma, los llamaremos los factores primos de 111. Similarmente, al producto 3·37 lo llamaremos fatorización prima de 111.
PrimeQ puede determinar la primalidad de números enteros bastante grandes, por ejemplo:
Estos resultados los obtengo en una fracción de segundo en un laptop de apenas 1.6 Ghz y 512 Mb de RAM. Pero, ¿qué deberíamos hacer nosotros para comprobar si estos números enormes son o no primos si sólo tuviéramos una calculadora a disposición ?
Pensemos en un número pequeño, el 35. Para verificar si es primo, tenemos que probar si es divisible por 2, por 3 y así sucesivamente hasta encontrar un número que lo divida de manera exacta. Si no existe ningún número que lo divida de manera exacta, entonces nuestra conclusión sería que el 35 es un número primo. Es claro que este número no es divisible por 2 (35/2=17.5), tampoco es divisible por 3 (resultado 35/3=11.6666…). No nos molestamos en verificar si es divisible por 4, porque si lo fuera, también sería divisible por 2. Cuando llegamos al 5, nos damos cuenta que el 5 cabe exactamente 7 veces en el 35, por lo tanto, 5·7 es la descomposición prima de 35.
Ahora ¿qué sucedería si el número fuese mucho más grande y que su primer factor primo fuera un número también grande?
Tomemos como ejemplo el número 7621615238807576688484949. Este número tiene como factorización prima a 2760727302517·2760727302497
En un análisis preliminar, como el primer número que factoriza al 7621615238807576688484949 es el 2760727302517 tendríamos que haber ido probando prácticamente uno por uno con todos los números menores que el 2760727302517, es decir tendríamos que haber hecho del orden del billón de intentos fallidos hasta dar finalmente con este divisor. Si por cada intento -suponiendo que contamos con alguien rápido con la calculadora- nos demorásemos 1 segundo, entonces para poder determinar que este número no era primo nos habríamos demorado del orden del billón de segundos, pero ¿cuánto tiempo en años es un billón de segundos? Un año tiene 365 días, cada día 24 horas, cada hora 60 minutos, cada minuto 60 segundos. Por lo tanto 1 año equivale a 365·24·60·60=31.536.000 segundos. ¿Y cuántas veces cabe este número en 1 billón? Calculemos 1000000000000/31.536.000=31709.8, es decir cerca de 32000 años, bastante tiempo, verdad? Gracias a los avances en la tecnología y la Teoría de Números, este resultado se puede obtener en apenas una fracción de segundo en cualquier computador actual que tenga instalado MATHEMATICA u otro software numérico.
Todo número que no es primo es el producto de factores primos, a estos números se los conoce con el nombre de números compuestos. El número 1 es un caso especial, no es primo ni compuesto. Para ser primo un número debe tener sólo dos divisores distintos, pero el 1 tiene un único divisor, el 1. Por eso es que el 2 es el primer número que se considera primo, porque es divisible por 1 y por 2, dos números distintos.
Por ejemplo, 24=2·2·2·3. Como todo número entero puede escribirse como el producto de números primos, los primos son considerados “las piezas fundamentales” del conjunto de los números enteros.
Para números de tamaño modesto, MATHEMATICA puede encontrar factorizaciones de números compuestos de manera muy rápida.
FactorInteger[n] encuentra la factorización prima del número n. FactorForm ordena el resultado en orden creciente de las bases.
Esta notación podría no ser muy legible, pero representa simplemente que
Para valores enteros hasta 10^37 (números con alredededor de 37 dígitos), la función FactorInteger encuentra sin problemas la factorización en un tiempo razonable.
Es fácil comprobar este resultado simplemente multiplicando estos dos valores
El problema general de factorizar un número entero es extremadamente complejo - hecho que hace que la criptografía moderna sea posible. El tiempo que toma factorizar números enteros cada vez más grandes crece aceleradamente, haciendo que una factorización rápida de un número arbitrario con apenas poco más de 40 dígitos quede fuera del alcance de los algoritmos y computadores modernos.
Sin embargo, para algunos casos especiales de números grandes no tenemos ningún problema.
Pero acá hicimos un poco de trampa. Escogimos 30! (30! que se lee “30 factorial” es el producto de 1•2•3•4•••30), número bastante fácil de factorizar.
Una tercera función que podemos usar para explorar los números primos es Prime[n], que entrega el n-ésimo número primo.
Ejemplo: Recordemos que el primer número primo es el 2, por lo tanto
El segundo número primo es el 3 por lo tanto
El siguiente es el cálculo del milésimo número primo
Y el siguiente es el millonésimo número primo
A continuación está la lista de los primeros 100 números primos.
¡Atención! La obtención exacta del n-ésimo número primo se puede lograr sólo si n es menor o igual a un billón (1012), pero esto no quiere decir que los primos se agoten a partir de este valor, la razón está en que el problema computacional asociado es extremadamente costoso, para el que los matemáticos (después de siglos y siglos) no han encontrado un algoritmo lo suficientemente rápido para hacer frente.
Cuando uno no puede resolver un problema, esto se puede deber a dos razones. El problema no tiene solución o nosotros no somos capaces de encontrarla. Esta incertidumbre permanece vigente hasta nuestros días.
¿Cuántos números primos hay?
¡Muchísimos!
Alrededor del año 300 AC, Euclides demostró que existen infinitos números primos ideando un método para construir un número primo a partir de otros ya conocidos. La simplicidad y elegancia de su demostración es legendaria en matemáticas tanto que vamos a enmarcarla a continuación y luego dar una exposición formal de dicha demostración.
Supongamos que el 2 y el 3 son los únicos números primos que conocemos. Si los multiplicamos y al resultado le sumamos 1, ese número no puede ser divisible ni por 2 ni por 3, luego probablemente sea un número primo.
2·3+1=7, 7 es primo.
Intentémoslo ahora con 2, 3 y 5.
2·3·5+1=31, nuevamente un primo.
Puedes intentar con 2, 3, 5, y 7, ó 2, 3, 5, 7 y 11, etc. En la medida en que calculamos estos números nuevos, no veremos ningún patrón, dado que a veces el resultado es primo y a veces no lo es. Como Euclides descubrió, podemos seguir obteniendo nuevos números primos con este proceso de multiplicar números primos y sumando 1 al resultado. A continuación está la demostración formal de la existencia de una cantidad infinita de números primos haciendo uso de este método de construcción o algoritmo.
Demostración de la infinitud de los números primos
Supongamos que p1, p2, p3,…, pn son números primos. Multipliquemos estos números y sumemos 1, llamando a este nuevo entero q. De esta forma q= p1·p2· p3·····pn+1. Si q es un número primo, entonces tenemos un nuevo número primo. Si q no es primo, debe ser divisible por un primo r. Pero r no puede ser p1, dado que deja como resto 1 al dividirlo por p1. De manera análoga, r no puede ser divisible por ningún pi. Por lo tanto, r es un nuevo número primo.
En otras palabras, sin importar que q sea primo o no, con este método siempre vamos a poder encontrar un nuevo número primo. Podemos continuar con este proceso indefinidamente y si nuestros computadores fueran tan inmortales como Euclides, podríamos obtener infinitos números primos de esta manera.
Se puede estar completamente seguro que en 1000 años más, matemáticos y curiosos seguirán sorprendiéndose con la claridad del razonamiento de Euclides.
Preguntas que surgen a partir del Teorema de Euclides
Pregunta 1
Después de pensar en la demostración del Teorema de Euclides, varias preguntas, todavía sin respuesta, se nos vienen a la mente. La siguiente pregunta es fácil de investigar.
Pregunta 1: Cuán frecuentemente un entero de la forma 1+2·3·5·7·11·13… es primo?
Los números de la forma 1+2·3·5·7·11·13 se denominan Números de Euclides o Números Euclídeos.
La expresión 
es una notación matematica usada para representar el producto de los enteros desde el 1 hastra el n. Así, por ejemplo, lo siguiente nos da el producto de los enteros desde el 1 al 5.
Para calcular el n-ésimo número de Euclides, definimos una función que toma el producto de los primeros n números primos y luego le suma 1.
Lo siguiente calcula 2•3•5+1
La siguiente es una lista de los primeros 11 números Euclídeos.
Algunos de los números de Euclides son primos y otros compuestos. Podemos encontrar con facilidad los números de Euclides primos, primero generando los números de Euclides y luego testeando su primalidad. El siguiente cálculo nos dice que el n-ésimo número de Euclides es primo cuando n=1,2, 3, 4, 5 y 11
Después de los primeros 5, los números de Euclides son evidentemente bastante escasos. El siguiente link contiene una lista de los primeros 200 números de Euclides. Ver ).
Aunque el Teorema de Euclides demuestra que los primos son infinitos, todavía no se sabe si hay un número infinito de primos de Euclides. El mayor número de Euclides primo actualmente conocido es el 26732-ésimo número de Euclides y que se muestra a continuación. Puede tomar varios días de cálculo probar que este número es primo.
Pregunta 2
Aunque la siguiente pregunta es bastante fácil de enunciar y comprender, resulta sorprendente que hayan transcurrido cerca de 2000 años para que pudiera ser formulada. Sigue sin respuesta hasta nuestros días.
Supongamos que construimos una lista de números primos, partiendo con el 2 y que usamos el método de Euclides para encontrar más números primos. Si al encontrarnos con un número compuesto escogemos solamente el divisor más pequeño ¿Aparecerán todos los números primos?
Para comprender la Pregunta 2, consideremos el método de Euclides. 2 es primo, entonces lo ponemos en nuestra lista. Agreguemos 1. Esto da 3, el cual es primo, así que lo ponemos en nuestra lista. Sumamos 1 al producto 2·3. Esto da 7, el cual es primo. Sumamos 1 a 2·3·7 para obtener 43, el que es nuevamente primo. Agregamos 1 a 2·3·7·43. Esto da 1807, número que no es primo.
El menor primo factor de 1807 es 13, entonces este se transforma en el siguiente número que ingresa a nuestra lista. Ahora miremos el 2·3·7·43·13+1. Este número también es compuesto, y su factor menor es el 53
Con la pregunta 2 buscamos saber si todos los números primos aparecerán eventualmente en esta secuencia. Sin embargo, estos números Euclídeos crecen bastante rápido, por lo tanto es imposible conseguir suficiente evidencia para responder a esta pregunta. El record mundial para el número Euclideo más grande encontrado de esta forma le pertenece a Sam Wagstaff, quien calculó 43 términos de esta secuencia y tomó todos los primos hasta la vigésimo novena entrada. La vigésimo octava entrada es el número primo más grande de la lista con 27 dígitos.
La función EuclidSequence genera la secuencia descrita en la Pregunta2
Un computador actual puede generar una lista con los primeros 17 términos en un tiempo que oscila entre los 20 minutos y 1 hora.
