Números primos: Propiedades, criba y aplicaciones

Definición formal

Un número primo es un número natural mayor que 1 que tiene exactamente dos divisores positivos distintos: el 1 y sí mismo. Los números naturales mayores que 1 que no son primos se denominan compuestos.

• El número 1 no es primo ni compuesto.
• El 2 es el único número primo par.
• Los primeros primos son: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Teorema fundamental de la aritmética

Todo número natural mayor que 1 puede expresarse de manera única como producto de números primos (salvo el orden de los factores). Esta factorización es la base de muchas aplicaciones en aritmética.

Ejemplo: \(360 = 2^3 \cdot 3^2 \cdot 5\)

La criba de Eratóstenes

Método clásico para encontrar todos los números primos menores que un cierto límite (n).

1. Se escribe la lista de números desde 2 hasta (n).
2. Se toma el primer número no tachado (2) y se tachan todos sus múltiplos mayores que él.
3. Se repite con el siguiente número no tachado (3, 5, 7...).
4. El proceso termina cuando el cuadrado del número considerado supera (n). Los números que quedan sin tachar son primos.

Infinitud de los números primos

Teorema de Euclides: no hay una cantidad finita de números primos. Demostración clásica:

• Supongamos que hay finitos primos (p_1, p_2, \dots, p_k).
• Considérese (N = p_1 p_2 \cdots p_k + 1).
• (N) no es divisible por ninguno de los primos conocidos, luego o bien es primo o tiene un factor primo nuevo. Contradicción.

Criterios de primalidad básicos

Para verificar si un número (n) es primo, basta comprobar si es divisible por algún primo (p) tal que (p^2 \le n).

• Si no se encuentra ningún divisor, (n) es primo.
• Ejemplo: para (n = 97), solo hay que probar primos menores o iguales a (\sqrt{97} \approx 9.8), es decir, 2, 3, 5, 7.

Distribución aproximada

El teorema de los números primos establece que la cantidad de primos menores que (x), denotada (\pi(x)), se aproxima a (x / \ln(x)) para valores grandes de (x). Esto implica que los primos se vuelven más escasos a medida que crecen, pero nunca desaparecen.

Aplicaciones importantes

• Criptografía: el algoritmo RSA se basa en la dificultad de factorizar números grandes que son producto de dos primos grandes.
• Divisibilidad: la factorización en primos permite calcular el MCD y el mcm de forma eficiente.
• Matemáticas discretas: los primos se usan en generadores pseudoaleatorios y en teoría de códigos.

Errores comunes a evitar

• Confundir 1 como primo (no lo es).
• Creer que todos los impares son primos (contraejemplo: 9, 15, 21...).
• Olvidar que 2 es primo y es el único primo par.
• Pensar que si un número no es divisible por los primeros primos pequeños, entonces es primo (hay que probar hasta (\sqrt{n})).

Resumen rápido

• Primo: exactamente dos divisores.
• Factorización única.
• Criba de Eratóstenes para listarlos.
• Infinitos primos (Euclides).
• Prueba de divisibilidad hasta (\sqrt{n}).
• Distribución aproximada: (\pi(x) \sim x/\ln x).