The Building Blocks

Discrete Math · Axiom Academy

LESSON The Building Blocks of Numbers Prime numbers are the atoms of mathematics: every integer can be built from them in exactly one way. The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... Numbers that aren't prime (except 1) are called composite because they can be composed from smaller factors. For example, 12 = 2 × 2 × 3. 2. The Fundamental Theorem of Arithmetic This means that primes are truly the "building blocks" of all integers. Just like any substance can be broken down into its constituent atoms in only one way, any number can be factored into primes in only one way. Why is prime factorization unique? We prove this by contradiction. Suppose a number n could be factored in two different ways: Key insight: If a prime p divides a product of numbers, it must divide at least one of those numbers. This is called Euclid's Lemma , and it's the crucial property that makes the proof work. 4. Finding Primes: Sieve of Eratosthenes How do we find all prime numbers up to a given limit? The ancient Greek mathematician Eratosthenes (276-194 BCE) invented an elegant algorithm: systematically eliminate all composite numbers by marking multiples of each prime. Start with the smallest unmarked number (initially 2) Mark all multiples of this number (except the number itself) Move to the next unmarked number and repeat Continue until you've processed all numbers up to √n

This is the written version of the interactive lesson above. See the full Discrete Math course.