Натуральное число простое, если у него ровно два натуральных делителя: 1 и само число (2, 3, 5, 7, 11, 13, …). Составное — если делителей больше двух. Число 1 ни простое, ни составное.
Простых чисел бесконечно много (Евклид). Если бы p было наибольшим простым, то число 2 · 3 · 5 · … · p + 1 не делилось бы ни на одно простое (остаток 1) и было бы простым, большим p, — противоречие.
Формулы, которые «всегда дают простые числа», обманчивы: 2n² + 29 простое при n = 1, 2, …, 7, но при n = 29 делится на 29. Одного контрпримера достаточно, чтобы опровергнуть утверждение «при любом n».
Чтобы показать, что число составное, достаточно найти у него делитель, кроме 1 и его самого, — часто помогает последняя цифра: число, оканчивающееся чётной цифрой, делится на 2, оканчивающееся на 0 или 5 — на 5.