Los números primos explicados de forma sencilla
Escrito por Viktor Jonas · Tiempo de lectura: unos 10 minutos
Un número primo es un número natural mayor que 1 con exactamente dos divisores: el 1 y él mismo. El 7 es primo porque solo el 1 y el 7 lo dividen sin resto. El 8 no lo es, porque también encajan el 2 y el 4. Los primos son las piezas con las que se construye cualquier otro número, y por eso reaparecen en casi todas las ramas de las matemáticas.
Divisor — un número que divide sin dejar resto.
Número primo — exactamente dos divisores.
Número compuesto — más de dos divisores, por ejemplo el 12.
Descomposición en factores primos — escribir un número como producto de primos.
Criba de Eratóstenes — método para hallar todos los primos hasta un límite.
Primos gemelos — dos primos separados por 2, como el 11 y el 13.
Por qué el 1 no cuenta
Parece arbitrario, pero hay una razón sólida. El teorema fundamental de la aritmética dice que todo número mayor que 1 se descompone en factores primos de una única manera. Si el 1 fuera primo habría infinitas descomposiciones: 12 = 2 · 2 · 3 = 1 · 2 · 2 · 3 = 1 · 1 · 2 · 2 · 3, y así sin fin. La unicidad desaparecería. Por eso se excluye el 1: para que el teorema más importante sobre los números siga siendo limpio.
Descomposición en factores primos
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
360 = 23 · 32 · 5
El procedimiento es tosco y siempre funciona: dividir por el primo más pequeño que encaje y seguir con el resultado hasta que quede 1. De la descomposición se leen después cosas que de otro modo habría que adivinar, como el mínimo común múltiplo o el máximo común divisor de dos números.
La criba de Eratóstenes
| Paso | Qué ocurre | Se tachan |
|---|---|---|
| 1 | el 2 se queda, se tachan sus múltiplos | 4, 6, 8, 10 … |
| 2 | el 3 se queda, se tachan sus múltiplos | 9, 15, 21, 27 |
| 3 | el 5 se queda, se tachan sus múltiplos | 25 |
| 4 | listo, porque 7 · 7 = 49 > 30 | — |
Quedan 2, 3, 5, 7, 11, 13, 17, 19, 23 y 29. El último paso es el más útil: solo hay que cribar hasta la raíz cuadrada del límite. Para comprobar si 97 es primo se prueban los divisores 2, 3, 5 y 7, y nada más, porque 11 · 11 = 121 ya supera a 97.
Errores habituales
- Contar el 1 como primo
- No lo es.
- Olvidar el 2
- Es el único primo par y se salta con facilidad al enumerar deprisa.
- Probar todos los números como divisores
- Basta llegar a la raíz cuadrada; en números de tres cifras eso ahorra casi todo el trabajo.
- «Todos los impares son primos.»
- El 9, el 15, el 21 y el 25 dicen lo contrario.
Hay infinitos
Euclides lo demostró hace más de dos mil años y la prueba cabe en cuatro líneas. Supongamos que solo hubiera un número finito de primos. Se multiplican todos y se suma 1. Al dividir ese número nuevo por cualquiera de los primos supuestos queda resto 1: ninguno encaja. Así que el número nuevo o bien es primo, o bien tiene un factor primo que no estaba en la lista. Las dos cosas contradicen la suposición. La lista, por tanto, nunca puede estar completa.
Comprueba si 143 es un número primo. Explica qué divisores hay que probar y por qué puedes detenerte ahí.
Ver solución
La raíz de 143 está entre 11 y 12, porque 11 · 11 = 121 y 12 · 12 = 144. Solo hay
que probar los primos hasta 11: 2, 3, 5, 7 y 11.
El 2 queda descartado (143 es impar), el 3 también (suma de cifras 8), el 5 igual (la
última cifra no es 0 ni 5) y el 7 no encaja (7 · 20 = 140, resto 3). Pero
11 · 13 = 143.
Así que 143 no es primo. Si el 11 tampoco hubiera encajado, 143 sería
primo: cualquier divisor mayor necesitaría un compañero más pequeño, y todos los
pequeños ya se han comprobado.
Los primos no son solo materia de clase. El cifrado con el que tu navegador envía los datos bancarios se apoya en que multiplicar dos primos muy grandes es trivial, mientras que volver a descomponer el producto resulta prácticamente imposible.
Primos gemelos y primos récord
Cuanto más arriba se llega en la serie de los números, más escasos son los primos, pero nunca desaparecen. A veces dos de ellos están muy juntos: 3 y 5, 11 y 13, 17 y 19, 29 y 31, 41 y 43. Los pares con una diferencia de 2 se llaman primos gemelos. Un pequeño truco muestra dónde buscarlos: todo primo mayor que 3 está justo al lado de un múltiplo de 6, porque los demás restos dan números pares o múltiplos de 3. Por eso, salvo el par 3 y 5, todo par de gemelos tiene la forma 6k − 1 y 6k + 1, por ejemplo 5 y 7 o 17 y 19.
Si existen infinitos primos gemelos, sigue sin demostrarse. Con todo, en 2013 el matemático Yitang Zhang logró un avance decisivo: demostró que existen infinitos pares de primos cuya diferencia es como mucho de 70 millones. Otros investigadores rebajaron después esa cota a 246. Así que todavía queda un largo camino hasta el 2.
Los mayores primos conocidos tienen casi siempre la forma 2p − 1, donde el exponente p es a su vez primo. Se llaman primos de Mersenne. Los primeros son 2² − 1 = 3, 2³ − 1 = 7, 2⁵ − 1 = 31 y 2⁷ − 1 = 127. No es automático, sin embargo: ya 2¹¹ − 1 = 2.047 no es primo, porque 23 · 89 = 2.047. Para números de esta forma existe una prueba especialmente rápida, la prueba de Lucas-Lehmer. Por eso aquí se pueden llevar los récords mucho más lejos que con números cualesquiera. La búsqueda se hace en el proyecto colaborativo GIMPS (Great Internet Mersenne Prime Search), en el que voluntarios ceden el tiempo de cálculo de sus ordenadores. Los números récord tienen muchos millones de cifras: escritos por completo, llenarían muchos miles de páginas de libro.
Encuentra todos los primos gemelos menores que 50 y comprueba si cada par, salvo 3 y 5, tiene la forma 6k − 1 y 6k + 1.
Ver solución
Los primos hasta 50 son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Con diferencia 2 están juntos: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) y (41, 43).
Comprobación: 5 y 7 rodean al 6 (k = 1), 11 y 13 al 12 (k = 2), 17 y 19 al 18 (k = 3), 29 y 31 al 30 (k = 5), 41 y 43 al 42 (k = 7). Solo (3, 5) se sale de la regla, porque el 3 es a su vez un divisor de 6. El 47 no tiene gemelo, ya que 45 y 49 son ambos compuestos.
Cómo usa el cifrado RSA los números primos
El método RSA, llamado así por sus inventores Rivest, Shamir y Adleman, protege datos en internet desde los años setenta. La idea básica: se eligen dos primos muy grandes p y q y se multiplican para obtener n = p · q. El producto n se publica; los dos factores permanecen secretos. Quien quiere cifrar un mensaje solo necesita n y un segundo número público e. Quien quiere leerlo necesita además un exponente secreto d, y ese solo lo puede calcular quien conozca p y q.
p = 61 y q = 53, así que n = 61 · 53 = 3.233
(p − 1) · (q − 1) = 60 · 52 = 3.120
público: e = 17, secreto: d = 2.753
Comprobación: 17 · 2.753 = 46.801 = 15 · 3.120 + 1
Cifrar el mensaje 65: 6517 dividido entre 3.233 deja de resto 2.790
Descifrar: 2.7902753 dividido entre 3.233 deja de nuevo de resto 65
Que el mensaje vuelva de verdad se deduce de un teorema de Euler sobre restos en la división. Lo decisivo es la mirada a la seguridad: el pequeño número 3.233 lo descompone cualquiera en segundos. Las claves reales usan un n de 2.048 bits, es decir, más de 600 cifras decimales. La división de prueba tendría que llegar hasta la raíz de n, un número con unas 300 cifras, y eso es imposible. Incluso los métodos de factorización más rápidos que se conocen tardan un tiempo inimaginable con esos números en los ordenadores actuales. Lo que no está demostrado es que no exista un camino rápido. Según lo que sabemos hoy, los ordenadores cuánticos podrían ofrecerlo en teoría si algún día se construyen lo bastante grandes. La seguridad de RSA se apoya, pues, en la experiencia y no en una demostración.
Gemelos, huecos y récords
Los primos se reparten de forma irregular, y eso es justo lo que los hace interesantes. A veces hay dos muy juntos, como el 11 y el 13 o el 41 y el 43: esos pares se llaman primos gemelos. Otras veces aparecen huecos enormes: entre 113 y 127 no hay ni uno. Esos huecos se pueden incluso fabricar a medida. Toma 101! y súmale 2, luego 3, luego 4 y así hasta 101: cada uno de esos cien números es divisible por el valor que has sumado, así que ninguno es primo. Existen, por tanto, tramos sin primos tan largos como se quiera, y aun así los primos no se acaban nunca.
Si hay infinitos gemelos sigue siendo un misterio. La pregunta es uno de los problemas abiertos más famosos de las matemáticas. Lo que sí se sabe es que los primos escasean a medida que los números crecen: cerca de un número n, de media sigue siendo primo aproximadamente uno de cada ln(n). En números de tres cifras eso es más o menos uno de cada siete; alrededor del millón, solo uno de cada catorce.
El método RSA con el que los navegadores y los bancos cifran datos se apoya en dos primos muy grandes, cada uno de varios cientos de cifras. Multiplicarlos lleva una fracción de segundo. La clave pública contiene solo el producto, y recuperar de ahí los dos factores resulta, con todos los métodos conocidos, prácticamente imposible. Ese desequilibrio entre un camino de ida fácil y uno de vuelta desesperado es toda la seguridad del sistema. Si mañana alguien encontrara un método rápido de factorización, habría que sustituir la mitad del cifrado de internet.