Простое число — натуральное число, большее 1, которое делится только на 1 и на само себя: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …. Натуральные числа, большие 1 и не простые, называют составными: у них есть ещё хотя бы один делитель. Число 1 не простое и не составное.
Каждое натуральное число, кроме 1, имеет простой делитель (наименьший его делитель, больший 1, — простое число).
Простых чисел бесконечно много (теорема Евклида): если бы 2, 3, 5, …, p были все простые числа, то число 2 · 3 · 5 · … · p + 1 не делилось бы ни на одно из них (остаток 1), а простой делитель у него есть — противоречие.