03/03/2012

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.

9 comentarios:

  1. Lograste lo que hace rato no lograba nadie: retrotraerme a mis primeros años de la secundaria: yo soy uno de los que pasamos por esas demostraciones que mis alumnos actuales tildan de "innecesarias, absurdas y ..." no agrego la última parte por decoro. Lo interesante es que nos prepararon para todo el conocimiento que acumulamos después. ¡Cuánto le agradezco a esos profesores que tuvimos y que nos guiaron y acompañaron en el descubrimiento del saber!

    ResponderEliminar
  2. Gracias por repostearlo :)

    Ya conocía la demostración y de las pocas que conozco me resulta una de las más elegantes, simples y bellas.

    La matemática es como un cirrus, ligera, elegante, refinada.
    La física, por su parte es como un cúmulus nimbus, fascinante, voluptuosa, medio mamarracha en algunas cosas pero sin dejar de ser bella.

    ResponderEliminar
  3. Juan Carlos Z11/3/12 21:17

    Y,.. digo yo, ya que son infinitos, ¿cual es el mayor número primo conocido? Imagino algún tipo de competencia intelectual entre universidades de manera similar a como de tanto en tanto se anuncia que se llego a conocer el decimal no se cuanto de pi.

    ResponderEliminar
  4. Juan Carlos Z11/3/12 23:14

    Se me ocurre otra pregunta: ¿en que sistema numérico contaban los griegos? En numeros romanos? en qué? los numeros actuales son arabigos y se introdujeron después.

    ResponderEliminar
    Respuestas
    1. Los griegos teníen un sistema complicado, similar al de los romanos pero más loco. Usaban todas las letras del alfabeto para representar las unidades, las decenas y las centenas, y armaban los números de manera aditiva. Como los romanos, no podían expresar números muy grandes de esta manera. Los astrónomos griegos posteriores a la Edad de Oro, sin embargo, inventaron un sistema sexagesimal (para medir ángulos) que era posicional, es decir como el nuestro, que permite expresar números arbitrariamente grandes con un conjunto pequeño de símbolos. Además, en un sistema posicional es muchísimo más fácil hacer operaciones. Arquímedes, en un librito titulado El Contador de Arena (algo cuento en Viaje a las Estrellas) inventó un sistema para expresar números arbitrariamente grandes.

      Eliminar
  5. Me costo mucho aprender sobre los numeros primos, pero jamas supe la demostracion de ellos. Uno nunca aprende del todo :)

    ResponderEliminar
  6. Juan Carlos Z12/3/12 14:21

    Me confundió esta pregunta: "OK, entonces Q+1 es compuesto. ¿Qué número primo podría ser divisor de Q+1?" pensé ¿porque el divisor de Q+1 debe ser un número primo? y no cualquier otro número primo o no-primo? Me tomé la molestia de ir a la versión anterior de la entrada que publicaste hace dos años en el 2010 y oh sorpresa! ahí la misma pregunta no incluye la palabra "primo" sino que es: "OK, entonces Q+1 es compuesto. ¿Qué número podría ser divisor de Q+1?" Ahora la cosa toma sentido. ¿Porque se coló ahí la palabra "primo" en esta segunda version de la entrada?

    ResponderEliminar
    Respuestas
    1. ¡Excelente pregunta! Estaba esperando que me la hicieran. La demostración queda más prolija así, porque descarto uno por uno los divisores primos de Q+1. La razón es que sólo los divisores primos son relevantes, ya que las divisiones se "encadenan", ¿no? Por ejemplo, tomemos el número 18. Es compuesto. ¿Cómo lo sabemos? Bueno, es divisible por 6. Pero el 6 también es compuesto, ya que 6 = 2×3. Como 18 es divisible por 6, y 6 es divisible por 2 y por 3, entonces 18 es automáticamente divisible por 2 y por 3. Así que cuando busco divisores de 18, sólo necesito revisar los números primos menores que 18. Chan.

      Eliminar
  7. Querido Juan Carlos Z: Como bien dice Guillermo, uno de los usos de los números primos es para hacer claves criptográficas y, por lo tanto, mientras más grandes sean los números usados, más difícil de decifrar la clave. Es fácil deducir que los mayores números primos encontrados hasta ahora están en manos de los que quieren claves MUY seguras, y por lo tanto, son TOP SECRET, como no podría ser de otra forma.

    ResponderEliminar