Descomposición en Factores Primos
La descomposición en factores primos es el proceso de expresar un número compuesto como el producto de sus factores primos.
Formula
n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}
Definition
La descomposición en factores primos consiste en desglosar un número en números primos que multiplicados dan como resultado ese número, dividiendo repetidamente hasta que cada pieza sea prima. Formalmente, la factorización prima de $n$ es su representación única como producto de potencias de primos, $n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$, garantizada su existencia y unicidad (salvo el orden) por el Teorema Fundamental de la Aritmética. Esta unicidad no es obvia: requiere demostrar que si $p \mid ab$ entonces $p \mid a$ o $p \mid b$, lo cual depende de la identidad de Bézout y por tanto del algoritmo de Euclides; en un UFD, la misma unicidad se cumple para elementos irreducibles de manera más general.
Example
Factorización prima de $36$: $36 = 2 \times 18 = 2 \times 2 \times 9 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$. La factorización prima de $360 = 2^3 \times 3^2 \times 5$ se puede usar para hallar $\text{GCF}(360, 84)$, ya que $84 = 2^2 \times 3 \times 7$ da $\text{GCF} = 2^2 \times 3 = 12$. La factorización de enteros es computacionalmente difícil en general: el mejor algoritmo clásico conocido (la criba general del cuerpo de números) se ejecuta en tiempo subexponencial $\exp(O(n^{1/3}))$, mientras que el algoritmo cuántico de Shor factoriza en tiempo polinómico, amenazando a RSA.
Key Insight
Un árbol de factores es una herramienta útil: ramifica en dos factores cualesquiera, y luego sigue ramificando cada factor hasta que todas las ramas sean números primos. Todo cálculo de MCD y todo cálculo de MCM es en secreto un problema de factorización prima: el MCD usa el exponente mínimo para cada primo, el MCM usa el máximo.