Fundamental Theorem of Arithmetic
The theorem that every integer greater than 1 factors uniquely into primes, up to the order of the factors.
The fundamental theorem of arithmetic states that every integer greater than 1 can be written uniquely as a product of primes, up to the order of the factors. For example, 60 = 2² · 3 · 5, and no other combination of primes produces 60. This uniqueness is what makes primes the atoms of the integers.
Existence of a factorization is easy to prove by induction: if n is composite, split it into smaller factors and repeat until all factors are prime. Uniqueness is the deep part. It follows from Euclid's lemma — if a prime divides a product, it divides one of the factors — which itself is proved using the Euclidean algorithm and Bézout's identity. The theorem is not automatic in other number systems: the ring of integers of ℚ(√−5), for example, lacks unique factorization, which is why the proof matters rather than being a formality.
The theorem is the basis of the canonical representation n = p₁a₁ · p₂a₂ · … used throughout number theory. It yields formulas for the number of divisors, the greatest common divisor and least common multiple, and the structure of multiplicative functions, and it underlies the study of the distribution of the primes encoded by the Riemann zeta function.
The practical counterpart of the theorem is that finding the factorization of a large integer is hard: no efficient general algorithm is known, and this difficulty is the foundation of public-key cryptography. The theorem guarantees that the representation exists and is unique — it says nothing about how long it takes to find it.
Tags
factorization mathematics number theory prime numbers