Prime Factorization
Fundamental Theorem
Every integer n>1 can be written uniquely as \(n=p_1^{{a_1}}p_2^{{a_2}}\cdots p_k^{{a_k}}\) (up to order).
Examples
Example 1. Factor 360.
Solution. 360=2³·3²·5.
In Depth
The Fundamental Theorem of Arithmetic guarantees unique prime factorization. This uniqueness is not automatic — in some rings (e.g., \(\mathbb{Z}[\sqrt{-5}]\)), factorization is not unique, motivating the theory of ideals in algebraic number theory.
Computing the prime factorization of a large integer is believed to be computationally hard (no polynomial-time algorithm is known). The best general-purpose algorithm, the General Number Field Sieve, runs in sub-exponential time \(\exp(O(n^{1/3}(\ln n)^{2/3}))\). This hardness is the security foundation of RSA.
Applications: GCD and LCM are easily computed from prime factorizations. The number of divisors \(\tau(n)=\prod(a_i+1)\) and sum of divisors \(\sigma(n)=\prod(p_i^{a_i+1}-1)/(p_i-1)\) are multiplicative functions of the factorization.
Further Reading & Context
The Fundamental Theorem of Arithmetic guarantees unique prime factorization for every integer \(n>1\). The proof has two parts: existence (by strong induction, every integer either is prime or has a prime factor) and uniqueness (using Euclid's lemma: if \(p\mid ab\) and \(p\) is prime, then \(p\mid a\) or \(p\mid b\)).
Trial division finds factors by testing primes up to \(\sqrt{n}\). For large \(n\), faster algorithms are needed: Pollard's rho algorithm runs in \(O(n^{1/4})\) expected time; the quadratic sieve in \(L_n[1/2]\); the number field sieve (NFS) in \(L_n[1/3]\) — the fastest known classical algorithm.
Smooth numbers (all prime factors \(\leq B\)) are key to factoring algorithms. The NFS collects pairs \((a,b)\) where both \(a+b\sqrt{D}\) and \(a+bm\) are \(B\)-smooth, then uses linear algebra over \(\mathbb{F}_2\) to find a congruence of squares \(x^2\equiv y^2\pmod{n}\), giving a factor \(\gcd(x-y,n)\).
Integer factorization is in NP ∩ co-NP (a factorization is easy to verify) but not known to be in P. Shor's quantum algorithm factors in polynomial time, threatening RSA. This motivates post-quantum cryptography based on problems believed hard even for quantum computers.
Arithmetic functions are defined via prime factorization: \(d(n)=\prod(e_i+1)\), \(\sigma(n)=\prod(p_i^{e_i+1}-1)/(p_i-1)\), \(\phi(n)=n\prod(1-1/p_i)\). These multiplicative functions encode deep properties of the integers and are central to analytic number theory.