El Teorema Fundamental de la Aritmética es una de esas joyitas que los matemáticos han conocido por tanto tiempo, pero que los computólogos hemos aprovechado extensivamente, principalmente en el campo de la criptografía.

El teorema dice lo siguiente:

Todo $n \in \mathbb{Z}$ tal que $n > 1$, puede expresarse como el producto de uno o más primos de manera única.

En palabras un poco más simples. Elige el número entero que tú quieras (es entero, no puede tener decimales: 8 es válido, 8.01 no es válido), con la única condición de que debe ser mayor que 1. Ese número que elegiste, es un primo, o es el resultado de multiplicar primos. Además, solo hay una forma única de obtener ese número al multiplicar números primos.

Antes de pasar a realizar la demostración formal del teorema, veamos un ejemplo. Tomemos un número cualquiera: 3785. Según este teorema, podemos tomar números primos ($2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots$), y va a haber una única forma de multiplicarlos que nos va a dar como resultado 194.

Lo anterior se puede calcular utilizando un método que probablemente recuerdas de la primaria: factorización. Como un breve recordatorio, la factorización se realiza dividiendo un número repetidamente entre ciertos factores primos hasta llegar a 1, siempre y cuando la división nos de un número entero (no puede haber residuo).

El proceso en este caso sería: $$\begin{aligned} 3780 / 5 &= 756 & \text{(obtenemos el primer factor primo, 5)} \\ 756 / 2 &= 378 & \text{(obtenemos el factor 2)} \\ 378 / 2 &= 189 & \text{(obtenemos el factor 2, otra vez)} \\ 189 / 3 &= 63 & \text{(obtenemos el factor 3)} \\ 63 / 3 &= 21 & \text{(obtenemos el factor 3, de nuevo)} \\ 21 / 3 &= 7 & \text{(igual obtenemos el factor 3)} \\ 7 / 7 &= 1 & \text{(obtenemos el factor 7, y terminamos)}\end{aligned}$$

Entonces, veamos los factores que obtuvimos del número $3780$. Tenemos $5, 2, 2, 3, 3, 3, 7$. Luego, sabemos que $2 \cdot 2 = 2^{2}$, y de forma más general $n \cdot \dots \cdot n = n^{m}$ donde $m$ es el número de veces que multiplicamos el número $n$. Por lo tanto, agrupamos los factores y tenemos que: $$ 3780 = 2^{2} \cdot 3^{3} \cdot 5 \cdot 7 $$

Y eso es básicamente lo que dice el Teorema fundamental de la aritmética: que el 3780 puede ser factorizado, y que solo existe la factorización anterior.

Demostración

Ya vimos un ejemplo de una factorización. Sin embargo, mostrar un ejemplo para un número no nos garantiza que todos los números tienen una factorización. Además, ¿cómo sabemos que el 3780 no puede factorizarse de alguna otra manera? Para eso, necesitamos una demostración.

En realidad necesitamos dos demostraciones, una para probar que todos los enteros mayores que 1 tienen una factorización, y otra para probar que esa factorización es única.

Demostración de existencia

Primero, demostraremos que todo $n \in \mathbb{Z}, n > 1$ tiene una factorización en números primos.

Realizaremos una demostración por contradicción, es decir, suponemos que existe algún número que no tiene una factorización en primos, y vamos a llegar a algo contradictorio.

Entonces, suponiendo que no todos los números enteros mayores que 1 cumplen lo anterior, podemos tomar el número más pequeño que no puede ser factorizado en primos, diremos que ese número es $n$.

Sabemos que $n$ no es un número primo, porque si fuera primo, su factorización en primos sería $n = 1 \cdot n$, y ya dijimos que $n$ no tiene una factorización en primos.

También sabemos que $n = rs$ donde $1 < r < n, 1 < s < n$. Es decir, existen dos números que multiplicados, nos dan $n$. ¿Cómo sabemos lo anterior? Pues porque los números primos son los únicos que no tienen divisores además de sí mismos y 1, y ya vimos que $n$ no es primo.

Recordemos que $n$ era el contraejemplo más pequeño que existe. Entonces, $r$ y $s$ sí son factorizables en primos, porque son más pequeños que $n$. Utilizando notación, tenemos que: $$ r = p_{1}p_{2} \dots p_{a} $$ $$ s = q_{1}q_{2} \dots q_{b} $$

donde los $p$ y $q$ son números primos.

Y ya alcanzamos nuestra contradicción. Porque si $n = rs$, entonces: $$ n = p_{1}p_{2} \dots p_{a}q_{1}q_{2} \dots q_{b} $$

