Euclides y sus primos

Hace ya dos años publiqué esta nota, que es una de las más visitadas de En el cielo las estrellas. No es por pereza que aparece de nuevo aquí —ya que no me faltan notas en borrador— sino porque me parece que vale la pena ponerla al alcance de mis lectores actuales. Los que ya la leyeron sabrán disfrutarla de nuevo. 

Note: This is one of the most visited entries of this blog. If you don't read Spanish, you may try a Google translation from the menu here at right. Your comments are welcome in any language!

Seguramente han escuchado hablar de Euclides. Seguramente también saben que existen unos números llamados números primos. Algunos recordarán inclusive que existen infinitos números primos, tal vez sin estar muy seguros de qué significa esto. Los más memoriosos deben tener someros recuerdos de ambos, Euclides y sus primos, de la escuela secundaria. Quisiera refrescarles la memoria y contarles algo interesante.

Euclides fue el primero en demostrar que existen infinitos números primos. Su demostración es de una belleza, una simplicidad y una profundidad tales que debería ser de enseñanza obligatoria en las escuelas. Según el genial Douglas Hofstadter, pasar por la vida sin experimentar este pilar crucial del conocimiento humano es una desgracia comparable a no haber probado jamás el chocolate o escuchado una pieza de música. Yo estoy de acuerdo, y voy a hacer mi pequeña contribución para eliminar de la vida de mis lectores esta lamentable falta.

Para refrescarles la memoria basta decir que Euclides fue un matemático griego de la Antigüedad que vivió en Alejandría en el siglo III A.C. Fue el fundador de la geometría tal como la conocemos. Su libro Elementos fue un manual de texto usado desde su época hasta principios del siglo XX ¡durante veintitrés siglos! En cuanto a los números primos, como recordarán, son números enteros que no pueden dividirse por otro número sin dejar resto. El 7, por ejemplo, es primo porque no es divisible ni por 2, ni por 3, ni por 4, ni por 5, ni por 6. El 10 no es primo —es compuesto— ya que es divisible por 2 (y por 5 también, claro). Así de sencillos como parecen, los números primos están envueltos en misterios. A lo largo de la historia muchos de esos misterios han sido develados por los matemáticos. El más fundamental de todos —que existen infinitos números primos— fue demostrado por Euclides. Y ahora viene lo interesante.

¿Qué significa que existen infinitos números primos? Está claro que parece haber muchos: si hacemos una lista parecen no acabarse nunca. Claro que a medida que buscamos números más grandes es cada vez más difícil verificar si son primos (porque hay más candidatos para dividirlos). Pero bueno, el 2 es primo, el 3 es primo, el 5, el 7, el 11, el 13, el 17, el 23... Son los que están marcados en rojo en la figura de acá arriba, y que Uds. pueden continuar hasta donde quieran. Si son infinitos, significa que podríamos seguir alargando la lista sin terminar jamás. Obviamente, si sospechamos que son infinitos, demostrarlo mediante semejante enumeración sin fin no parece un plan muy practicable, dada la finitud de la vida humana. ¿Qué podemos hacer? ¿Fundar una secta de monjes, los Venerables Contadores de Primos, y alargar la lista generación tras generación? Sería también inútil: la vida en la Tierra se acabará en algún momento, a lo sumo cuando se extinga el Sol, y ni siquiera los miles de millones de años que hayan pasado habrán sido suficientes para enumerar infinitos números primos. Ni siquiera la eventual larguísima vida del universo todo, suponiendo que nuestros descendientes se muden a otros mundos, sería suficiente. Está claro que la demostración de que existen infinitos números primos debe ser más sutil que una simple enumeración. Así que hay que razonar. Y así razonó Euclides. Atención.

Supongamos que existe un número que es el mayor de los números primos, P, el Mayor Primo Bajo el Sol, y veamos a dónde nos lleva esta suposición. Si existe P, quiere decir que existe un conjunto finito, el Club de Todos los Primos, de los cuales P es el glorioso decano. Multipliquemos todos los números del Club, para formar un número —enorme, claramente mayor que P— que llamaremos Q. Es decir Q = 2×3×5×...×P. Este número Q es divisible por 2 (obviamente, ya que Q/2 da 3×5×...×P sin resto). También es divisible por 3 (ya que Q/3 = 2×5×...×P), por 5, por 7, por 11 y así sucesivamente hasta que dividimos a Q por P, también sin resto. Es decir, debido a su propia definición, Q es compuesto, ya que es divisible por todos los miembros del Club, o sea ¡por todos los primos del universo! (recordemos que supusimos que P es el mayor de todos los primos).

Ahora viene un paso crucial: sumemos 1 a Q, para formar el número Q+1. ¿Qué sabemos de Q+1? Que es un número colosal, sin duda. Es inclusive más grande que Q (no por mucho, pero es más grande). Sabemos también que Q+1 es compuesto, no puede ser primo, porque P (que es muchísimo más chico que Q+1) es el mayor de los primos. Cuando supusimos que P era el primo más grande, automáticamente supusimos que todos los números mayores que P tienen que ser compuestos.

OK, entonces Q+1 es compuesto. ¿Qué número primo podría ser divisor de Q+1? No puede ser 2, ya que 2 divide a Q, y Q es el anterior de Q+1, y los números pares nunca son consecutivos. Tampoco puede ser 3, ya que 3 divide a Q, que es el anterior, y los múltiplos de 3 tampoco son consecutivos (vienen de tres en tres...). De hecho, cualquier número primo p que elijamos, divide a Q, y por lo tanto no puede dividir al siguiente de Q, que es Q+1. En la figura se ilustra esto pintando los múltiplos de los primeros primos: nunca son consecutivos. Este razonamiento nos lleva a concluir que ninguno de los miembros del Club de Todos los Primos divide a Q+1. Ninguno, desde el pequeño 2 hasta el propio P.

Pero ¿entonces? En el párrafo anterior habíamos concluido que Q+1 es compuesto, o sea tiene algún divisor. ¡Y ahora decimos que no tiene ninguno! ¡Es una trampa! ¡Nuestro razonamiento nos ha arrinconado en una contradicción de la cual no sabemos si podremos escapar! Hemos creado un monstruo, un número que por un lado es compuesto, y por el otro no tiene ningún divisor. ¿Cómo zafamos?

La contradicción viene de la suposición de que existe ese Club de Todos los Primos, finito y cerrado, coronado por el máximo primo P. Así que no nos queda alternativa más que retroceder y eliminar esa suposición. No existe, no puede existir, el mayor de todos los primos. La verdad, según hemos demostrado, es que existen infinitos números primos. La lista de los números primos sigue y sigue, sin final. Ahora estamos seguros, no porque los hayamos contado uno por uno, sino porque lo hemos demostrado mediante un razonamiento impecable. (A propósito, este tipo de razonamiento en el cual se supone una hipótesis y se llega a una contradicción se llama reducción al absurdo, y está en el corazón de muchísimas demostraciones matemáticas.)

Espero que lo hayan disfrutado. Ahora no sólo saben que hay infinitos números primos, sino que saben por qué. Como el chocolate y como la música, dice el amigo Hofstadter, esta demostración es algo que se puede volver a disfrutar si dentro de un tiempo vuelven a leerla.

Para los curiosos que se preguntan para qué sirve un número primo, baste decir que los números primos se encuentran en el corazón de todos los métodos criptográficos de la actualidad, que permiten desde el almacenamiento seguro de las claves de usuario hasta la seguridad de las compras que hacemos con la tarjeta de crédito.

---

Douglas Hofstadter cuenta de manera encantadora, aquí burdamente imitada, esta demostración en su libro I am a strange loop.