Fundamental theorem of arithmetic

Every integer n > 1 can be written as a product of primes, and that factorization is unique except for the order of its factors. Equivalently, each such integer has one prime-power representation n = p₁^a₁ p₂^a₂ ⋯ pₖ^aₖ, where the pᵢ are distinct primes and each exponent aᵢ is a positive integer. For example, 360 = 2³ × 3² × 5. Rearranging the factors does not give a different factorization.

If n > 1 is prime, it is already a product consisting of one prime. If it is composite, write n = ab with integers a and b strictly between 1 and n. Each factor is smaller than n. Repeating this process, or using induction, eventually expresses n as a product of primes: each split replaces a composite integer with smaller positive factors, so the process terminates.

A key ingredient is Euclid's lemma: if a prime p divides a product ab, it must divide a or b. More generally, if p divides a product of several integers, it divides at least one factor. Suppose an integer has two prime factorizations. The first prime in one factorization divides the product in the other, so Euclid's lemma implies it equals one of the primes there. Cancel this common prime from both sides and repeat. All prime factors, including their multiplicities, must match; only their order can differ. Euclid's Elements presents the prime-divisor result in Book VII, Proposition 30, and results about decomposition appear in adjacent propositions.

The factorization of 360 can be written 360 = 2 × 2 × 2 × 3 × 3 × 5 or, in prime-power form, 2³ × 3² × 5. The theorem makes prime factorizations a reliable way to compare integers: a greatest common divisor is obtained by taking the smaller exponent of each prime shared by the numbers, while a least common multiple uses the larger exponent. It also explains why 1 is not classified as prime: if it were, factors of 1 could be inserted indefinitely, contradicting uniqueness.

The theorem concerns ordinary integers; unique factorization does not automatically hold in every number system or algebraic structure. In modern number theory, studying which broader systems have unique factorization is a major topic. Prime factorization also appears in cryptography: RSA public keys include a composite modulus formed from two large primes, and factoring such moduli is related to the security of RSA when it is correctly implemented. The theorem guarantees a unique factorization exists; it does not say that finding the factors of a large number is computationally easy.