Es decir, multiplicamos la factorización de $r$ y $s$, y tenemos la factorización de $n$, cuando dijimos que $n$ no tenía factorización.

El error vino de pensar que existía un número que no tenía una factorización.

Demostración de unicidad

Ya vimos que todos los enteros mayores que 1 tienen al menos una factorización como números primos. Ahora falta demostrar que solo tienen una factorización. La demostración, igual que la anterior, será por contradicción.

Tomemos un número mayor que 1, digamos que es $n$. Por la demostración anterior, sabemos que $n$ tiene al menos una factorización: $$ n = p_{1}p_{2} \dots p_{j} $$

Para ver que la factorización es única, sin pérdida de generalidad, supongamos que en realidad hay dos factorizaciones (si encontramos un error al suponer que existen dos factorizaciones, tampoco pueden haber más de 2). La segunda factorización será: $$ n = q_{1}q_{2} \dots q_{k} $$

Notemos que en una factorización $n$ tiene $j$ factores, y en la otra $n$ tiene $k$. Supongamos que $j \leq k$. Si $j > k$, la demostración es análoga (es decir, es la misma demostración, simplemente invirtiendo $j$ por $k$).

También sabemos que $n=n$ (obvio, ¿no?). Por lo tanto: $$ p_{1}p_{2} \dots p_{j} = q_{1}q_{2} \dots q_{k} $$

Como $p_{1}$ es un factor de $n$, sabemos que $p_{1} \vert n$ (léase “$p_{1}$ divide a $n$”). Entonces sabemos que: $$ p_{1} \vert q_{1}q_{2} \dots q_{k} $$

Por lo tanto, $p_{1} = q_{l}$ para alguna $1 \leq l \leq k$. Esto es porque los primos solo se dividen entre sí mismos y entre 1. Luego, sin pérdida de generalidad, diremos que $p_{1} = q_{1}$. Entonces, como son el mismo número, podemos cancelarlos y nos queda: $$ p_{2} \dots p_{j} = q_{2} \dots q_{k} $$

Luego, realizaremos un proceso iterativo; es decir, realizamos el paso anterior varias veces.

Finalmente, como $j \leq k$, sabemos que sucede uno de los dos siguientes casos:

  1. Si $j=k$, entonces terminamos el proceso iterativo y resultó que todos los $p_{i} = q_{i}$, entonces la factorización ¡es única! Esto fue una contradicción, porque supusimos que $n$ tenía dos factorizaciones distintas.

  2. Si $j<k$, entonces tenemos que: $$ 1 = \dots q_{k-2}q_{k-1}q_{k} $$

Y por lo tanto, los $q$ restantes son $1$ o $-1$, pues esos son los únicos números que pueden ser multiplicados para ser igual que $1$. Entonces, los podemos despreciar y removerlos de la factorización, pues no afectan el resultado. Y nuevamente tenemos que la factorización ¡es única! Nuevamente, una contradicción pues supusimos que las factorizaciones eran distintas.

Las contradicciones en ambos casos, vienen de suponer que la factorización no era única.

Con las dos demostraciones anteriores, queda demostrado el Teorema Fundamental de la Aritmética que nos dice que todo número entero mayor que 1 tiene una factorización única en números primos.

Pero, ¿cuál es la importancia del teorema? Este blog va enfocado a programadores, entonces te daré la conclusión más importante en nuestra área: criptografía.

En criptografía la idea es transformar información de manera que la única forma de desencriptarla sea con la llave correcta (pues no queremos que algo se pueda desencriptar con varias llaves, ¿cuál sería el punto de encriptarlo?) y que además, sea difícil de obtener para alguien que no tiene la clave correcta.

La complejidad de desencriptar la información corresponde a otro campo de estudio, pero el que la llave sea única es gracias al teorema fundamental de la aritmética. Y esto es porque las llaves que utilizan los buenos protocolos de encriptación se basa en el uso de números primos. Si tienes la factorización en primos correcta (y única) de un número, puedes desencriptar la información, si no, cualquier otra llave va a fallar.

Y este es el concepto que vemos aplicado en protocolos como https, que cifra nuestras comunicaciones a través de la web, con el que todos los desarrolladores estamos familiarizados.

¿Quieres ver otro teorema interesante a partir de este teorema? ¿Sabes cuántos números primos existen? ¿Hay un número primo mayor que todos los demás? Puedes revisar mi post anterior: Demostración: Existe una cantidad infinita de números primos.