Простые числа
Простые числа — в математике, это натуральные числа, большие единицы, которые не делятся ни на одно натуральное число, кроме единицы и самого себя. Обычно простое число обозначается буквой p. Простых чисел бесконечно много. Является ли заданное число N простым можно проверить, последовательно деля его на все натуральные числа, меньшие его (достаточно проверить для чисел 2, 3, …, ). Существует также детерминированный полиномиальный алгоритм проверки натурального числа на простоту. Согласно основной теореме арифметики, любое натуральное число, большее 1, раскладывается в произведение простых чисел и единственным образом с точностью до порядка сомножителей. Простые числа являются объектом изучения теории чисел и находят практическое использование в современной криптографии.
По возрастанию простые числа образуют целочисленную последовательность 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, …(последовательность, обозначенная A000040 в энциклопедии целочисленных последовательностей Слоэна).
История[править]
Понятие простого числа было введено математиками Древней Греции. В Древней Греции также установили бесконечность множества простых чисел и и понимали факт единственности разложения на простые множители. В Новое время в рамках исследований по теории чисел активно изучался асимптотический закон распределения простых чисел, связанный с дзета-функцией и до сих пор не доказанной и не опровергнутой гипотезой Римана. Во второй половине XX века простые числа стали использоваться в реально применяемых на практике криптографических протоколах. В начале 2000-х годов был найден детерминированный алгоритм проверки натурального числа на простоту за полиномиальное время от длины этого числа.
Асимптотический закон распределения[править]
→ Теорема о распределении простых чисел
Если обозначить количество простых чисел, меньших , через , то эта функция асимптотически растет как , то есть:
- .
Эквивалентным образом, -е простое число по возрастанию растет асимптотически как :
- .
Асимптотический закон распределения простых чисел был полностью доказан в 1896 году независимо Адамаром и Валле-Пуссеном с использованием методов теории функций комплексного переменного. В XX веке было найдено доказательство элементарными методами.
В основе изучения свойств распределения простых чисел лежит дзета-функция Римана:
рассматриваемая как функция комплексной переменной .
Этот ряд сходится, является аналитической функцией и допускает аналитическое продолжение на всю комплексную плоскость без единицы.
Тождество Эйлера иллюстрирует связь дзета-функции Римана с простыми числами:
где произведение берется по всем простым .
Проблемы[править]
С простыми числами связан ряд проблем, на протяжении десятилетий и даже веков не поддающихся решению. Одна из таких проблем — гипотеза Гольдбаха-Эйлера, сформулированная в XVIII веке: любое четное (натуральное) число, большее двух, можно представить в виде суммы двух простых чисел. Эта гипотеза до сих пор не доказана и не опровергнута. Более слабый вариант этой гипотезы, согласно которому каждое достаточно большое нечётное (натуральное) число можно представить в виде суммы трёх простых, был доказан в 1937 году И. М. Виноградовым, для всех нечётных натуральных чисел представимость их в виде суммы трех простых доказана в 2013 году перуанским математиком Харальдом Гельфготтом.
Гипотеза Римана гласит, что все комплексные нули дзета-функции, лежащие в полосе , находятся на прямой . Гипотеза Римана была сформулирована в XIX веке Риманом и вплоть до настоящего времени не поддается доказательству. Есть ряд численных экспериментов, свидетельствующих в ее пользу. Доказательство гипотезы Римана привело бы к уточнению закона распределения простых чисел.
См. также[править]
- Решето Эратосфена — простой алгоритм нахождения всех простых чисел, не превышающих заданной границы.
Литература[править]
- Бухштаб А. А. Теория чисел — М.: «Просвещение», 1966.
Ссылки[править]
Числовые системы ↑ [+] | |
---|---|
множества |
Натуральные числа () • Целые () • Рациональные () • Алгебраические () • Периоды • Вычислимые |
и их расширения |
Действительные (вещественные) () • Комплексные () • Кватернионы () • Числа Кэли (октавы, октонионы) () • Седенионы () • Альтернионы • Дуальные • Гиперкомплексные • Супердействительные • Гипервещественные |
числовые системы |
Кардинальные числа • Порядковые (трансфинитные, ординалы) • p-адические • Сверхнатуральные • Сюрреальные |
Двойные • Иррациональные • Трансцендентные • Числовой луч • Положительные числа • Простые числа • Бикватернионы • Координатизация • Расширение понятия числа |