Numeros Primos

Números primos

Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dos definiciones el 1 queda excluido del conjunto de los números primos.

Ejemplos: a) El 7 es primo. Sus únicos divisores son 1 y 7. Sólo puede expresarse como producto de 7•1.

b) El 15 no es primo. Sus divisores son 1, 3, 5 y 15. Puede expresarse como 3•5. (y también como 15•1)

El término primo no significa que sean parientes de alguien. Deriva del latín "primus" que significa primero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los "primeros", porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5)

Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100.

En la siguiente tabla tenemos todos los primos menores que 1000, que hacen un total de 168 (21×8)

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73

79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181

191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307

311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433

439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571

577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701

709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853

857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

Póster con los números primos hasta 1000 Listado con los primos menores que 1.000.000 (

Para ver los 10.000 primeros números primos pincha aquí

Primos en el anillo de los enteros de Gauss

Cómo averiguar si un número es primo.

El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, ... , n-1. Si alguna de las divisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si un número es compuesto alguno de sus factores (sin contar el 1) debe ser menor o igual que √ n. Por lo tanto, el número de divisiones a realizar es mucho menor. Sólo hay que dividir entre 2, 3, 4, 5, ... , [√ n]. En realidad, bastaría hacer las divisiones entre los números primos menores o iguales que √ n.

Ejemplo: Para probar que 227 es primo sabiendo que √227 = 15'0665... basta con ver que no es divisible entre 2, 3, 5, 7, 11 y 13.

Este procedimiento resulta eficiente para números pequeños o que tienen factores pequeños. Sin embargo si el número tiene por ejemplo unas 20 cifras y es primo, habrá que realizar miles de millones de divisiones para comprobarlo. Aunque un ordenador pueda realizar millones de divisiones en un segundo, el tiempo necesario es bastante considerable. Y cuando el número de dígitos aumenta el tiempo necesario ¡¡crece de forma exponencial!!

Ejemplo práctico: Supongamos que queremos saber si un número de unas 50 cifras es primo. La raíz cuadrada de un número de este orden está en torno a 1025. Si un ordenador hace 1000 millones de divisiones por segundo, necesitará 1025/109 segundos; es decir, 1016 segundos. Este tiempo equivale, aproximadamente, a 1'6*1014 minutos, que son 2'7*1012 horas, o también 1'16*1011 días, aproximadamente 3'17*108 años. Que para hacer esto se necesiten 317.097.920 años se me antoja una tarea poco recomendable. Y si nos decidiésemos a llevarla a cabo, ¿sería útil esta información pasado todo este tiempo? O más drástico todavía, ¿seguiría existiendo nuestra especie entonces?

Debemos pues, buscar una alternativa que nos permita responder a este problema de una forma más favorable; necesitamos un algoritmo más eficiente.

Una respuesta puede ser el teorema pequeño de Fermat. Este teorema afirma que si n es primo y mcd(a,n) = 1, entonces an-1 ≡ 1 (mod n). Hay que tener en cuenta que la exponenciación modular puede realizarse en un tiempo bastante favorable, si se hace de forma adecuada (hay algoritmos que nos dan la respuesta en tiempo polinómico)

Ejemplo: Queremos comprobar si el número 15 es primo o no (utilizando esta propiedad). Tomamos a = 2, n = 15, y evaluamos 214 (mod 15). La respuesta es 214 ≡ 4 (mod 15). Podemos asegurar entonces que 15 es compuesto. Probemos con a = 2, n = 341, evaluamos 2340 (mod 341) y obtenemos que 2340 ≡ 1 (mod 341). Esto no nos permite deducir que 341 sea compuesto, pero tampoco que sea primo. Al probar con a=3 tenemos 3340 ≡ 56 (mod 341), lo cual implica que 341 es compuesto.

A los números que se comportan como el 341 en el ejemplo anterior se les llama pseudoprimos para la base 2 (se comportan como un primo para a=2). Este comportamiento es bastante más peculiar peculiar para algunos números. Tomando por ejemplo a=2 y

...