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

Материал из Циклопедии
(перенаправлено с «Простое число»)
Перейти к: навигация, поиск
Kampus.kz: Математика. Урок 2 - Числа: Простые числа

Простые числа — в математике, это натуральные числа, большие единицы, которые не делятся ни на одно натуральное число, кроме единицы и самого себя. Обычно простое число обозначается буквой p. Простых чисел бесконечно много. Является ли заданное число N простым можно проверить, последовательно деля его на все натуральные числа, меньшие его (достаточно проверить для чисел 2, 3, …, [math]\sqrt{N}[/math]). Существует также детерминированный полиномиальный алгоритм проверки натурального числа на простоту. Согласно основной теореме арифметики, любое натуральное число, большее 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-х годов был найден детерминированный алгоритм проверки натурального числа на простоту за полиномиальное время от длины этого числа.

[править] Асимптотический закон распределения

Если обозначить количество простых чисел, меньших [math]x[/math], через [math]\pi(x)[/math], то эта функция асимптотически растет как [math]x/\ln(x)[/math], то есть:

[math]\lim\limits_{x \to +\infty} \frac{\pi(x)}{x/\ln x} = 1[/math].

Эквивалентным образом, [math]k[/math]-е простое число по возрастанию [math]p_k[/math] растет асимптотически как [math]k\ln k[/math]:

[math]\lim\limits_{k \to \infty} \frac{p_k}{k\ln k} = 1[/math].

Асимптотический закон распределения простых чисел был полностью доказан в 1896 году независимо Адамаром и Валле-Пуссеном с использованием методов теории функций комплексного переменного. В XX веке было найдено доказательство элементарными методами.

В основе изучения свойств распределения простых чисел лежит дзета-функция Римана:

[math]\zeta(s) = \sum\limits_{n=1}^{\infty}\frac{1}{n^s},[/math]

рассматриваемая как функция комплексной переменной [math]s[/math].

Этот ряд сходится, является аналитической функцией и допускает аналитическое продолжение на всю комплексную плоскость без единицы.

Тождество Эйлера иллюстрирует связь дзета-функции Римана с простыми числами:

[math]\zeta(s) = \prod\limits_p \frac{1}{1 - p^{-s}},[/math]

где произведение берется по всем простым [math]p[/math].

[править] Проблемы

С простыми числами связан ряд проблем, на протяжении десятилетий и даже веков не поддающихся решению. Одна из таких проблем — гипотеза Гольдбаха-Эйлера, сформулированная в XVIII веке: любое четное (натуральное) число, большее двух, можно представить в виде суммы двух простых чисел. Эта гипотеза до сих пор не доказана и не опровергнута. Более слабый вариант этой гипотезы, согласно которому каждое достаточно большое нечётное (натуральное) число можно представить в виде суммы трёх простых, был доказан в 1937 году И. М. Виноградовым.

Гипотеза Римана гласит, что все комплексные нули дзета-функции, лежащие в полосе [math]0 \leqslant \operatorname{Re}\,s \leqslant 1[/math], находятся на прямой [math]\operatorname{Re}\,s = \frac{1}{2}[/math]. Гипотеза Римана была сформулирована в XIX веке Риманом и вплоть до настоящего времени не поддается доказательству. Есть ряд численных экспериментов, свидетельствующих в ее пользу. Доказательство гипотезы Римана привело бы к уточнению закона распределения простых чисел.

[править] См. также

  • Решето Эратосфена — простой алгоритм нахождения всех простых чисел, не превышающих заданной границы.

[править] Литература

  • Бухштаб А. А. Теория чисел — М.: «Просвещение», 1966.
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты