Números primos: los ladrillos de la aritmética

Un número primo es un entero > 1 divisible solo por 1 y por sí mismo. Primeros 20: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

El número 1 no es ni primo ni compuesto por convención matemática.

Teorema fundamental de la aritmética

Todo entero > 1 se expresa de manera única (salvo orden) como producto de primos. Demostrado por Euclides (~300 a.C.) en Elementos.

n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k

Ejemplos: 12 = 2² × 3, 360 = 2³ × 3² × 5, 1001 = 7 × 11 × 13.

Criba de Eratóstenes

Algoritmo antiguo (Eratóstenes de Cirene, ~240 a.C.):

1. Escribir números de 2 a n
2. El menor no tachado es primo: tachar sus múltiplos
3. Repetir con siguiente primo
4. Detenerse cuando primo > √n

Complejidad: O(n log log n).

Tests de primalidad

• División de prueba: O(√n), hasta ~10⁹
• Miller-Rabin: probabilístico, determinista hasta 3,3 × 10¹⁴
• AKS (2002): primer algoritmo determinista polinomial
• ECPP: certificación primos gigantes

Teorema de los números primos

Hadamard y de la Vallée Poussin (1896 independientemente):

π(n) ~ n / ln(n)

Densidad primos: 25% hasta 100, 16,8% hasta 1.000, 7,85% hasta 1.000.000.

Demostración infinitos primos (Euclides)

Supón finitos: p₁, ..., p_n. Considera N = p₁·p₂·...·p_n + 1. N no divisible por ningún p_i. Contradicción → infinitos primos. QED ~300 a.C.

Primos famosos

Primos de Mersenne

M_p = 2^p − 1. Mayor conocido (2024): 2^136.279.841 − 1, ~41 millones cifras. Proyecto GIMPS.

Primos de Fermat

F_n = 2²ⁿ + 1. Fermat (1640) conjeturó todos primos. Euler (1732) encontró F₅ compuesto = 641 × 6.700.417. Solo F₀..F₄ conocidos primos.

Primos gemelos

Pares (p, p+2): (3,5), (5,7), (11,13), (17,19), (29,31).

Conjetura abierta: infinitos pares. Zhang 2013 redujo a distancia < 70 millones, luego Polymath a < 246.

Primos Sophie Germain

p primo con 2p+1 también primo. Usados en criptografía.

Criptografía y primos

RSA (1977)

Claves pública y privada basadas en dos primos ~300-600 cifras. Descifrar requiere factorizar n = p·q, computacionalmente infactible.

RSA-2048 seguridad actual. RSA-1024 roto 2019.

Amenaza cuántica

Algoritmo Shor (1994) factoriza en tiempo polinomial. NIST estandarizando criptografía post-cuántica.

Funciones aritméticas

Función φ de Euler

Enteros 1..n coprimos con n. φ(n) = n·Π(1 − 1/p)

φ(10) = 4 (1, 3, 7, 9). φ(p) = p − 1 para p primo.

Teorema Euler: si gcd(a,n)=1, a^φ(n) ≡ 1 (mod n). Base criptografía.

Función σ divisores

Suma divisores positivos. σ(12) = 28.

Números perfectos

Igual a suma divisores propios: 6, 28, 496, 8128, 33.550.336. Euler: par perfecto ⇔ 2^p-1(2^p−1) con Mersenne primo. Impares: problema abierto.

Números amigos

(a, b) con σ(a)−a = b y σ(b)−b = a. Primeros: (220, 284), (1184, 1210), (2620, 2924).

Conjeturas abiertas célebres

Goldbach (1742)

Todo par > 2 = suma de dos primos. Verificado hasta 4 × 10¹⁸.

Hipótesis Riemann (1859)

Ceros no triviales función zeta con parte real 1/2. Premio Millennium: $1M.

Primos gemelos

Infinitas parejas.

Legendre

Siempre primo entre n² y (n+1)².

Mayor primo conocido

