Prime Factorization
ArithmeticPrime 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. You keep dividing until all pieces are prime.
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$.
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.
Definition
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}$. The Fundamental Theorem of Arithmetic guarantees this factorization exists and is unique (up to ordering).
Example
Prime factorization of $360$: $360 = 8 \times 45 = 2^3 \times 9 \times 5 = 2^3 \times 3^2 \times 5$. Used to find $\text{GCF}(360, 84)$: $84 = 2^2 \times 3 \times 7$; $\text{GCF} = 2^2 \times 3 = 12$.
Key Insight
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.
Definition
The Fundamental Theorem of Arithmetic states: every integer $n > 1$ has a unique factorization into primes (in $\mathbb{Z}$, up to order and sign of primes). In a UFD, this uniqueness holds for irreducible elements. The factorization is the basis for the ring isomorphism $\mathbb{Z} \sim \prod_p \mathbb{Z}_p$ over primes $p$ of the $p$-adic integers (Chinese Remainder Theorem at a local level).
Example
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}))$. Shor's quantum algorithm factors in polynomial time, threatening RSA.
Key Insight
The uniqueness of prime factorization is NOT obvious. It requires proving that if $p \mid ab$ then $p \mid a$ or $p \mid b$ (prime implies irreducible in $\mathbb{Z}$), which depends on Bezout's identity and hence on the Euclidean algorithm.