Números primos

Definición

Un número primo es un número natural mayor que 1 que tiene exactamente dos divisores positivos: 1 y sí mismo. Los números que tienen más de dos divisores se llaman compuestos.

Propiedades fundamentales

• El número 1 no es primo ni compuesto.
• El número 2 es el único primo par.
• Todo número compuesto puede expresarse como producto de primos (Teorema Fundamental de la Aritmética).

Criba de Eratóstenes

Algoritmo para encontrar todos los primos menores que un número dado:

1. Escribir la lista de números desde 2 hasta N.
2. Tachar los múltiplos de cada primo comenzando por el 2.
3. Los números no tachados al final son primos.

Teorema Fundamental de la Aritmética

Todo número entero mayor que 1 se puede representar de manera única como producto de números primos (ignorando el orden). Ejemplo: (360 = 2^3 \times 3^2 \times 5).

Infinitud de los primos

Euclides demostró que existen infinitos números primos. La demostración clásica supone una lista finita y construye un número nuevo que no es divisible por ninguno de ellos.

Primos gemelos

Son pares de primos que difieren en 2, como (3,5), (11,13), (17,19). Se desconoce si hay infinitos pares de primos gemelos (Conjetura de los primos gemelos).

Distribución aproximada

El teorema de los números primos establece que la cantidad de primos menores que (x) es aproximadamente (\frac{x}{\ln x}). Para (x = 10^6), hay alrededor de 78,498 primos.

Primos famosos

• Primo de Mersenne: de la forma (2^p - 1), donde (p) es primo. Los más grandes conocidos son de este tipo.
• Primo de Fermat: de la forma (2^{2^n} + 1), solo se conocen 5 primos de Fermat.

Criptografía

Los números primos son esenciales en criptografía RSA, que se basa en la dificultad de factorizar grandes números compuestos.

Ejercicio rápido

Determinar si 97 es primo. Verificar divisibilidad por primos menores que (\sqrt{97} \approx 9.8): 2,3,5,7. Ninguno divide a 97, por lo tanto es primo.