Números Primos y la Criba de Eratóstenes

Descubre por qué los primos son los ladrillos fundamentales de todos los enteros.

Estudiar en la plataforma interactiva
Módulo 5 · Teoría de Números

Cuarenta aciertos y un error

Le preguntas a un compañero, o a un chat de inteligencia artificial, y te responde con seguridad: «n2+n+41n^2 + n + 41 es primo para todo natural nn; lo comprobé de 0 a 30». Y es verdad que da primos en todos esos casos: 41, 43, 47, 53, 61… Sigue dando primos hasta n=39n = 39.

Pero con n=40n = 40 da 1 600+40+41=1 681=41⋅411\,600 + 40 + 41 = 1\,681 = 41 \cdot 41, que no es primo. Muchos ejemplos no demuestran nada sobre infinitos números. Para saber si un número es primo hace falta un método, y el más antiguo es una criba.

Momento animado

La criba de Eratóstenes

Cada primo tacha sus múltiplos. Mira desde dónde empieza cada uno y por qué basta llegar al 7.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100tachando múltiplos de 2, desde 4
primo 2
Etapas

Etapa 1 de 5 · El 2

El 1 no es primo. El 2 sí: se encierra y se tachan sus múltiplos, 4, 6, 8… Ningún par mayor que 2 puede ser primo.

¿Qué es un número primo?

Un entero p>1p > 1 es primo si sus únicos divisores positivos son 11 y pp. Si tiene más divisores, es compuesto.

Los primeros primos son: 2,3,5,7,11,13,17,19,23,29,31,...2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Errores Comunes en Olimpiadas

  • • 1 NO es primo — Tiene solo un divisor, no dos.
  • • 2 es el ÚNICO primo par — Todo otro par se divide entre 2.
  • • No todos los impares son primos — 9, 15, 21, 25... son compuestos.

¿Por qué importan en olimpiadas? Porque el Teorema Fundamental de la Aritmética dice que los primos son los "átomos" de los enteros:

El Teorema Fundamental de la Aritmética

Teorema Fundamental

Todo entero n>1n > 1 se puede escribir como producto de primos de manera única (salvo el orden):

n=p1a1⋅p2a2⋯pkakn = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}

Ejemplo: Factorizar 2520

1

Dividir por 2

2520=2×12602520 = 2 \times 1260
2

Seguir con 2

1260=2×630=2×2×3151260 = 2 \times 630 = 2 \times 2 \times 315
3

Dividir por 3 (315 no es par)

315=3×105=3×3×35315 = 3 \times 105 = 3 \times 3 \times 35
4

Dividir por 5

35=5×735 = 5 \times 7
5

7 es primo. ¡Listo!

2520=23×32×5×72520 = 2^3 \times 3^2 \times 5 \times 7

Fórmulas Útiles (a partir de la factorización)

Si n=p1a1⋯pkakn = p_1^{a_1} \cdots p_k^{a_k}, entonces:

Cantidad de divisores:

τ(n)=(a1+1)(a2+1)⋯(ak+1)\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)

Suma de divisores:

σ(n)=∏i=1kpiai+1−1pi−1\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1}-1}{p_i-1}

Ejemplo: τ(2520)=(3+1)(2+1)(1+1)(1+1)=48\tau(2520) = (3+1)(2+1)(1+1)(1+1) = 48 divisores.

Concepto Clave

"La factorización prima es ÚNICA. Esto permite pasar de preguntas sobre divisibilidad a preguntas sobre exponentes."

La Criba de Eratóstenes

El método más elegante para encontrar primos fue inventado por Eratóstenes de Cirene hace más de 2200 años. Es simple pero poderoso:

  1. Escribe todos los números de 2 hasta NN.
  2. El primer número no tachado es primo: márcalo y tacha todos sus múltiplos.
  3. Repite hasta que el siguiente primo sea mayor que N\sqrt{N}.
  4. Todos los que sobreviven son primos.

Criba de Eratóstenes Interactiva

Observa cómo la criba elimina los compuestos hasta encontrar todos los primos ≤ 120.

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
Primo
Cribando...
Eliminado

¿Por qué solo hasta N\sqrt{N}? Si nn es compuesto y n≤Nn \leq N, entonces nn tiene un factor primo p≤n≤Np \leq \sqrt{n} \leq \sqrt{N}.

Concepto Clave

"La criba verifica primalidad probando divisores solo hasta √N. Si un número sobrevive todas las pruebas hasta √N, es primo."

Problemas de Olimpiada

Infinitud de los primos (Euclides)

Al suponer una lista finita de primos {p1,…,pn}\{p_1, \ldots, p_n\} y definir N=p1⋯pn+1N = p_1 \cdots p_n + 1, ¿cuál es el núcleo de la contradicción?

Contando Divisores

¿Cuántos divisores positivos tiene el número 10!10!?

Argumentación · Ejemplos y demostración
Alguien afirma que n2+n+41n^2 + n + 41 es primo para todo natural nn, porque lo comprobó de n=0n = 0 a n=30n = 30. ¿Qué pasa con n=40n = 40?
Práctica · ¿Es primo?
¿Es primo el 91?
Práctica · Hasta la raíz
Para saber si 221 es primo, ¿hasta qué primo basta probar?