Определение
Простым числом называют натуральное число, которое больше 1 и делится
только на 1 и на само себя.
Приведём первые 15 простых чисел:
$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47$.
Непростые натуральные числа, большие 1, называют составными. Каждое
составное число делится на 1, на себя и ещё хотя бы на одно натуральное число.
Приведём составные числа, меньшие 25:
$4,\ 6,\ 8,\ 9,\ 10,\ 12,\ 14,\ 15,\ 16,\ 18,\ 20,\ 21,\ 22,\ 24$.
🧠 Запомни: число 1 не является
ни простым, ни составным. Значит, множество всех натуральных чисел состоит из трёх частей:
простых чисел, составных чисел и числа 1.
💡 Из жизни: простые числа — это как атомы в химии. Из них путём умножения
«собираются» все остальные, составные числа, а сами простые числа дальше на множители
(кроме 1 и себя) не раскладываются.
Теорема 1. У составного числа всегда есть простой делитель
Теорема. Каждое отличное от единицы натуральное число имеет делитель —
простое число.
Докажем это утверждение по шагам.
1
Любое натуральное число $n > 1$ имеет делители $1$ и $n$.
2
Если $n$ — простое число, делитель-простое число уже найден: это само $n$.
3
Если $n$ — составное число, возьмём $d$ —
наименьший его делитель, отличный от 1.
4
Докажем, что $d$ простое. Предположим противное: $d$ составное. Тогда у $d$ есть делитель
меньше $d$ и не равный 1, который является делителем и для $n$ — значит, $d$ не был
наименьшим делителем $n$. Получили противоречие.
5
Значит, $d$ — простое число. Теорема доказана.
Теорема Евклида. Простых чисел бесконечно много
Все простые числа выписать невозможно — их бесконечно много. Любой список простых чисел
можно пополнить ещё одним. Это доказал древнегреческий учёный Евклид ещё в III веке до н.э.
Теорема Евклида. Простых чисел бесконечно много.
1
Предположим противное: простых чисел конечное число, и $p$ — наибольшее из них.
2
Выпишем все простые числа по порядку возрастания: $2,\ 3,\ 5,\ 7,\ \ldots,\ p$.
3
Составим число $$N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot \ldots \cdot p + 1.$$
4
Так как $N > 1$, по теореме 1 у него есть простой делитель — значит, $N$ делится хотя бы на одно из чисел $2, 3, 5, \ldots, p$.
5
Но при делении $N$ на любое из чисел $2, 3, 5, \ldots, p$ остаток всегда равен 1 — значит, $N$ не делится ни на одно из них. Противоречие!
6
Предположение неверно: наибольшего простого числа не существует. Простых чисел бесконечно много.
Попробуй сам проверить это на интерактивной схеме справа →
⚠️ Частая ошибка: многие думают, что все нечётные числа простые. Но,
например, $51 = 3 \times 17$ — составное число,
хотя оно нечётное и не делится ни на одно однозначное чётное число. Проверять делимость
нужно не только на 2, а на все простые числа не больше $\sqrt{n}$.
🧠 Запомни: число 2 — единственное чётное простое число (все остальные
чётные числа делятся на 2, а значит составные). Множество простых чисел бесконечно
(теорема Евклида), а перебирать делители при проверке достаточно только до $\sqrt{n}$.