Prime numbers

This is why primes are called the 'atoms' of arithmetic: there's exactly one recipe for building each number, so knowing the primes and their powers tells you everything about a number's divisors.

Existence (by minimal counterexample): Suppose there exists an integer $n > 1$ that cannot be written as a product of primes, and let $m > 1$ be the smallest such integer. Since every prime is a product of a single prime, $m$ must be composite, so $m = a b$ for integers satisfying $1 < a, b < m$. By the minimality of $m$, both $a$ and $b$ are products of primes, whence their product $m = a b$ is also a product of primes—a contradiction.

Euclid's Lemma: Suppose a prime $p$ satisfies $p \mid a b$ with $p \nmid a$. Because $p$ is prime and $p \nmid a$, we have $\gcd(p, a) = 1$. By Bézout's identity, there exist integers $x, y$ such that $p x + a y = 1$. Multiplying both sides by $b$ yields $p(b x) + (a b)y = b$; since $p$ divides both $p(b x)$ and $a b$, $p$ must divide the right-hand side, giving $p \mid b$.

Uniqueness: Assume for contradiction that some integer admits two distinct prime factorizations, and let $n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$ (ordered so that $p_1 \le \cdots \le p_r$ and $q_1 \le \cdots \le q_s$) be the smallest such integer. Since $p_1 \mid q_1 q_2 \cdots q_s$, repeated application of Euclid's lemma shows that $p_1$ divides some prime $q_j$, which forces $p_1 = q_j \ge q_1$. By symmetry $q_1 \ge p_1$, so $p_1 = q_1$. Canceling $p_1$ from both sides produces a smaller integer $n / p_1 < n$ with two distinct prime factorizations, contradicting the minimality of $n$.

Euclid's argument (c. 300 BCE): suppose there were only finitely many primes $p_1, p_2, \ldots, p_k$. Multiply them all together and add 1: $N = p_1 p_2 \cdots p_k + 1$. Dividing $N$ by any $p_i$ leaves remainder 1, so none of the $p_i$ divides $N$. But $N$ must have some prime factor (by the fundamental theorem of arithmetic) — a prime that isn't on the list. So the list was never complete.

Step 1 (Constructing Euclid's number): Let $\{p_1, p_2, \dots, p_k\}$ be any finite collection of prime numbers. Form the integer $N = p_1 p_2 \cdots p_k + 1$ by multiplying all primes in the list and adding $1$. Since $p_1 \ge 2$, we have $N \ge 2 + 1 = 3 > 1$.

Step 2 (Existence of a prime factor): By the fundamental theorem of arithmetic, every integer $N > 1$ admits at least one prime divisor $q$, so $q \mid N$ (where $q = N$ if $N$ itself is prime, or $q < N$ if $N$ is composite).

**Step 3 (Proving $q$ is a new prime):** Suppose for contradiction that $q = p_i$ for some index $i$. Then $q \mid p_1 p_2 \cdots p_k$, and since $q \mid N$, the prime $q$ must divide their linear combination $q \mid (N - p_1 p_2 \cdots p_k) = 1$. This is impossible because every prime satisfies $q \ge 2$. Hence $q \notin \{p_1, p_2, \dots, p_k\}$, proving that no finite list can contain all prime numbers.