The atoms of arithmetic — primes are the building blocks of all integers.
A prime p > 1 has exactly two divisors: 1 and itself. The first primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
Primes are the foundation of modern cryptography and connect deeply to factoring in algebra.
360 ÷ 2 = 180 → 180 ÷ 2 = 90 → 90 ÷ 2 = 45 → 45 ÷ 3 = 15 → 15 ÷ 3 = 5 → 5 ÷ 5 = 1
Divisors of 360: (3+1)(2+1)(1+1) = 24 divisors
Euclidean Algorithm computes GCD efficiently: GCD(a, b) = GCD(b, a mod b). This is one of the oldest algorithms — and it's essential in modular arithmetic for finding modular inverses.
To find all primes ≤ n: start with 2, mark all multiples of 2, next unmarked (3), mark all multiples of 3, continue to √n. The remaining unmarked numbers are prime. Complexity: O(n log log n).
The Prime Number Theorem: π(n) ≈ n/ln(n), where π(n) counts primes ≤ n. This connects primes to logarithmic functions and limits. There are infinitely many primes (Euclid's proof by contradiction is one of the most elegant in mathematics).
Open problems: the Twin Prime Conjecture (infinitely many primes p where p+2 is also prime), Goldbach's Conjecture (every even n > 2 is the sum of two primes), and the Riemann Hypothesis (about the precise distribution of primes).