Prime Factorization
Prime factorization is the process of expressing a composite number as a product of its prime factors.
Formula
n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}
Definition
Prime factorization means breaking a number down into prime numbers that multiply together to make it, dividing repeatedly until every piece is prime. Formally, the prime factorization of $n$ is its unique representation as a product of prime powers, $n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}$, guaranteed to exist and be unique (up to ordering) by the Fundamental Theorem of Arithmetic. This uniqueness is not obvious: it requires proving that if $p \mid ab$ then $p \mid a$ or $p \mid b$, which depends on Bezout's identity and hence on the Euclidean algorithm; in a UFD, the same uniqueness holds for irreducible elements more generally.
Example
Prime factorization of $36$: $36 = 2 \times 18 = 2 \times 2 \times 9 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$. Prime factorization of $360 = 2^3 \times 3^2 \times 5$ can be used to find $\text{GCF}(360, 84)$, since $84 = 2^2 \times 3 \times 7$ gives $\text{GCF} = 2^2 \times 3 = 12$. Integer factorization is computationally hard in general: the best known classical algorithm (general number field sieve) runs in sub-exponential time $\exp(O(n^{1/3}))$, while Shor's quantum algorithm factors in polynomial time, threatening RSA.
Key Insight
A factor tree is a helpful tool: branch off any two factors, then keep branching each factor until all branches are prime numbers. Every GCF calculation and every LCM calculation is secretly a prime factorization problem: GCF uses the minimum exponent for each prime, LCM uses the maximum.