Fundamental Theorem of Arithmetic
This theorem states that every integer greater than 1 is either a prime number or can be uniquely represented as a product of prime numbers, disregarding the order of the factors. For example, \(1200 = 2^4 \times 3^1 \times 5^2\). This unique factorization is a cornerstone of number theory, providing a fundamental multiplicative structure for the integers.
The Fundamental Theorem of Arithmetic, also called the unique factorization theorem, consists of two main assertions for any integer \(n > 1\): first, that \(n\) can be written as a product of prime numbers (the existence part), and second, that this product is unique, apart from the order of the factors (the uniqueness part). The existence of a prime factorization is typically proven using strong induction. The base case is that 2 is prime. For the inductive step, assume every integer up to \(k\) has a prime factorization. For \(k+1\), it is either prime (and we are done) or composite. If it is composite, it can be written as a product of two smaller integers, \(a \times b\). By the induction hypothesis, both \(a\) and \(b\) have prime factorizations, and their product gives a prime factorization for \(k+1\).
The uniqueness part is more subtle and relies critically on Euclid’s Lemma, which states that if a prime \(p\) divides a product \(ab\), then \(p\) must divide either \(a\) or \(b\). To prove uniqueness, assume an integer \(n\) has two different prime factorizations: \(n = p_1 p_2 cdots p_k = q_1 q_2 cdots q_m\). The prime \(p_1\) divides the left side, so it must divide the right side. By Euclid’s Lemma, \(p_1\) must divide one of the \(q_j\). Since all \(q_j\) are prime, \(p_1\) must be equal to some \(q_j\). We can then cancel these terms from both sides and repeat the process, eventually showing that the two factorizations must be identical. While elements of this theorem appeared in Euclid’s *Elements* (c. 300 BC), Carl Friedrich Gauss provided the first clear statement and rigorous proof in his 1801 work *Disquisitiones Arithmeticae*, solidifying its foundational role in number theory.
UNESCO Nomenclature: 1101
– Pure mathematics
Precursors
- Euclid’s proof of the infinitude of primes
- Euclid’s Lemma
- The concept of prime numbers and divisibility from ancient Greek mathematics
- Development of mathematical induction as a proof technique
Applications
- cryptography (e.g., RSA algorithm)
- algorithms for finding the greatest common divisor (GCD)
- solving diophantine equations
- development of abstract algebra
- computer science algorithms for integer factorization
Potential Innovations Ideas
Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.
Related to: fundamental theorem of arithmetic, prime factorization, unique factorization, number theory, integer, prime number, Euclid, Gauss, canonical representation, multiplicative structure.