Continuamos hablando de números primos. En el post anterior vimos su carácter aleatorio. Aparecen aquí y allá sin que alguien pueda predecir dónde. No hay una fórmula conocida que nos devuelva siempre números primos, y de hecho, se debe verificar computacionalmente si los posibles 'candidatos' a número primo realmente lo son.
Sin embargo, hay ciertos números primos que siguen determinadas fórmulas matemáticas. (Ojo, esto no quiere decir que todos los números que siguen dichas fórmulas sean necesariamente primos). En algunas ocasiones, esto implica curiosas propiedades matemáticas, como veremos a continuación.
Primos de Mersenne
Un número de Mersenne es de forma N = 2p - 1, donde p es primo. No todos los números de Mersenne son primos, de hecho, sólo se conocen 47 primos de Mersenne. Sucede algo interesante: los nueve mayores números primos que se conocen son de Mersenne. ¿Por qué?
Para empezar, sólo podemos encontrar un primo de Mersenne a partir de otro primo. Esto ya reduce sensiblemente nuestro campo de búsqueda. Pero además, la fórmula de los números de Mersenne es muy simple, y esto supone que hay algoritmos de búsqueda relativamente sencillos.
En concreto, el más famoso es el algoritmo de Lucas-Lehmer. N = 2p - 1 es primo si y sólo si es divisor de Sp-2. Los términos de la sucesión Sj se definen por Sj = Sj-12 - 2, con S0 = 4.
Existe un interesante proyecto de computación colaborativa, llamado GIMPS (Great Internet Marsenne Prime Search), en la que miles de usuarios de todo el mundo colaboran en la búsqueda de primos de Marsenne instalando un programa en su ordenador. No hace falta el supercomputador más potente del mundo, como intuían algunos de nuestros lectores en la anterior entrada. En este caso, la unión hace la fuerza.
De hecho, los nueve primos más grandes conocidos hasta la fecha han sido gracias a la fundación GIMPS, es decir, gracias a miles de usuarios anónimos cediendo una pequeña parte de la potencia de su ordenador para hacer estos cálculos.
Nos podríamos preguntar cuál es la utilidad real de encontrar números primos cada vez más grandes en lugar de dedicar recursos informáticos a otras cosas. Como bien dijo alguno de vosotros en los comentarios del post anterior, los números primos son muy útiles para cifrar información, y cuanto más grandes, mejor. Si usásemos números compuestos, se podría de hecho descomponer el problema en varios problemas más sencillos y mucho más fáciles de resolver.
Primos de Fermat
Son de la forma N = 22n+ 1. Sólo se conocen cinco primos de Fermat: 3, 5, 17, 257 y 65537. Estos números tienen una propiedad geométrica muy curiosa: un polígono regular de n lados se puede construir de forma directa con regla y compas si y sólo si n = 2k·p, donde k es cualquier número entero no negativo y p es un primo de Fermat. Así que no intentéis buscar un método directo para dibujar el heptágono regular, ya que 7 no cumple la condición.
Primos de Sophie Germain y primos seguros
Un número p es un primo de Sophie Germain si es primo y además N = 2p + 1 también es primo. Por ejemplo, el 11 lo es ya que 11·2 + 1 = 23 es primo. En este caso, al número N (por ejemplo, 23) lo llamaríamos 'primo seguro'. Este nombre se debe a que dicho tipo de primos es útil en aplicaciones de criptografía y cifrado. Salvo el 5 y el 7, no existe ningún primo seguro que sea además de Mersenne o de Fermat (los primos de Fermat, comparativamente, serían 'menos seguros' ya que derivan de una fórmula matemática concreta en la que no intervienen otros números primos).
Primos de Euclides
Son los números de forma p# + 1. El número p# es el llamado primorial de p. Sólo un número primo puede tener primorial. El primorial de p estaría formado por el producto de p por todos los primos menores que él. Por ejemplo: el primorial de 5 sería 5# = 5·3·2 = 30. Si nos fijamos en el número primo 31, resulta que 31 = 30 + 1 = 5# + 1, por tanto 31 es un primo de Euclides.
Estos primos están directamente relacionados con la demostración de la infinitud de los números primos dada por Euclides y que vimos en el primer post sobre números primos.
Primos gemelos
Son parejas de primos que están separados por sólo una unidad. Por ejemplo, 3 y 5, ó 17 y 19. Una de las grandes cuestiones de la teoría de números es precisamente saber si existen infinitas parejas de primos gemelos. Intuitivamente, uno tendería a pensar que la aparición de primos es cada vez menos frecuente a medida que los números se van haciendo mayores, por lo tanto debería ser cada vez más difícil encontrar dos primos separados tan solo por una unidad.
La pregunta es, ¿existe realmente algún momento en el que ya no podamos encontrar primos gemelos? no se sabe, pero la mayoría de hipótesis suponen que existen infinitas parejas de primos gemelos. Aunque esto choque con la intuición, concuerda con las sorprendentes propiedades de la distribución de números primos.
Veremos esto en la cuarta entrega de la serie, pero antes, en el siguiente post, seguiremos viendo más tipos de primos. En este caso, nos acercaremos de un modo informal y veremos números con propiedades curiosas y divertidas.
Imagen | Número de dígitos de los primos de Mersenne conocidos En Genciencia | Los díscolos números primos (I)
Ver 8 comentarios