Открыть сервисСервис

Простое число: определение и свойства

Простое число — натуральное число, имеющее ровно два делителя: единицу и само себя. К простым числам относятся 2, 3, 5, 7, 11, 13, 17, 19, 23 и далее; единица и все составные числа (например, 4, 6, 8, 9) простыми не являются. Простые числа играют центральную роль в теории чисел: согласно основной теореме арифметики, любое натуральное число больше единицы представимо в виде произведения простых множителей единственным образом (с точностью до порядка сомножителей).

История

Вопрос о простых числах восходит к античности. Евклид в «Началах» (около 300 года до н. э.) доказал бесконечность множества простых чисел, предложив классическое сокращённое доказательство: если бы простых чисел было конечное множество, их произведение плюс единица не делилось бы ни на одно из них, что противоречило бы предположению. Пифагорейцы, по свидетельству позднейших авторов, рассматривали простые и составные числа как «нечётные» и «чётные» в более широком смысле, а сам термин «простое число» (греч. πρῶτον ἀριθμός) закрепился в трудах Никомаха Герасенского (II век н. э.).

В Средние века изучение простых чисел продолжилось в работах арабских математиков — Аль-Хорезми, Аль-Караджи и Ибн аль-Хайсама, — а в Европе — у Фибоначчи и Ферма. Пьер де Ферма в XVII веке сформулировал ряд гипотез о простых числах, включая знаменитую теорему о сумме двух квадратов: нечётное простое число представимо в виде суммы двух квадратов тогда и только тогда, когда оно имеет вид 4k+1.

Определение и базовые свойства

Простое число — натуральное число p > 1, которое не имеет положительных делителей, отличных от 1 и p. Число 1 по определению не является ни простым, ни составным. Составное число — натуральное число, имеющее хотя бы один делитель, отличный от единицы и самого себя.

Ключевые свойства:

  • Делители. У простого числа p ровно два делителя: 1 и p.
  • Нечётность. Единственное чётное простое число — 2; все остальные простые числа нечётны.
  • Критерий делимости. Если простое число p делит произведение ab, то p делит a или p делит b (свойство евклидовой леммы).
  • Разложение. Любое число > 1 либо само простое, либо представимо в виде произведения простых чисел (основная теорема арифметики).

Распределение простых чисел

Постулат Пифагора и гипотеза о простых числах

Ещё в античности возникло предположение, что между любыми двумя простыми числами n и 2n существует хотя бы одно простое число (постулат Пифагора). Оно не доказано и в общем виде считается трудным; впервые его частный случай (n = 1) доказал Эврипид, а для произвольного n — Бертран (1850), что известно как гипотеза Бертрана (теорема Шебышева).

Асимптотика и гипотеза Римана

Число π(x) простых чисел, не превосходящих x, по теореме о простых числах (Гаусс, Лежандр, доказана Адамаром и де ла Валле-Пуссеном в 1896 году) асимптотично равно x/ln x. Более точное приближение даёт логарифмическая интеграл li(x). Расхождение между π(x) и li(x) связано с нерешённой гипотезой Римана о нулях дзета-функции Римана; доказательство этой гипотезы включено в список задач тысячелетия Института математики Клея.

Типы простых чисел

ТипОпределениеПримеры
Твёрдое простоеПростое число p, для которого (p−1)/2 тоже простое3, 5, 7, 11, 23, 47
МерсенновоПростое вида 2^p − 13, 7, 31, 127, 8191
ФерматовоПростое вида 2^(2^n) + 13, 5, 17, 257, 65537
ТвинПростое p, для которого p+2 или p−2 также простое(3,5), (5,7), (11,13)
Софі-ЖерменПростое p, для которого 2p+1 также простое2, 3, 5, 11, 23

Методы проверки на простоту

Для определения простоты числа n используются:

  • Перебор делителей — проверка делимости на все числа от 2 до √n; сложность O(√n).
  • Тест Ферма — проверка равенства a^(n−1) ≡ 1 (mod n) для нескольких оснований a; может давать ложнопростые числа (например, 561 — число Кармайкла).
  • Тест Миллера — Рабина — вероятностный алгоритм, для которого не доказано отсутствие составных «свидетелей», но на практике ошибки не встречаются.
  • Тест АКС — первый детерминированный полиномиальный алгоритм проверки простоты, открытый Агарвалем, Сеной и Саксеной в 2002 году.

Простые числа в криптографии

Современная публично-ключевая криптография опирается на простые числа. В системе RSA генерируются два больших простых числа p и q; их произведение n = pq служит открытым модулем, а знание разложения n на множители позволяет вычислить секретный ключ. Сложность разложения больших чисел на простые множители (проблема факторизации) лежит в основе стойкости RSA и родственных схем. Для генерации простых чисел используют тесты Миллера — Рабина и алгоритмы поиска простых чисел вида k·2^n + 1.

Интересные факты

  • Простые числа распределены неравномерно: плотность простых чисел убывает по мере роста числа.
  • Гипотеза о твин-простых числах (существование бесконечного числа пар простых с разностью 2) остаётся открытой; в 2013 году Чжан Мэйтянь доказал, что существует бесконечно много пар простых чисел с разностью, не превосходящей 70 миллионов (впоследствии граница была улучшена до 246).
  • Число 17 — единственное простое число, все цифры которого (1 и 7) также простые.
  • Известно, что простых чисел бесконечно много, но неизвестно, существует ли бесконечно много простых чисел вида n² + 1.

Источники

  • Евклид. Начала, книга IX.
  • Никомах Герасенский. Введение в арифметику.
  • Харди Г., Райт Э. Введение в теорию чисел.
  • Нивен З., Закерман Г., Монтгомери Г. Введение в теорию чисел.
  • Кнут Д. Искусство программирования, том 2.
  • Институт математики Клея. Задачи тысячелетия.
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru