Простое число

Определение

Число, которое делится только на себя и 1. Благодаря этому свойству используются во многих алгоритмах, например, полиномиальном хешировании. В целом, такие числа являются основой, ведь все составные числа раскладываются на простые, а значит можно провести биекцию между наборами простых чисел и всеми числами.

Математические свойства простых чисел

Утверждение. Простых чисел бесконечное число.
Доказательство. Пусть это не так. Тогда у нас есть конечный набор простых чисел $p_1,p_2,p_3\dots p_n$. Перемножим все числа в нем и добавим к получившемуся числу 1. Обозначим полученное число за $N$. Оно не может делиться ни на одно из ранее полученных простых чисел, ведь иначе мы знаем, что $N\underset{p_k}{\equiv }0$ и $N-1\underset{p_k}{\equiv }0$, из чего следует, что $1\underset{p_k}{\equiv }0⟹p_k=1$ что явно неверно. Поэтому у нас точно существует новое простое число $N$, а значит их бесконечное количество.

Дополнительная информация

Существует много интересных типов простых чисел, так например простые числа близнецы - это числа, которые отличаются друг от друга на 2: 11 и 13, 37 и 39, 1e9+7 и 1e9+9, нерешенная загадка, связанная с ними - бесконечное ли их количество? Также существуют простые числа Мерсенна, они имеют вид $2^p-1$, и полезны в некоторых ситуациях, например при поиске совершенных чисел.