Every natural number greater than \(1\) can be broken down into divisors, but some numbers refuse to break down any further: their only positive divisors are \(1\) and themselves. These numbers are the multiplicative building blocks of \(\mathbb{N}\), in much the same way that the successor function of the Peano axioms generates every natural number additively from \(1\).
A natural number \(p>1\) is called prime if its only positive divisors are \(1\) and \(p\). A natural number \(n>1\) that is not prime is called composite: it can be written as \(n=ab\) with \(1<a,b<n\). The number \(1\) itself is neither prime nor composite, since the definition of a prime explicitly requires \(p>1\). The first few primes are
\[2,3,5,7,11,13,17,19,23,29,31,\ldots\]
Every Number Greater Than 1 Has a Prime Divisor
Before primes can be shown to be infinite in number, or every number shown to decompose into them, it helps to know that a prime divisor always exists in the first place. This follows from the well-ordering principle: every nonempty subset of \(\mathbb{N}\) has a least element.
Suppose, for contradiction, that some natural number greater than \(1\) has no prime divisor, and let \(n_0\) be the smallest such number, using well-ordering on the (assumed nonempty) set of counterexamples. Then \(n_0\) itself cannot be prime, since a prime divides itself; so \(n_0\) is composite, \(n_0=ab\) with \(1<a,b<n_0\). Because \(a<n_0\) and \(n_0\) was chosen as the smallest counterexample, \(a\) is not itself a counterexample, so \(a\) has some prime divisor \(p\). But \(p\mid a\) and \(a\mid n_0\) together give \(p\mid n_0\), contradicting that \(n_0\) has no prime divisor. So no counterexample exists: every \(n>1\) has a prime divisor.
The Infinitude of Primes
Euclid gave the classical proof that there are infinitely many primes, by showing that no finite list of primes can be complete. Suppose \(p_1,p_2,\ldots,p_k\) were all the primes that exist, and consider
\[N:=p_1p_2\cdots p_k+1.\]
Since \(N>1\), the previous section guarantees a prime divisor \(p\) of \(N\). By assumption, \(p\) must be one of \(p_1,\ldots,p_k\), so \(p\) divides the product \(p_1p_2\cdots p_k\) as well as \(N\), and therefore divides their difference,
\[N-p_1p_2\cdots p_k=1.\]
But no prime divides \(1\): a prime is greater than \(1\) by definition, and the only positive divisor of \(1\) is \(1\) itself. This contradiction shows that no finite list of primes can contain all of them, so there are infinitely many primes.
The Fundamental Theorem of Arithmetic
Every natural number \(n>1\) is a product of primes, and this decomposition is unique up to the order of the factors. This decomposition is called the prime factorization of \(n\); for example,
\[60=2^2\cdot3\cdot5.\]
Existence
Suppose, again for contradiction, that some \(n>1\) has no prime factorization, and let \(n_0\) be the smallest such number by well-ordering. Then \(n_0\) is not itself prime, since a prime is trivially its own one-factor factorization; so \(n_0=ab\) with \(1<a,b<n_0\). By minimality of \(n_0\), both \(a\) and \(b\) do have prime factorizations, and concatenating them gives a prime factorization of \(n_0=ab\), contradicting the choice of \(n_0\). So every \(n>1\) has a prime factorization.
Uniqueness
Uniqueness rests on Euclid's lemma, already proved for general divisors: if \(a\mid bc\) and \(\gcd(a,b)=1\), then \(a\mid c\). Specializing to a prime \(p\) and any \(a\in\mathbb{N}\) with \(p\nmid a\): since \(\gcd(p,a)\) divides \(p\), it can only be \(1\) or \(p\) by the definition of a prime, and it cannot be \(p\) because that would mean \(p\mid a\); so \(\gcd(p,a)=1\). Applying Euclid's lemma with this fact gives the version needed here: if a prime \(p\) divides a product \(ab\), then \(p\mid a\) or \(p\mid b\) — otherwise \(p\nmid a\) would force \(\gcd(p,a)=1\) and hence \(p\mid b\).
This extends by induction to any number of factors: if a prime \(p\) divides a product \(q_1q_2\cdots q_r\) of primes, then \(p=q_i\) for some \(i\). For \(r=1\) this is immediate, since \(p\mid q_1\) with both prime forces \(p=q_1\) (the only divisors of \(q_1\) greater than \(1\) are \(q_1\) itself). For the step from \(r-1\) to \(r\), the two-factor case applied to \(q_1\) and \(q_2\cdots q_r\) gives either \(p\mid q_1\) (hence \(p=q_1\)) or \(p\mid q_2\cdots q_r\), in which case the induction hypothesis on the shorter product gives \(p=q_i\) for some \(i\geq2\).
Now suppose \(n>1\) has two prime factorizations,
\[n=p_1p_2\cdots p_r=q_1q_2\cdots q_s.\]
Since \(p_1\) divides the left side, it divides the right side too, so by the fact just shown \(p_1=q_j\) for some \(j\); reordering the \(q\)'s so that \(j=1\), both sides can be divided by this common factor, leaving \(p_2\cdots p_r=q_2\cdots q_s\). Repeating the same argument strips off one matching pair of factors at a time. Neither side can run out of factors before the other — if, say, the left side reached an empty product \(1\) while primes \(q_i\) remained on the right, then \(1\) would have a prime divisor, which is impossible. So the process pairs up every \(p_i\) with some \(q_j\), forcing \(r=s\) and the two factorizations to agree up to order.
Twin Primes
Two primes \(p\) and \(p+2\) that differ by exactly \(2\) are called twin primes, for example
\[(3,5),\quad(5,7),\quad(11,13),\quad(17,19),\quad(29,31),\quad(41,43),\quad(101,103).\]
The twin prime conjecture — that infinitely many such pairs exist — is one of the oldest open problems in number theory and remains unproved. A major partial result came in 2013, when Yitang Zhang proved that infinitely many pairs of primes exist with some bounded gap between them (initially at most \(70{,}000{,}000\)); the bound was subsequently reduced to \(246\) through the Polymath project and independent work by James Maynard. This shows primes cluster together infinitely often, but the specific gap of \(2\) required by the twin prime conjecture itself is still open.
Prime Factorization and Cryptography
Multiplying two large primes together is computationally fast, but recovering the two primes from their product alone, for numbers with hundreds of digits, is believed to require infeasible amounts of computation with currently known methods. This asymmetry — easy to compute one way, hard to invert — is the basis of several public-key cryptographic schemes, alongside the discrete-logarithm asymmetry used in the Diffie–Hellman key exchange. The Euclidean algorithm for computing \(\gcd\), by contrast, runs efficiently even on such large numbers, since divisibility does not require knowing the prime factorization at all.