El Teorema Fundamental de la Aritmética

¿Por qué los primos son los "átomos" de los enteros?

Cuando los químicos descubrieron que toda materia se construye combinando átomos de la tabla periódica, la química se organizó. Los primos juegan el mismo papel en teoría de números: todo entero mayor que 1 se construye multiplicando primos.

Este hecho —que la descomposición existe y es única— es tan fundamental que lleva el nombre de Teorema Fundamental de la Aritmética (TFA). Sin él, expresiones como "$v_p(n)$" o "el exponente de 7 en $n$" no tendrían sentido único.

Antes de la demostración, fijemos vocabulario. Un entero $p \ge 2$ es primo si sus únicos divisores positivos son $1$ y $p$. Todo entero $\ge 2$ que no es primo se llama compuesto.

Enunciado y demostración de existencia

Teorema Fundamental de la Aritmética: todo entero $n \ge 2$ puede escribirse como producto de primos. Además, esa escritura es única salvo el orden de los factores.

Existencia (por inducción fuerte): base: $n=2$ es primo, listo. Paso inductivo: sea $n \ge 3$ y supongamos que todo entero $k$ con $2 \le k < n$ tiene factorización prima. Si $n$ es primo, es su propio producto de un solo primo. Si $n$ es compuesto, existen $a, b$ con $2 \le a, b < n$ y $n = ab$. Por hipótesis inductiva $a$ y $b$ tienen factorizaciones primas; concatenarlas da una factorización prima de $n$. Fin.

Notar que la existencia es sencilla. La parte difícil es la unicidad, que requiere el Lema de Euclides demostrado en la lección 1.2.

Demostración de unicidad via Lema de Euclides

Unicidad: supongamos que $n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$ son dos factorizaciones primas de $n$ (los primos repetidos se listan con multiplicidad). Demostraremos que $r = s$ y que ambas listas son iguales.

Como $p_1 \mid q_1 q_2 \cdots q_s$ y $p_1$ es primo, el Lema de Euclides (que dice: si un primo divide a un producto entonces divide a alguno de los factores) garantiza que $p_1 \mid q_j$ para algún $j$. Como $q_j$ es primo y $p_1 \ge 2$, se concluye $p_1 = q_j$. Cancelamos $p_1$ de ambas listas y repetimos el argumento con $n/p_1$. Por inducción, las listas coinciden.

Esta demostración muestra con claridad por qué el Lema de Euclides —que depende de la identidad de Bézout— es la pieza clave. La unicidad de la factorización no sería cierta en sistemas numéricos donde ese lema falla (por ejemplo en $\mathbb{Z}[\sqrt{-5}]$, donde $6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$).

Consecuencias: divisores y sus fórmulas

Sea $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Todo divisor positivo $d$ de $n$ tiene la forma $d = p_1^{b_1} \cdots p_k^{b_k}$ con $0 \le b_i \le a_i$. Cada exponente $b_i$ tiene $a_i + 1$ opciones, y las elecciones son independientes, así que el número de divisores es:

$\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$.

Análogamente, la suma de divisores se obtiene sumando $d = p_1^{b_1}\cdots p_k^{b_k}$ sobre todas las elecciones válidas. Como las elecciones son independientes, la suma factoriza:

$\sigma(n) = (1+p_1+p_1^2+\cdots+p_1^{a_1})(1+p_2+\cdots+p_2^{a_2})\cdots(1+p_k+\cdots+p_k^{a_k})$.

Usando la suma de progresión geométrica: $\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1}-1}{p_i-1}$.

Ejemplo: calcula $\tau(720)$ y $\sigma(720)$. Factorizamos: $720 = 2^4 \cdot 3^2 \cdot 5^1$. Entonces $\tau(720) = (4+1)(2+1)(1+1) = 5 \cdot 3 \cdot 2 = 30$. Para $\sigma$: $(1+2+4+8+16)(1+3+9)(1+5) = 31 \cdot 13 \cdot 6 = 2418$.

La valuación p-ádica como lenguaje unificado

Con el TFA en mano, para cada primo $p$ y entero $n \ne 0$ definimos $v_p(n)$ como el exponente de $p$ en la factorización de $n$. Las propiedades esenciales son: $v_p(ab) = v_p(a)+v_p(b)$ y $v_p(a+b) \ge \min(v_p(a), v_p(b))$ (con igualdad si $v_p(a) \ne v_p(b)$).

Este lenguaje convierte muchos problemas olímpicos en aritmética de valuaciones. Por ejemplo: $d \mid n$ equivale a $v_p(d) \le v_p(n)$ para todo primo $p$. Y $\text{mcd}(a,b) = \prod_p p^{\min(v_p(a),v_p(b))}$, $\text{mcm}(a,b) = \prod_p p^{\max(v_p(a),v_p(b))}$.

Memoriza estas dos propiedades: son la gramática del TFA.