miércoles, 23 de febrero de 2011

216. Los números primos




Nuestro amigo Víctor plantea en un comentario al párrafo anterior estas interesantes preguntas:


"Tengo entendido que hay matemáticos que se dedican a buscar números primos, lo que me sugiere que la "aparición" de tales números no sigue una pauta regular.

1º ¿Estoy en lo cierto, o, por el contrario, los números primos SI que se encuentran ordenados de forma regular?

2º En caso de que NO sigan una pauta regular: ¿por qué es así?

3º Y por último (para conocer cuál es la mecánica de esa búsqueda): ¿qué procedimiento tendríamos que seguir para encontrar los números primos que existan entre, por ejemplo, los números 4.000 y 14.000?"

Voy a tratar de responder aquí hasta donde yo sé, pero los lectores que deseen proponer sus ideas serán bienvenidos.

Los números primos son aquellos números enteros que no poseen divisores que produzcan un cociente entero y exacto. Obviamente se exceptúa de la regla la división por el mismo número y por el número 1, que siempre producen un número entero. Se llaman compuestos a los enteros que no son primos. Si, por ejemplo, se parte del número 2 y se suma 2 repetidas veces para producir 4, 6, 8, ... todos estos números son compuestos con excepción del primero de la serie que es primo: el 2. El siguiente número, 3, no está en la sucesión anterior (no es múltiplo de 2) y, por lo tanto, es primo. Igual que antes, sumamos 3 repetidas veces para encontrar 6, 9, ... que son todos compuestos salvo el primero (el 3). Ahora el 4 no puede usarse porque está en la sucesión del 2 y hay que pasar al 5, el que por no estar en sucesión anterior alguna, es primo, igual que antes, sumamos... etc etc.
Como se ve, los compuestos están perfectamente ordenados en sucesiones muy fáciles de formar. Los primos serían los "huecos" del conjunto de todas esas sucesiones y nadie conoce un ordenamiento que los incluya en su totalidad. Pero pienso que no hay una razón "de principio" que impida la existencia de un tal ordenamiento. Esto querría decir que propuesto un cierto número (por ejemplo 2011) se podría responder inmediatamente si es o no primo.
Por el momento, saber si un número es primo o no, requiere dividirlo por los primos anteriores... aunque no todos, por lo siguiente: cuando se divide un número por otro para obtener un cociente entero y un "resto" también entero, puede pasar que el cociente sea mayor o menor que el divisor. Por ejemplo: 6 dividido 2 da 3 y 6 dividido 3 da 2. Si el resto ha dado cero para una división con un divisor menor que la raíz cuadrada del número, volverá a dar cero con un divisor mayor que esa raíz cuadrada, y si nunca el resto dio cero con los divisores menores que la raíz cuadrada, nunca dará cero. Entonces basta probar con divisores menores que la raíz cuadrada del número. Para los números del 1 al 100 hay que probar con los divisores 2, 3, 5 y 7 y para los números del 1 al 1000 hay que probar a dividirlos por los primos hasta el 31.
Para lo propuesto por Víctor en su punto 3, habría que probar a dividir los números del 4000 al 14000 por divisores que, para los cercanos al 4000, serían los primos menores que el 61(incluyendo éste) y ya para los cercanos al 14000 habría que extenderse hasta el 113. Por supuesto, se encuentran en Internet tablas de números primos y programitas rápidos que responden si un cierto número es primo o no.
En resumen, no existe un algoritmo "breve" para detectar si un número es primo o no ya que, cuando se proponen números relativamente "grandes", el número de divisores a probar también es "grande" pero, desde luego, los sistemas informáticos realizan este proceso a gran velocidad.
Un inesperado beneficio colateral del estudio de los números primos consiste en que el moderno trabajo sobre claves secretas y encriptación de la información se basa en los teoremas que se han ido obteniendo en ese estudio.
Los interesados en estos temas pueden empezar poniendo en un buscador de Internet, por ejemplo, la frase "Máquina Enigma".

Ilustra esta entrada la excelente foto de una máquina Enigma, tomada por Víctor en el Deutsches Museum de Berlín.

Si algún lector desea agregar algo, como ya dije, es bienvenido.

Saludos a todos.

2 comentarios:

Víctor dijo...

Roberto, muchas gracias por dedicar esta entrada a la consulta que te hice.

Me ha quedado clara la mecánica para detectar los números primos, y me has despejado la duda que tenía sobre la existencia de una pauta "regular", en sentido negativo.

Me parece asombroso que, como dices, no se conozca un ordenamiento que incluya la totalidad de los números primos, dada la simplicidad aparente de la cuestión y los medios de computación actuales.. ¿no habrá algún error de origen en el sistema decimal? (esto es broma)

Muy interesante también la historia de la Enigma que viene en la wikipedia..

Un abrazo

Roberto dijo...

Ahora que nombras el sistema decimal, Víctor, me haces recordar que en realidad hay algún mecanismo breve, pero solo para números pequeños, para saber si son primos o no: los llamados criterios de divisibilidad. En la escuela elemental se habla de unos simples algoritmos para saber si un número es múltiplo de 2, 3, 5, 7 u 11. Por ejemplo sumar sus cifras y si da múltiplo de 3 el propio número es múltiplo de 3. Seguro que allí en España hacen algo parecido en los primeros grados de primaria, ¿no?
Esto permitiría rápidamente saber si un número menor que el cuadrado de 11 (121) es primo o no.
Lógicamente, en la actualidad, eso puede hacerse con una calculadora de bolsillo en un instante... y no resuelve el problema de los números un poco más grandes que 121. Te cuento algo personal: a mí me divierte buscar (mentalmente) los factores primos que multiplicados dan un cierto número propuesto, por ejemplo, el correspondiente al año corriente. Y, si no me equivoco, lo hice algún día de enero del 2009 con ese número y también algún día de enero del 2010... bueno, por ejemplo: 2010 es 2*3*5*67.
No lo trates de hacer con 2011... es primo, ja ja.

Un abrazo.