Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic is one of the most elegant and powerful results in all of mathematics. It states that every integer greater than 1 can be written as a product of prime numbers in exactly one way, up to the order of the factors. This theorem underpins much of number theory and explains why primes are often called the 'building blocks' of the integers — just as atoms build molecules, primes build every whole number. The theorem has two parts: existence (every integer greater than 1 has at least one prime factorisation) and uniqueness (no integer can have two genuinely different prime factorisations). Both parts require careful proof and should not be taken for granted. Mathematicians have studied this result since antiquity, and a rigorous proof appears in Euclid's Elements, making it one of the oldest theorems still taught today. Understanding unique prime factorisation unlocks a huge range of topics: finding greatest common divisors (GCD) and least common multiples (LCM), simplifying fractions, proving the irrationality of square roots, and much more. It is also the foundation for modern cryptographic systems such as RSA, which secures internet communications by exploiting the difficulty of factoring large numbers.
- What is a Prime Number?
- Statement of the Theorem
- Existence: Every Integer Has a Prime Factorisation
- Uniqueness: Euclid's Lemma is the Key
- Standard Form and Notation
- Applications: GCD and LCM
What is a Prime Number?
A prime number is an integer p > 1 whose only positive divisors are 1 and itself. Examples: 2, 3, 5, 7, 11, 13, … A composite number is any integer n > 1 that is not prime — it has at least one divisor other than 1 and n. The number 1 is neither prime nor composite by convention, which is precisely what allows unique factorisation to hold.
Statement of the Theorem
Fundamental Theorem of Arithmetic: Every integer n > 1 can be expressed as a product of primes: n = p₁ · p₂ · … · pₖ where each pᵢ is prime. Moreover, this representation is unique up to reordering of the factors. For example, 360 = 2³ · 3² · 5, and there is no other way to write 360 as a product of primes (apart from changing the order).
Existence: Every Integer Has a Prime Factorisation
Proof by strong induction. Base case: n = 2 is prime, so it is its own factorisation. Inductive step: Assume every integer from 2 to n−1 has a prime factorisation. If n is prime, we are done. If n is composite, then n = a · b where 1 < a, b < n. By the inductive hypothesis, both a and b have prime factorisations, so multiplying them gives a prime factorisation of n. By induction, every integer n > 1 has a prime factorisation.
Uniqueness: Euclid's Lemma is the Key
The uniqueness part relies on Euclid's Lemma: If a prime p divides a product ab, then p divides a or p divides b (or both). Using this, suppose n = p₁p₂…pₖ = q₁q₂…qₘ are two prime factorisations. Then p₁ divides q₁q₂…qₘ, so by Euclid's Lemma p₁ must equal some qⱼ. Cancelling p₁ = qⱼ from both sides and repeating the argument shows k = m and the two lists of primes are identical (up to order). Therefore the factorisation is unique.
Standard Form and Notation
Any integer n > 1 can be written in standard form as n = p₁^a₁ · p₂^a₂ · … · pₛ^aₛ, where p₁ < p₂ < … < pₛ are distinct primes and each exponent aᵢ ≥ 1. For example: 1260 = 2² · 3² · 5 · 7. This compact notation makes it easy to compute GCDs and LCMs: GCD(a, b) takes the minimum exponent of each prime; LCM(a, b) takes the maximum.
Applications: GCD and LCM
If a = 2³ · 3 · 5² and b = 2 · 3² · 7, then GCD(a, b) = 2^min(3,1) · 3^min(1,2) · 5^min(2,0) · 7^min(0,1) = 2¹ · 3¹ · 5⁰ · 7⁰ = 6, and LCM(a, b) = 2³ · 3² · 5² · 7 = 6300. Notice GCD(a,b) · LCM(a,b) = a · b, which is a useful identity provable directly from the prime factorisation structure.
The Key Equation
- n — Integer (dimensionless): Any integer greater than 1 to be factorised
- p_i — Prime factor (dimensionless): The i-th distinct prime in the factorisation, listed in increasing order
- a_i — Exponent (dimensionless): The number of times the prime pᵢ appears in the factorisation; must be at least 1
- s — Number of distinct primes (dimensionless): The total count of distinct prime factors of n
Worked Example
Problem. Find the prime factorisation of 2520. Then use it to find GCD(2520, 360) and LCM(2520, 360).
Answer. 2520 = 2³ · 3² · 5 · 7; GCD(2520, 360) = 360; LCM(2520, 360) = 2520
Origins · 1 minCarl Friedrich Gauss and how this was discovered
Gauss gave the first rigorous and complete proof of the Fundamental Theorem of Arithmetic in his landmark 1801 work Disquisitiones Arithmeticae, written when he was just 21. Before Gauss, the result had been used and stated (most famously in Euclid's Elements around 300 BCE), but no fully rigorous proof of uniqueness had been published. Gauss recognised that uniqueness was the deep part and explicitly identified Euclid's Lemma as the crucial ingredient. The Disquisitiones also introduced modular arithmetic and laid the foundation for modern number theory. Gauss was asked as a schoolboy to add all integers from 1 to 100 as a punishment. He noticed pairs summing to 101 and gave the answer 5050 almost instantly — a story that has delighted mathematics teachers ever since.
Related Concepts
- Prime Numbers and Divisibility — Prime numbers are the atomic units used in the Fundamental Theorem; understanding divisibility rules helps identify them quickly.
- GCD and LCM — The most direct application of unique prime factorisation is the efficient calculation of GCDs and LCMs using exponent comparisons.
- Irrational Numbers — Proofs that numbers like √2 and √3 are irrational rely on unique prime factorisation to reach a contradiction.
- Modular Arithmetic — Modular arithmetic, introduced by Gauss alongside the FTA, uses prime structure to understand remainders and forms the basis of cryptography.
- The Integer Number System — The Fundamental Theorem of Arithmetic is specifically a theorem about the integers; understanding the properties of ℤ is essential context.