Fundamental Theorem of Arithmetic

Number Theory · Axiom Academy

LESSON Fundamental Theorem of Arithmetic The cornerstone of number theory: every integer has a unique prime factorization The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of prime numbers, and this representation is unique up to the order of the factors. Fundamental Theorem of Arithmetic where p₁, p₂, ..., pₖ are distinct prime numbers, a₁, a₂, ..., aₖ are positive integers, and this representation is unique up to the ordering of factors. Existence: Every integer n > 1 can be written as a product of primes. Uniqueness: This prime factorization is unique (except for the order of factors). We prove existence using strong induction . The key idea is that every composite number can be broken down into smaller factors, and we can apply induction to those factors. Base case: For n = 2, we have 2 = 2, which is already prime. Inductive step: Assume the theorem holds for all integers 2 ≤ m < n. We must show it holds for n. Case 1: If n is prime, then n is its own prime factorization. Case 2: If n is composite, then n = ab where 2 ≤ a, b < n. By the inductive hypothesis, both a and b have prime factorizations. Combining these factorizations gives a prime factorization of n. 3. Proving Uniqueness: Euclid's Lemma The uniqueness part is more subtle and requires a key lemma known as Euclid's Lemma . In other words: if a prime divides a product, it must divide at least one of the factors.

This is the written version of the interactive lesson above. See the full Number Theory course.