Простое число
Простые числа — в математике, это натуральные числа помимо единицы, не делимые ни на одно натуральное число, кроме единицы и самого себя. Обычно простое число обозначается буквой p. Простых чисел бесконечно много. Является ли заданное число N простым можно проверить, последовательно деля его на все натуральные числа, меньшие его (достаточно проверить для чисел 2, 3, …, Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \sqrt{N}} ). Существует также детерминированный полиномиальный алгоритм проверки натурального числа на простоту. Согласно основной теореме арифметики, любое натуральное число, большее 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-х годов был найден детерминированный алгоритм проверки натурального числа на простоту за полиномиальное время от длины этого числа.
Асимптотический закон распределения[править]
→ Теорема о распределении простых чисел
Если обозначить количество простых чисел, меньших Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x} , через Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \pi(x)} , то эта функция асимптотически растет как Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x/\ln(x)} , то есть:
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lim\limits_{x \to +\infty} \frac{\pi(x)}{x/\ln x} = 1} .
Эквивалентным образом, Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k} -е простое число по возрастанию Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p_k} растет асимптотически как Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k\ln k} :
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lim\limits_{k \to \infty} \frac{p_k}{k\ln k} = 1} .
Асимптотический закон распределения простых чисел был полностью доказан в 1896 году независимо Адамаром и Валле-Пуссеном с использованием методов теории функций комплексного переменного. В XX веке было найдено доказательство элементарными методами.
В основе изучения свойств распределения простых чисел лежит дзета-функция Римана:
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \zeta(s) = \sum\limits_{n=1}^{\infty}\frac{1}{n^s},}
рассматриваемая как функция комплексной переменной Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle s} .
Этот ряд сходится, является аналитической функцией и допускает аналитическое продолжение на всю комплексную плоскость без единицы.
Тождество Эйлера иллюстрирует связь дзета-функции Римана с простыми числами:
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \zeta(s) = \prod\limits_p \frac{1}{1 - p^{-s}},}
где произведение берется по всем простым Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p} .
Проблемы[править]
С простыми числами связан ряд проблем, на протяжении десятилетий и даже веков не поддающихся решению. Одна из таких проблем — гипотеза Гольдбаха-Эйлера, сформулированная в XVIII веке: любое четное (натуральное) число, большее двух, можно представить в виде суммы двух простых чисел. Эта гипотеза до сих пор не доказана и не опровергнута. Более слабый вариант этой гипотезы, согласно которому каждое достаточно большое нечётное (натуральное) число можно представить в виде суммы трёх простых, был доказан в 1937 году И. М. Виноградовым, для всех нечётных натуральных чисел представимость их в виде суммы трех простых доказана в 2013 году перуанским математиком Харальдом Гельфготтом.
Гипотеза Римана гласит, что все комплексные нули дзета-функции, лежащие в полосе Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 0 \leqslant \operatorname{Re}\,s \leqslant 1} , находятся на прямой Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \operatorname{Re}\,s = \frac{1}{2}} . Гипотеза Римана была сформулирована в XIX веке Риманом и вплоть до настоящего времени не поддается доказательству. Есть ряд численных экспериментов, свидетельствующих в ее пользу. Доказательство гипотезы Римана привело бы к уточнению закона распределения простых чисел.
См. также[править]
- Решето Эратосфена — простой алгоритм нахождения всех простых чисел, не превышающих заданной границы.
Литература[править]
- Бухштаб А. А. Теория чисел — М.: «Просвещение», 1966.
Ссылки[править]
 Числовые системы ↑ | |
|---|---|
множества |
Натуральные числа (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{N}} ) • Целые (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{Z}} ) • Рациональные (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{Q}} ) • Алгебраические (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\overline{\mathbb{Q}}} ) • Периоды • Вычислимые |
и их расширения |
Действительные (вещественные) (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{R}} ) • Комплексные (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{C}} ) • Кватернионы (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{H}} ) • Числа Кэли (октавы, октонионы) (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{O}} ) • Седенионы (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle\mathbb{S}} ) • Альтернионы • Дуальные • Гиперкомплексные • Супердействительные • Гипервещественные |
числовые системы |
Кардинальные числа • Порядковые (трансфинитные, ординалы) • p-адические • Сверхнатуральные • Сюрреальные |
|
Двойные • Иррациональные • Трансцендентные • Числовой луч • Положительные числа • Простые числа • Бикватернионы • Координатизация • Расширение понятия числа | |