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

простое число, простое число это
Просто́е число́ — это натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя. Другими словами, число простое, если оно больше и делится без остатка только на и на .

Натуральные числа, большие единицы, не являющиеся простыми, называются составными. Таким образом, все натуральные числа разбиваются на три класса: единицу (имеющую один делитель), простые числа (имеющие два делителя) и составные числа (имеющие больше двух делителей). Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

Последовательность простых чисел начинается так:

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, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …

Содержание

  • 1 Разложение натуральных чисел в произведение простых
  • 2 Алгоритмы поиска и распознавания простых чисел
  • 3 Бесконечность множества простых чисел
  • 4 Наибольшее известное простое
  • 5 Простые числа специального вида
  • 6 Некоторые свойства
  • 7 Открытые вопросы
  • 8 Приложения
  • 9 Вариации и обобщения
  • 10 См. также
  • 11 Примечания
  • 12 Литература
  • 13 Ссылки

Разложение натуральных чисел в произведение простых

Основная статья: Факторизация целых чисел

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа — элементарные «строительные блоки» натуральных чисел.

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема RSA и некоторые другие. Факторизация с полиномиальной сложностью теоретически возможна на квантовом компьютере с помощью алгоритма Шора.

Алгоритмы поиска и распознавания простых чисел

Основная статья: Тест простоты Эратосфен Киренский

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

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

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор. Противоречие.

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма величин, обратных к первым n простым числам, неограниченно растёт с ростом n.

Теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое , растёт как .

Наибольшее известное простое

Основная статья: Наибольшее известное простое число

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в своё время Эйлер, найдя простое число .

Наибольшим известным простым числом по состоянию на август 2014 года является . Оно содержит 17 425 170 десятичных цифр и является простым числом Мерсенна (M57885161). Его нашли 25 января 2013 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

Простые числа специального вида

Существует ряд чисел, простота которых может быть установлена эффективно с использованием специализированных алгоритмов.

  • Числа Мерсенна — числа вида , где p — простое число. Как уже было отмечено выше, эффективным тестом простоты является тест Люка-Лемера.
  • Числа Ферма — числа вида , где n — неотрицательное целое число. Эффективным тестом простоты является тест Пепина. По состоянию на ноябрь 2011 года известно только 5 простых чисел Ферма (для n = 0, 1, 2, 3, 4), и высказана гипотеза, что других простых чисел Ферма нет.
  • Числа Вудала — числа вида . Эффективным тестом простоты является тест Люка — Лемера — Ризеля (англ.).

С использованием теста Бриллхарта — Лемера — Селфриджа (англ.) может быть проверена простота следующих чисел:

  • Числа Каллена — числа вида .
  • Числа Прота — числа вида , причем k нечётно и . Числа Каллена являются частным случаем чисел Прота при k = n. Числа Ферма являются частным случаем чисел Прота при k = 1 и .
  • Числа Миллcа — числа вида где  — константа Миллса.

Для поиска простых чисел обозначенных типов в настоящее время используются проекты распределенных вычислений GIMPS, PrimeGrid, Ramsey@Home, Seventeen or Bust, Riesel Sieve, Wieferich@Home.

Некоторые свойства

  • Если  — простое, и делит , то делит или . Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.
  • Кольцо вычетов является полем тогда и только тогда, когда  — простое.
  • Характеристика каждого поля — это ноль или простое число.
  • Если  — простое, а  — натуральное, то делится на (малая теорема Ферма).
  • Если  — конечная группа, порядок которой делится на , то содержит элемент порядка (теорема Коши).
  • Если  — конечная группа, и  — максимальная степень , которая делит , то имеет подгруппу порядка , называемую силовской подгруппой, более того, количество силовских подгрупп равно для некоторого целого (теоремы Силова).
  • Натуральное является простым тогда и только тогда, когда делится на (теорема Вильсона).
  • Если  — натуральное, то существует простое , такое, что (постулат Бертрана).
  • Ряд чисел, обратных к простым, расходится. Более того, при
  • Любая арифметическая прогрессия вида , где  — целые взаимно простые числа, содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
  • Всякое простое число, большее 3, представимо в виде или , где  — некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k>1) одинакова, то она обязательно кратна 6 — например: 251-257-263-269; 199-211-223; 20183-20201-20219.
  • Если  — простое, то кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3).
  • Теорема Грина-Тао. Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел.
  • Никакое простое число не может иметь вид , где n>2, k>1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид , то k — простое (см. числа Мерсенна).
  • Никакое простое число не может иметь вид , где n>1, k>0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бо́льшим 1.
  • Существуют многочлены, множество положительных значений которых при неотрицательных значениях переменных совпадает с множеством простых чисел. Одним из примеров является многочлен

содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа — 5 при 42 переменных; наименьшее число переменных — 10 при степени около 1,6·1045. Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества.

Открытые вопросы

Основная статья: Открытые проблемы в теории чисел Распределение простых чисел pn = f (Δsn); Δsn = pn+1² — pn². Δpn = pn+1 — pn; Δpn = 2, 4, 6, … .

До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе:

  1. Проблема Гольдбаха (первая проблема Ландау): верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел?
  2. Вторая проблема Ландау: бесконечно ли множество «простых близнецов» — простых чисел, разность между которыми равна 2? (в 2013 году математик Чжан Итан (Yitang Zhang) из университета Нью-Гэмпшира доказал, что существует бесконечно большое количество простых чисел, расстояние между которыми не превышает 70 миллионов. Позже, Джеймс Мэйнард (James Maynard) улучшил результат до 600. В 2014 году проект Polymath под руководством Теренса Тао несколько улучшили последний метод, получив оценку в 246.)
  3. Гипотеза Лежандра (третья проблема Ландау): верно ли, что для всякого натурального числа n между и всегда найдётся простое число?
  4. Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида , где n — натуральное число?

