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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:28, 23 февраля 2017.
TemplateDifinitionIcon.svg Определение «Простое число»
Число называется простым, если не имеет положительных делителей, кроме и


Бесконечность множества простых чисел

TemplateTheoremIcon.svg Теорема Теорема
Простых чисел бесконечно много
Доказательство

От противного. Пусть существует максимально большое простое число . Тогда число делится (без остатка) на любое простое, но тогда остаток от деления на любое простое числа будет равен 1. Таким образом, либо само простое, либо делится на простое, большее . Противоречие.


Методы нахождения простых чисел

Методы нахождения простых чисел делятся на вероятностные и детерминированные.

Вероятностные

Детерминированные

Теорема Чебышёва

TemplateDifinitionIcon.svg Определение « Теорема Чебышёва»

Существуют такие постоянные и , что для любого целого справедливы неравенства
,
где - число простых чисел, не превосходящих .

См. также