Primes and the Fundamental Theorem of Arithmetic

The Atoms of the Integers

A prime is an integer greater than 1 whose only positive divisors are 1 and itself: $2, 3, 5, 7, 11, \dots$. An integer greater than 1 that is not prime is composite — it factors into smaller pieces. The number $1$ is neither prime nor composite (by convention, and for good reason — see below). Primes are the multiplicative "atoms" of the integers.

The central result is the Fundamental Theorem of Arithmetic: every integer greater than 1 can be written as a product of primes, and this factorization is unique up to the order of the factors. For example $60 = 2^2 \cdot 3 \cdot 5$, and no other set of primes multiplies to $60$. This uniqueness is why primes are the fundamental building blocks — every integer has exactly one "prime fingerprint."

This is also why $1$ is excluded from the primes: if $1$ were prime, factorizations would no longer be unique (you could insert any number of $1$s), breaking the theorem. Definitions in mathematics are chosen to make the important theorems clean.

Two classic facts round out the theory:

• There are infinitely many primes (Euclid's theorem). The proof is a gem of contradiction: assume finitely many, multiply them all and add 1; the result is divisible by none of them, a contradiction.
• To test whether $n$ is prime, you need only check for divisors up to $\sqrt{n}$: if $n = ab$ with $a \le b$, then $a \le \sqrt{n}$, so a factor below the square root must exist if any factor does.

Prime factorization underlies the gcd, the lcm, modular arithmetic, and modern cryptography (whose security rests on factoring being hard for large numbers).

Common pitfall: thinking 1 is prime, or that a number needs checking for divisors all the way up to itself. By definition a prime is greater than 1, and 1 is neither prime nor composite. And to test primality you only check divisors up to $\sqrt{n}$ — any composite $n$ must have a factor at or below its square root, so finding none there proves $n$ prime.

A factor tree for 60 branching 60 to 2 and 30, 30 to 2 and 15, 15 to 3 and 5, the accent leaves 2, 2, 3, 5 collected as the unique prime factorization.

$$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$