Número primo

De Wikipedia, la enciclopedia libre

El conjunto de los números primos es un subconjunto de los números naturales que engloba a todos los elementos de este conjunto mayores que 1 que son divisibles únicamente por sí mismos y por la unidad.

Los números primos menores que cien son 25, a saber: 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.

El teorema fundamental de la Aritmética establece que cualquier número natural mayor que 1 siempre puede representarse como un producto de números primos, y esta representación (factorización) es única módulo el orden de los factores.

Tabla de contenidos 1 ¿Cuántos números primos existen? 2 Propiedades de los números primos 3 Clases de primos 4 Conjeturas sobre los números primos 5 Aplicaciones en Informática 6 Referencias 7 Véase también 8 Enlaces externos

[editar] ¿Cuántos números primos existen?

Existen infinitos números primos. Euclides realizó la primera demostración alrededor del año 300 adC. Otros matemáticos han demostrado la infinitud de los números primos con métodos diversos, contandose entre ellos Algebra Conmutativa y Topología.

A pesar de que sabemos que hay infinitos números primos, aún quedan preguntas en el aire sobre procedimientos exactos para saber con certeza si un número determinado es primo o no en tiempo computacionalmente bajo.

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; para ver esto basta notar que para n entero positivo en el conjunto

no hay numeros primos, pues sus elementos son divisibles por respectivamente.

Si nos preguntamos por la cantidad de primos bajo una cierta cantidad dada se conocen resultados satisfactorios. Denotando por π(x) la cantidad de primos hasta x se tiene que

donde, como es usual en Teoría de Números, log denota el logaritmo natural. Este es el Teorema del Número Primo en su versión mas sencilla, pero su demostración no es trivial.

Hasta hoy se mantienen abiertos numerosos problemas relativos a la distribución y frecuencia de aparición de los primos y de algunas familias particulares de estos. Por ejemplo, se conjetura que existen infinitos números primos de la forma p₁=p₂ + 2 (siendo p₁ y p₂ primos) o primos gemelos.

[editar] 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 natural diferente de 1, 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 . (Postulado de Bertrand)
• En toda progresión aritmética , donde los enteros positivos 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 (Teorema de los números primos).
• El anillo Z/nZ es un cuerpo si y solo si n es primo. Equivalentemente: n es primo si y solo si φ(n) = n − 1.

[editar] 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)

[editar] 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.

[editar] 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 primos hallados. Actualmente el primo de Mersenne más alto encontrado cuadragésimo cuarto es el número 2^32582657 – 1 que tiene 9.808.358 dígitos y fue descubierto el 4 de septiembre de 2006 gracias al proyecto de computación distribuida GIMPS en la dirección.^[1]

[editar] Referencias

[editar] Véase también

• Portal:Matemática Contenido relacionado con Matemática.
• Criptografía
• Matemática
• Espiral de Ullam
• Test de primalidad
• Tabla de factores primos

[editar] Enlaces externos

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" mathmistakes
• Algoritmos eficientes para calcular números primos, por Steve Litt
• ¿Es este número primo?
• nombres premiers