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
Modulo 5 · Teoría de Números

¿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. Táchalo y elimina 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

Problema 1Clásico

Infinitud de los primos

Demuestre que hay infinitos números primos. (Demostración de Euclides)

Ver Demostración

Supongamos que solo hay un número finito de primos: p1,p2,…,pnp_1, p_2, \ldots, p_n.

Construimos N=p1p2⋯pn+1N = p_1 p_2 \cdots p_n + 1.

Ningún pip_i divide a NN, pues al dividir NN entre pip_i siempre sobra 1.

Pero N>1N > 1, así que tiene algún factor primo... ¡que no está en nuestra lista!

Contradicción. Los primos son infinitos. ∎
Problema 2Nivel Nacional

Contando Divisores

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

Ver Solución

Paso 1: Factorizar 10!10!.

10!=28×34×52×710! = 2^8 \times 3^4 \times 5^2 \times 7

Paso 2: Usar la fórmula τ(n)=(a1+1)(a2+1)⋯\tau(n) = (a_1+1)(a_2+1)\cdots

τ(10!)=(8+1)(4+1)(2+1)(1+1)=9×5×3×2=270\tau(10!) = (8+1)(4+1)(2+1)(1+1) = 9 \times 5 \times 3 \times 2 = 270