Números Primos

Teoría

Un número primo es un entero $p > 1$ cuyos únicos divisores positivos son $1$ y el mismo $p$. A los enteros mayores que $1$ que no son primos los puedes llamar números compuestos. Piensa en los números primos como los bloques de construcción "atómicos" de los enteros. Este concepto lo puedes ver de forma más formal con el Teorema Fundamental de la Aritmética, que dice que cada entero mayor que $1$ lo puedes representar como el producto de números primos de forma única, sin importar el orden de los factores. Como el $2$ es el único número primo par, casi siempre juega un papel especial en argumentos de paridad y problemas de teoría de números que involucran primos.

En las matemáticas de competencia, la factorización prima es tu herramienta principal para resolver problemas de divisibilidad, máximo común divisor (MCD), mínimo común múltiplo (mcm) y cantidad de divisores. Cuando descompones un número en sus factores primos, un problema difícil sobre un entero grande a menudo lo puedes separar en problemas independientes y más sencillos sobre potencias de primos. Por ejemplo, para mostrar que $a$ divide a $b$, basta con que muestres que para cada primo $p$, la potencia de $p$ que divide a $a$ es menor o igual a la potencia de $p$ que divide a $b$.

Otro aspecto crítico de los primos es su distribución y sus propiedades en la aritmética modular. Aunque no hay una fórmula simple para generar el $n$-ésimo primo, técnicas como la Criba de Eratosthenes te permiten determinar eficientemente los primos hasta cierto límite. En problemas avanzados (AIME/Olimpiada), vas a usar seguido propiedades como el Pequeño Teorema de Fermat y la valuación de primos en factoriales (Fórmula de Legendre) para determinar residuos o la cantidad de ceros al final de un número grande.

Fórmulas Clave

1. Teorema Fundamental de la Aritmética Cada entero $n > 1$ tiene una factorización prima única: $$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ donde $p_1 < p_2 < \dots < p_k$ son primos y $e_i \geq 1$ son enteros positivos.

2. Funciones de Divisores Usa la factorización canónica de arriba:

• Cantidad de divisores $\tau(n)$ (o $d(n)$): $$\tau(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1)$$
• Suma de divisores $\sigma(n)$: $$\sigma(n) = \frac{p_1^{e_1+1}-1}{p_1-1} \cdot \frac{p_2^{e_2+1}-1}{p_2-1} \cdots \frac{p_k^{e_k+1}-1}{p_k-1}$$

3. Lema de Euclid Si un primo $p$ divide al producto de dos enteros $ab$, entonces $p$ tiene que dividir a $a$ o $p$ tiene que dividir a $b$: $$p \mid ab \implies p \mid a \quad \text{o} \quad p \mid b$$

4. Fórmula de Legendre El exponente de la mayor potencia de un primo $p$ que divide a $n!$ (que escribimos como $v_p(n!)$) lo encuentras con esta fórmula: $$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots$$ Nota: La suma es finita porque los términos se hacen cero cuando $p^k > n$.

5. Pequeño Teorema de Fermat Si $p$ es un número primo, entonces para cualquier entero $a$: $$a^p \equiv a \pmod{p}$$ Si $p$ no divide a $a$, esto lo puedes simplificar a: $$a^{p-1} \equiv 1 \pmod{p}$$

Demostración

Teorema: Hay infinitos números primos.

Esta es la demostración clásica de Euclid por contradicción.

Demostración: Supón, para llegar a una contradicción, que hay una cantidad finita de primos. Imagina que este conjunto finito de todos los números primos es $P = {p_1, p_2, \dots, p_n}$, donde $p_1=2, p_2=3$, y así hasta el primo más grande $p_n$.

Ahora considera el entero $N$ que construyes al multiplicar todos estos primos y sumarle $1$: $$N = p_1 p_2 \cdots p_n + 1$$

Como $N > 1$, por el Teorema Fundamental de la Aritmética, $N$ tiene que tener al menos un divisor primo. Toma a $q$ como un factor primo de $N$.

Como el conjunto $P$ contiene todos los números primos, $q$ tiene que ser uno de los primos en el conjunto ${p_1, p_2, \dots, p_n}$. Por lo tanto, $q$ divide al producto $p_1 p_2 \cdots p_n$.

Ahora tienes esto:

1. $q \mid N$ (por la definición de $q$)
2. $q \mid (p_1 p_2 \cdots p_n)$ (ya que $q \in P$)

Si un número divide a dos enteros, también tiene que dividir a su diferencia. Por lo tanto, $q$ debe dividir a: $$N - (p_1 p_2 \cdots p_n) = (p_1 p_2 \cdots p_n + 1) - (p_1 p_2 \cdots p_n) = 1$$

Esto implica que $q \mid 1$. Sin embargo, $q$ es un número primo, así que $q > 1$. Es imposible que un entero mayor que $1$ divida al $1$.

Esta contradicción viene de suponer que el conjunto de primos es finito. Por lo tanto, el conjunto de los números primos tiene que ser infinito. $\square$