Fundamental theorem of arithmetic

Statement and examples

The formal statement has two parts: existence and uniqueness. Existence means each integer greater than 1 can be written as a product of primes (possibly a single prime). Uniqueness means that if n = p1 p2 ... pr = q1 q2 ... qs with all p_i and q_j prime, then r = s and, after reordering, p_i = q_i for every i. Common examples illustrate the idea: 1200 = 2^4 · 3 · 5^2 and 6936 = 2^3 · 3 · 17^2. If anyone presents a different factorization of these numbers into primes, the lists of primes can be rearranged to match the above decompositions.

Proof outline and key ideas

Existence is usually shown by induction or by iteratively dividing an integer by a smallest prime divisor until only primes remain. Uniqueness rests on a fundamental lemma attributed to Euclid: if a prime divides a product ab, then it divides a or it divides b. Using this property repeatedly shows that any prime appearing in one factorization must appear in every factorization, with at least the same multiplicity. Together these arguments prove that prime factorizations are unique up to order.

Consequences and applications

The theorem underlies many elementary arithmetic constructions. Greatest common divisors and least common multiples can be computed directly from prime exponents: for n = ∏ p^a_p and m = ∏ p^b_p, gcd(n,m) = ∏ p^{min(a_p,b_p)} and lcm(n,m) = ∏ p^{max(a_p,b_p)}. The theorem also explains why multiplicative arithmetic functions (like the divisor function or Euler's totient) factor naturally across primes. In modern applications, the practical difficulty of factoring large integers into primes is exploited in public-key cryptography, where security depends on the gap between the ease of multiplying primes and the hardness of reversing the process.

Generalizations and notable facts

While the integers form a domain with unique factorization, not all rings share this property. Algebraic number theory studies rings in which unique factorization can fail; this led to the concept of unique factorization domains (UFDs) and to the development of ideal factorization. Historically the theorem traces to ancient Greek mathematics and was given clear proofs by Euclid; later work formalized the primes, divisibility properties, and proofs used today. The restriction that 1 is not prime and is treated as a unit is important: uniqueness is stated up to multiplication by units (±1 in the integers) and permutation of the prime factors.

Further reading and resources

• Formal statements and proofs
• Context within number theory
• Definitions of integers and primes
• Multiplicative structure of integers
• Prime numbers and their properties
• Algorithms for factorization
• Applications in cryptography