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

Простое число — это натуральное число, которое больше единицы и имеет ровно два положительных делителя: единицу и само себя. Формально это можно записать так: $n>1$ и $\forall a,b\in\mathbb{N}\ (ab=n\Rightarrow (a=1\lor b=n))$. Проще говоря, простое число нельзя разложить на множители, отличные от тривиальных; такие числа служат «атомами» в арифметике целых чисел. Важно отметить, что единица не считается простым числом, поскольку у неё только один положительный делитель.

Простые числа играют центральную роль в теории чисел и в практических приложениях. Одно из ключевых свойств — разложение целого числа на простые множители, которое по основной теореме арифметики является единственным с точностью до порядка множителей; это свойство удобно выражается формулой вида $n=\prod_{i=1}^k p_i^{\alpha_i}$. Существуют бесконечно много простых чисел (доказательство приписывают Евклиду), а их распределение изучается в аналитической теории чисел. В прикладных областях простые числа используются в криптографии (например, в схемах на основе факторизации больших чисел и в протоколах типа RSA), в генерации псевдослучайных чисел и при проверке целостности данных. Для проверки простоты числа применяются как простые методы (деление на все возможные делители), так и более сложные алгоритмы, такие как тесты вероятностной природы и детерминированные алгоритмы быстрой проверки простоты.