Открытой проблемой является также существование бесконечного количества простых чисел во многих целочисленных последовательностях, включая числа Фибоначчи, числа Ферма и т. д.

Приложения

Большие простые числа (порядка ) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ «Вихрь Мерсенна»).

Вариации и обобщения

  • В теории колец, разделе общей алгебры, определено понятие простого элемента и простого идеала.
  • В теории узлов определено понятие простого узла как нетривиального узла, который не может быть представлен в виде связной суммы нетривиальных узлов.

См. также

  • Незаконное простое число
  • Полупростое число
  • Примориал
  • Простые числа, отличающиеся на шесть
  • Случайное простое число
  • Составное число
  • Список простых чисел

Примечания

  1. Простое число // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 4.
  2. последовательность A000040 в OEIS, см. также список простых чисел
  3. Рекорды простых чисел по годам
  4. EFF Cooperative Computing Awards (англ.)
  5. последовательность A001348 в OEIS
  6. Простые числа Мерсенна образуют последовательность A000668 в OEIS
  7. последовательность A000215 в OEIS
  8. последовательность A003261 в OEIS
  9. Простые числа Вудала образуют последовательность A050918 в OEIS
  10. последовательность A002064 в OEIS
  11. Простые числа Каллена образуют последовательность A050920 в OEIS
  12. последовательность A080075 в OEIS
  13. Простые числа Прота образуют последовательность A080076 в OEIS
  14. Доказательство. Нечётное число p, не кратное 3, равно 1 или 2 по модулю 3 и равно 1, 3, 5 или 7 по модулю 8. При возведении в квадрат это даёт 1 по модулю 3 и 1 по модулю 8. Вычитая 1, получаем 0 по модулю 3 и 0 по модулю 8. Следовательно, кратно 3 и кратно 8; следовательно, оно кратно 24.
  15. Weisstein, Eric W. Теорема Грина-Тао (англ.) на сайте Wolfram MathWorld.
  16. Эти 2 свойства непосредственно следуют из формул разложения суммы и разности степеней.
  17. Jones J. P., Sato D., Wada H., Wiens D (1976). «Diophantine representation of the set of prime numbers». Amer. Math. Mon. 83 (6): 449–464.
  18. Yuri Matiyasevich, Diophantine Equations in the XX Century
  19. Matijasevic’s polynomial. The Prime Glossary.
  20. Weisstein, Eric W. Landau's Problems (англ.) на сайте Wolfram MathWorld.
  21. Неизвестный математик совершил прорыв в теории простых чисел-близнецов
  22. Bounded Gaps Between Primes

Литература

  • Гальперин Г. «Просто о простых числах» // Квант. — № 4. — С. 9-14,38.
  • Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1.
  • Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
  • Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2002. — 104 с. — 2000 экз. — ISBN 5-94057-060-7.. Архивировано из первоисточника 31 мая 2013
  • Кноп К. «В погоне за простотой»
  • Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.
  • Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker's Delight. — М.: «Вильямс», 2007. — 288 с. — ISBN 0-201-91465-4.
  • Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты = Prime Numbers: A Computational Perspective. — М.: УРСС, Либроком, 2011. — 664 с. — ISBN 978-5-397-02060-2.
  • Ю. Матиясевич. Формулы для простых чисел // Квант. — 1975. — № 5. — С. 5-13.
  • Н. Карпушина. Палиндромы и «перевёртыши» среди простых чисел // Наука и жизнь. — 2010. — № 5.
  • Д. Цагер. Первые 50 миллионов простых чисел // Успехи математических наук. — 1984. — Т. 39. — № 6(240). — С. 175–190.
  • Энрике Грасиан - "Простые числа. Долгая дорога к бесконечности" серия "Мир математики" том.3 Де Агостини 148с, 2014. ISBN: 978-5-9774-0682-6, 978-5-9774-0637-6

Ссылки

  • Математический проект «Простые числа»
  • Онлайн-утилита для проверки простых чисел
  • Программа расчёта простых чисел
  • The Prime Pages (англ.) — база данных наибольших известных простых чисел
  • PrimeGrid prime lists — все простые числа, найденные в рамках проекта PrimeGrid
  • Геометрия простых и совершенных чисел (исп.)
  • Geometrical connection between natural numbers and their factors
  • Скрипт визуализации

2701 простое число, как перевести дробь в простое число, какое наименьшее простое число, простое число, простое число определение, простое число это, самое большое простое число, случайное простое число, четное простое число, что такое простое число


Простое число Информацию О

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


  • user icon

    Простое число beatiful post thanks!

    29.10.2014


Простое число
Простое число
Простое число Вы просматриваете субъект
Простое число что, Простое число кто, Простое число описание

There are excerpts from wikipedia on this article and video

Случайные Статьи

Кварто

Кварто

Куарто (итал. Quarto) — коммуна в Италии, располагается в регионе Кампания, в провинции Не...
Уррусменди, Хосе Эусебио

Уррусменди, Хосе Эусебио

* Количество игр и голов за профессиональный клуб считается только для различных лиг нацио...
Go! Mokulele

Go! Mokulele

2009 Хабы международный аэропорт Гонолулу международный аэропорт Кона Бонусная программа ...
Саулкалне

Саулкалне

Са́улкалне (латыш. Saulkalne), — посёлок в Саласпилсском крае Латвии, расположен на правом бере...