Primes and the Fundamental Theorem of Arithmetic — The Atomic Decomposition of Integers
We define prime numbers and establish their basic properties, including Euclid's proof of the infinitude of primes. We then give a rigorous proof of the fundamental theorem of arithmetic (existence and uniqueness of prime factorization), and discuss the sieve of Eratosthenes and the Miller--Rabin primality test.
1 Definition and Basic Properties of Primes
Definition 1 (Prime number).
An integer is called a prime if its only positive divisors are and itself. An integer that is not prime is called composite.
Lemma 2 (Euclid's lemma).
If is prime and , then or .
Proof.
Suppose . Since is prime, . By Bé with . Multiplying both sides by gives . Now and , so . □
Corollary 3.
If is prime and , then for some .
2 The Infinitude of Primes
Theorem 4 (Euclid).
There are infinitely many primes.
Proof.
Suppose, for contradiction, that is a complete list of all primes. Set . Since , it has at least one prime factor . This must equal some . But then and , so . This contradicts . □
3 The Fundamental Theorem of Arithmetic
Theorem 5 (Fundamental theorem of arithmetic).
Every integer can be written as a product of primes (existence). Moreover, this representation is unique up to the ordering of the factors (uniqueness):
Proof.
Existence. We proceed by strong induction on . The base case holds since is prime. For : if is prime, we are done. If is composite, write with . By the inductive hypothesis, both and are products of primes, so is as well.Uniqueness. Suppose with and . We argue by induction on . If , then is prime, forcing and . For : since , Euclid's lemma gives for some . Since is also prime, . Dividing both sides by yields . By the inductive hypothesis, and the remaining prime factors agree up to reordering. □
4 The Sieve of Eratosthenes
Remark 6.
The sieve of Eratosthenes is a classical method for listing all primes up to . One writes down the integers from to and, for each prime with , strikes out the multiples . The surviving numbers are precisely the primes. The time complexity is .
Theorem 7.
Every composite number has a prime factor at most .
Proof.
Write with . Then , so . Any prime factor of is at most . □
5 The Miller–Rabin Primality Test
Definition 8.
For an odd integer , write with odd. An integer with is called a strong probable prime witness for if or for some .
Theorem 9.
If is prime, then every with is a strong probable prime witness. If is composite, then at most of the integers with are strong probable prime witnesses.
Remark 10.
Based on this theorem, testing randomly chosen bases yields a probability of at most that a composite number passes as prime. With , this probability falls below , which is more than sufficient for practical purposes.
FO
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.
1 followers·105 articles