Numeros Primos

Números primos y compuestos

Para entender que son los números primos hay que conocer antes los divisores.

Son divisores de un número todos aquellos números entre los que se puede hacer la división exacta de dicho número. Una división exacta es una división con resto cero o sin resto.

Con un ejemplo se verá mas claro. Algunos divisores del número 12 son el 1, el 2 y el 3. Porque 12 se puede dividir entre 1, (12 y resto 0), entre 2, (6 y resto 0) y entre 3, (4 y resto 0). Pero en cambio no son divisores ni 5 ni 7, porque si dividimos 12 entre 5 nos queda un resto de 2. Y si dividimos 12 entre 7 nos queda un resto de 5.

Si quieres consultar los divisores de los primeros 10.000 números puedes hacerlo consultando la tercera columna de la tabla representada en la siguientes páginas:

1~1000, 1001~2000, 2001~3000, 3001~4000, 4001~5000, 5001~6000, 6001~7000, 7001~8000, 8001~9000, 9001~10000

Ahora podemos definir lo que son números primos:

Un número primo es aquel que tiene exactamente dos divisores. Estos divisores siempre son el mismo número y el 1.

Ejemplo de números primos son el 2 y el 3. El 2 solo tiene dos divisores, 2 y 1. El 3 también tiene solo 2 divisores, 3 y 1. En cambio 4 tiene 3 divisores: 1, 2 y 4. Por tanto no es primo.

La siguiente lista muestra los números primos menores de 100: 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

Asimismo puedes comprobar cuales de los números menores de 10.000 son primos consultando la misma lista de páginas anterior. La fila que representa a un número primo tiene el fondo de color verde. O consultar las siguientes páginas donde se dan los números primos hasta el 100, el 200, el 500, el 1000, el 2000, el 5000 y el 10.000, que son las que más se suelen buscar.

Primos del 1 al 100, Primos del 1 al 200, Primos del 1 al 500, Primos del 1 al 1000, Primos del 1 al 2000, Primos del 1 al 5000, Primos del 1 al 10000

Los números con mas de dos divisores se denominan números compuestos. Los primeros compuestos son el 4 y el 6, con 3 y 4 divisores respectivamente.

  • Divisores del 4: 1, 2, 4.
  • Divisores del 6: 1, 2, 3, 6.

Criba de Eratóstenes

Existen métodos para encontrar números primos mucho mas sencillos que el de ir contando sus divisores.

Uno de los primeros algoritmos conocidos para localizar números primos es el conocido como Criba de Eratóstenes, el cual permite obtener todos los números primos menores a uno dado.

Se crea una lista con todos los números desde el 2 hasta el número máximo que vamos a comprobar. A continuación se eliminan todos los múltiplos de 2. Después se eliminan todos los múltiplos del siguiente número de la lista, el 3. Seguimos eliminando los múltiplos del siguiente de la lista, el 5, y así sucesivamente hasta eliminar todos los múltiplos de la lista. Los números que quedan son los primos que había en la lista.

La criba de Eratóstenes puede mejorarse eliminándose solo los múltiplos de hasta la raíz cuadrada del número máximo que vamos a comprobar. Esto es más fácil de ver cuando representamos la lista en una tabla cuadrada, como la del video que se muestra a continuación en los que se buscan los primos hasta 100, representando la lista en una tabla de 10 filas por 10 columnas.

La raíz cuadrada de 100 es 10. Cuando eliminamos los múltiplos de 2, 3, 5 y 7, (los primos menores de 10), el siguiente número a probar es el 11. Los múltiplos de 11 generados por multiplicaciones de 11 por 2, 3, 4, hasta 10 ya han sido descartados en los pasos anteriores. Y los múltiplos de 11 por 12, 13, etcétera, están descartados pues son todos mayores de 100. Por esto solo hay que eliminar los múltiplos de los números hasta 10, o en un caso más general, hasta la raíz cuadrada del número máximo a probar.

Otro método de generar números primos consiste en dividir cada número a partir del 3 entre todos los primos menores a el, (empezariamos por dividirlo entre 2). Si alguna división es exacta el número es compuesto. En caso contrario es primo.

Como ejemplo, para determinar si 17 es primo dividiriamos 17 entre 2, entre 3, entre 5, entre 7, entre 11 y entre 13. Puesto que ninguna división es exacta, 17 es primo.

Nuevamente, no es necesario comprobar hasta el primo inferior al número a comprobar. Basta con comprobar los primos menores de la raíz del número en cuestion. Para el caso del 17, cuya raíz es aproximadamente 4.12, solo necesitamos comprobar los primos menores a 4, el 2 y el 3.

Teorema Fundamental de la Aritmética

Los números primos son considerados como los ladrillos de la matemática gracias al Teorema Fundamental de la Aritmética.

Para entender este teorema tenemos que saber primero que son factores. Son factores de un número los números que mediante un producto generen al número original. Ejemplo: 6 y 2 son factores de 12, pues 12=2·6. Pero también pueden serlo 3 y 4, pues 12=3·4. Se llama factorización al proceso de obtener los factores de un número.

El Teorema Fundamental de la Aritmética afirma que todo número natural se puede representar de forma única como producto de factores primos.

Como ejemplo: 12=22·3 o 726=2·3·112, donde los únicos factores usados son factores primos, aunque como vemos un primo puede estar repetido en la factorización, o lo que es lo mismo, que puede estar elevado a una potencia.

De hecho, el número 1, antiguamente considerado primo, (pues se consideraba que todo número que tuviese como divisores a el mismo y al uno era primo), dejo de considerarse como tal pues tendríamos varias factorizaciones posibles de primos para un mismo número, como 6=2·3 y 6=1·2·3, y ya no sería una factorización única.

Infinitud de los números primos

Podemos preguntarnos cuantos números primos existen. Parece lógico pensar que con un conjunto finito de números primos podrían formarse por factorización todos los números posibles. De hecho si consultamos la lista de los primeros 1000 números en 1~1000, vemos en la segunda columna de la tabla que casi todas las factorizaciones aparecen un 2, un 3, un 5 o un 7. Aunque esto no es casual, pues la mitad de los números tienen 2 como divisor, una tercera parte a 3, uno de cada 5 al 5, etcétera.

Pero no es así. La lista de números primos es infinita. Existen diferentes formas de demostrarlo. La primera conocida es similar a la que voy a exponer aquí, y fue expuesta por Euclides, (325~265 a.C.).

Tomemos el producto de los primeros n primos + 1. Como ejemplo, el número formado por los primeros 3 primos sería:

2·3·5+1=31

Este número no es divisible por ninguno de los primos usado, pues en todos el resto de la división sería 1.

En tal caso quedan 2 posibilidades:

  • O es un número primo mayor que todos los anteriores, como el formado por los 3 primeros primos mas 1, el 31 citado.
  • O es un número compuesto formado por producto de primos mayores que los usados.

Como ejemplo del segundo caso el producto formado por 2·3·5·7·11·13+1=30031=59·509, ambos primos superiores a 13.

Como esto se cumple para cualquier número de primos usado siempre puedo encontrar primos mayores a uno dado usando dicho método. Por tanto, la lista es infinita.

Última modificación: domingo, 19 de abril de 2015, 14:40