Простые и составные числа
Основные определения
Простое число
Простое число — это натуральное число, большее 1, которое имеет ровно два различных положительных делителя: 1 и само себя.
Формально: $p > 1$ является простым тогда и только тогда, когда для всех $a, b \in \mathbb{N}$, $p = a \cdot b$ означает, что $a = 1$ или $b = 1$.
Составное число
Составное число — это натуральное число, большее 1, которое имеет более двух различных положительных делителей. Другими словами, его можно представить как произведение двух меньших натуральных чисел.
Формально: $n > 1$ является составным, если существуют $a, b \in \mathbb{N}$ с $1 < a, b < n$ такие, что $n = a \cdot b$.
Особый случай: Число 1 не является ни простым, ни составным. Оно называется единицей. Число 2 — единственное чётное простое число.
🏛️ Теорема: Бесконечность множества простых чисел (Евклид, ~300 г. до н. э.)
Теорема. Множество простых чисел бесконечно.
Доказательство (от противного):
- Предположим, для получения противоречия, что существует лишь конечное число простых чисел: $p_1, p_2, p_3, \ldots, p_n$.
- Рассмотрим число: $$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$
- Поскольку $N > 1$, число $N$ должно быть либо простым, либо иметь простой делитель.
- Однако при делении $N$ на любое простое число $p_i$ из нашего списка мы получаем остаток 1: $$N \div p_i = (p_1 \cdot p_2 \cdots p_n) / p_i + \frac{1}{p_i}$$ Следовательно, $p_i \nmid N$ для любого $i = 1, 2, \ldots, n$.
- Это означает, что $N$ либо является новым простым числом, не входящим в наш список, либо $N$ имеет простой делитель, не входящий в наш список.
- В любом случае мы нашли простое число, не входящее в исходный список — противоречие. ∎