Octubre 2024: 2^136.279.841 − 1, 41 millones cifras, 51° Mersenne, encontrado Luke Durant vía GIMPS.

Algoritmos avanzados factorización

• Pollard rho: O(n^1/4)
• Quadratic Sieve: hasta 10¹⁰⁰
• Number Field Sieve: L(1/3). Rompió RSA-768 en 2009
• Shor cuántico: polinomial (amenaza futura RSA)

Aplicaciones modernas

• Criptografía (RSA, Diffie-Hellman, ECC)
• PRNG seguros (Blum Blum Shub)
• Hash functions (universal hashing)
• Reed-Solomon (CD, QR, DVB)
• Computación distribuida (GIMPS)

Ejemplos

Factorización 360

360 = 2³ × 3² × 5. Divisores: 24 total.

Carmichael 561

561 = 3 × 11 × 17. Compuesto pero pasa test Fermat. Pseudo-primo fuerte.

Primalidad 1.000.003

√1M ≈ 1000. Sin divisores ≤ 1000 → primo.

Python

from sympy import isprime, primerange, factorint, primepi
isprime(1000003)  # True
factorint(360)    # {2: 3, 3: 2, 5: 1}
primepi(10**6)    # 78498

Errores comunes

• 1 no es primo (convención)
• 2 par y primo: el único
• RSA con claves < 2048 obsoleto

FAQ

¿Por qué 1 no es primo?

Convención para mantener unicidad factorización.

¿Primos gemelos infinitos?

Conjetura abierta. Progreso Zhang 2013.

¿RSA seguro?

Sí, 2048+ bits. Amenaza: cuánticos.

¿Cuántos primos hasta 10⁶?

78.498. Aprox 1 de cada 12-13.

Propiedades matemáticas notables

Pequeño teorema de Fermat

Si p es primo y gcd(a, p) = 1, entonces a^p-1 ≡ 1 (mod p). Caso especial del teorema de Euler cuando n es primo.

Ejemplo: 2⁶ = 64 ≡ 1 (mod 7), verificable: 64 = 9·7 + 1.

Teorema de Wilson

p es primo si y sólo si (p-1)! ≡ −1 (mod p). Demostrado por Lagrange 1771.

Ejemplo: p=5, (5-1)! = 24 = 5·5 − 1, entonces 24 ≡ −1 (mod 5).

Congruencia de Gauss

Si p es primo impar, entonces 2^(p-1)/2 ≡ ±1 (mod p), con +1 si 2 es residuo cuadrático mod p.

Primos en literatura y cultura

• Contact (Carl Sagan, 1985): mensaje alienígena basado en primer primi
• Teorema dei numeri primi: menzionado en The Curious Incident of the Dog in the Night-Time
• Cicada 3301: puzzle criptografico internet che usa teoría de números
• La soledad de los números primos (Paolo Giordano, 2008): novela premiada

Cicadas y primos

Cicadas del género Magicicada emergen cada 13 o 17 años (ambos primos!). Teoría evolutiva: ciclos primos reducen coincidencia con depredadores y parásitos también ciclicos.

Si depredador ciclo 2, 3 años: cicada ciclo 13 años solo coincide cada 26 y 39 años. Cicada ciclo 12 coincidiría cada 12 años con ambos.

Ejemplo fascinante de matemática en selección natural.

Distribución de primos y zeta de Riemann

La función zeta de Riemann ζ(s) = Σ 1/n^s está profundamente conectada a la distribución de primos por la identidad de Euler:

ζ(s) = Π_{p primo} 1/(1 − p^−s)

Los ceros no triviales de ζ controlan las fluctuaciones de π(n) respecto al teorema de los números primos. La hipótesis de Riemann (todos los ceros no triviales tienen parte real 1/2) implicaría la máxima regularidad posible en la distribución de primos.

Demostrada: haría colapsar numerosos teoremas de teoría analítica de números que actualmente la asumen como hipótesis.

Actualizado a julio de 2026