Número primo

Plantilla:Números El conjunto de los números primos es un subconjunto de los números naturales que engloba a todos los elementos de este conjunto que son divisibles exactamente tan sólo por sí mismos y por la unidad (por convención, el 1 no se considera primo). Los veinte primeros números primos son: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 y 71.

Nótese el hecho de que todos los números naturales son divisibles por sí mismos y por la unidad.

El teorema fundamental de la Aritmética establece que cualquier entero positivo puede representarse siempre como un producto de números primos, y esta representación (factorización) es única.

¿Cuántos números primos existen?

Existen infinitos números primos. Euclides realizó la primera demostración alrededor del año 300 a.C. Otros matemáticos han demostrado la infinitud de los números primos con métodos diversos, e incluso hay una demostración topológica.

A pesar de que sabemos que hay infinitos números primos, aún quedan preguntas en el aire sobre la distribución de los mismos o la lista de primos que hay por debajo de cierto número.

Un procedimiento empleado para hallar todos los números primos menores que un entero dado es el de la criba de Eratóstenes. Además, se sabe que no hay límite para la distancia entre dos primos consecutivos, esto es, dado un número N, se puede encontrar dos números primos tales que entre ellos dos no hay otros números primos y su diferencia es mayor que N.

Aunque no se ha podido probar hasta la fecha, se conjetura que existen infinitos números primos de la forma p₁=p₂ + 2 (siendo p₁ y p₂ primos) o primos gemelos. Sí se ha probado que los únicos "primos trillizos" (primos de la forma p₁ = p₂ + 2 y p₂ = p₃ + 2) son 3, 5 y 7; y esto es así porque uno de los números p₁, p₂ y p₃ así definidos es múltiplo de 3, y por tanto compuesto cuando p₃>3.

Propiedades de los números primos

Si $p$ es un número primo y divisor del producto de números enteros $ab$ , entonces $p$ es divisor de $a$ o de $b$ . (Lema de Euclides)
Si $p$ es primo y $a$ es algún número entero, entonces $a^{p}-a$ es divisible por $p$ (Pequeño Teorema de Fermat)
Un número $p$ es primo si y solo si el factorial $(p-1)!+1$ es divisible por $p$ . (Teorema de Wilson)
Si $n$ es un número natural, entonces siempre existe un número primo $p$ tal que $n<p<2\cdot n$ . (Postulado de Bertrand)
En toda progresión aritmética $a_{n}=a+n\cdot q$ , donde los enteros positivos $a,\;q\geq 1$ son primos entre sí, existen infinitos números primos. (Teorema de Dirichlet).
El número de primos menores que un $x$ dado sigue una función asintótica a $f(x)={\frac {x}{\ln x-0,83}}$ (Teorema de los números primos).

Clases de primos

Número primo de Fermat (de forma 2²ⁿ + 1)
Número primo de Mersenne (de forma M_p = 2^p - 1 donde p es primo)
Número primo de Sophie Germain (un p primo tal que 2p + 1 es primo)
Números primos gemelos (p y p+2 primos)

Conjeturas sobre los números primos

Todo número par mayor o igual que 4 es suma de dos números primos. (Conjetura de Goldbach)
Existen infinitos pares de números primos gemelos.
Existen infinitos números primos de Fermat.
Para cada n natural, existe algún número primo entre n² y (n + 1)².
Existen infinitos números primos de la forma n² + 1
La sucesión de Fibonacci contiene infinitos números primos.

Aplicaciones en Informática

El algoritmo RSA se basa en la obtención de la clave pública mediante la multiplicación de dos números grandes (mayores que 10¹⁰⁰) que sean primos. La seguridad de este algoritmo radica en que no hay maneras rápidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales. La computación cuántica podría ofrecer una solución a este problema de factorización.

Los primos de Mersenne se encuentran entre los más grandes hallados (hasta diciembre de 2005) (2^30402457 - 1, más de 9 millones de dígitos, descubierto el 15 de diciembre de 2005). Los grandes números primos, de más de mil dígitos, son llamados "titánicos". Existe un proyecto de computación distribuida en la dirección http://www.mersenne.org.

Véase también

Páginas relacionadas

Enlaces externos

En español

En inglés:

The Prime Pages
Sobre el artìculo de Manindra Agrawal et al. PRIMES IS IN P en donde afirman: "We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite. [1]