Prime Numbers Summary

Number Theory · Axiom Academy

Let's review the fundamental building blocks of all integers. Prime Number: An integer greater than 1 with exactly two positive divisors: 1 and itself First Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... Only Even Prime: 2 is the only even prime number Composite Numbers: Integers greater than 1 that are not prime (have more than two divisors) 1 is Neither: By convention, 1 is neither prime nor composite Fundamental Role: Primes are the multiplicative building blocks of all integers Unique Factorization: Every integer greater than 1 can be expressed as a product of primes in exactly one way (up to order) Irreducibility: Primes cannot be factored into smaller positive integers GCD and LCM: Prime factorization enables efficient computation of greatest common divisors and least common multiples Ancient Algorithm: Efficient method for finding all primes up to a given limit, discovered by Eratosthenes around 240 BCE Method: Start with 2, mark all its multiples as composite, then move to the next unmarked number and repeat Efficiency: Time complexity O(n log log n), very practical for finding primes up to millions Visual: Numbers are systematically "sieved out" until only primes remain Trial Division: Test divisibility by all primes up to √n; simple but slow for large numbers Fermat Test: Probabilistic test based on Fermat's Little Theorem Miller-Rabin: More sophisticated probabilistic test with better error bounds

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