Основная теорема арифметики говорит: любое натуральное число больше единицы единственным образом — с точностью до порядка — представимо в виде произведения простых. Это значит, что простые числа играют для арифметики ту же роль, что химические элементы для вещества: всё остальное собирается из них.

Доказательство бесконечности простых чисел Евклид дал около 300 года до н.э. — и оно занимает несколько строк1. Предположим, что простых чисел конечно много: p₁, p₂, …, pₙ. Рассмотрим число N = p₁·p₂·…·pₙ + 1. Оно либо само простое, либо имеет простой делитель. В обоих случаях этот делитель не может быть ни одним из p₁…pₙ — потому что N даёт остаток 1 при делении на любое из них. Противоречие.

Простые числа — это атомы арифметики.
— Маркус дю Сотой

Распределение простых неравномерно, но подчиняется удивительно точному закону. Теорема о простых числах (доказана независимо Адамаром и Валле-Пуссеном в 1896) утверждает, что количество простых, не превосходящих n, асимптотически равно n/ln n2. Это значит, что плотность простых на отрезке [1, n] примерно 1/ln n — и она убывает медленно, но неуклонно.

Несмотря на то, что мы знаем о простых очень много, ключевые вопросы остаются открытыми. Гипотеза о простых-близнецах: бесконечно ли пар (p, p+2)? Гипотеза Гольдбаха: всякое чётное n > 2 — сумма двух простых? Гипотеза Римана связывает распределение простых с нулями дзета-функции. Все три — нерешены, и каждая из них тянет за собой целые здания математики.

Простые числа — это объект, в котором детерминированность правил порождает структуру, неотличимую от случайной. Каждое из них вычислимо, и при этом мы не умеем предсказать следующее.