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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Простые числа»)
Перейти к: навигация, поиск

Просто́е число́ (др.-греч. πρώτος ἀριθμός) — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя[1]. Другими словами, число является простым, если оно больше и при этом делится без остатка только на и на . К примеру,  — простое число, а является составным числом, так как, помимо и , также делится на и на . Основная теорема арифметики устанавливает основную роль простых чисел в теории чисел: любое целое число, больше, чем , является простым или может быть выражено как произведение простых чисел, которое является уникальным с точностью до порядка. Уникальность в этой теореме требует исключения как простого числа, потому что можно включать произвольно много 1 в любое разложение, например, , · , · · , и т. д. являются разложением на множители числа .

Свойство числа быть простым называется простотой. Простой, но медленный метод проверки простоты заданного числа n известен как перебор делителей. Он состоит из проверки того, является ли кратным целому числу от до . Алгоритмы, намного более эффективные, чем перебор делителей, были разработаны для проверки простоты больших чисел. К ним относятся Тест Миллера-Рабина, который является быстрым, но имеет небольшую вероятность ошибки и тест AKS, который всегда дает правильный ответ за полиномиальное время, но слишком медленный, чтобы быть использованным. Особенно быстрые методы вычисления доступны для чисел имеющих особые формы, таких как числа Мерсенна. По состоянию на январь 2016 года наибольшее известное простое число имеет 22 338 618 десятичных цифр.

Многие вопросы, касающиеся простых чисел, остаются открытыми, например, гипотеза Гольдбаха (каждое четное целое число больше 2 может быть выражено как сумма двух простых чисел) и гипотеза Харди — Литтлвуда (существует бесконечно много пар простых чисел, разность которых равна 2), такие вопросы стимулировали развитие различных отраслей теории чисел, фокусируясь на аналитических или алгебраических аспектах чисел. Простые числа используются в нескольких подпрограммах в области информационных технологий, таких как криптосистема с открытым ключом, которая использует такие свойства, как сложность разложения чисел на простые множители. Простые числа порождают различные обобщения в других математических областях, в основном алгебре, таких как простые элементы и простые идеалы.

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

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

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, 163, 167, 173, 179, 181, 191, 193, 197, 199[2]

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

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

Основная теорема арифметики[править | править код]

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

. ( обозначает квадратную или вторую степень .)

Как и в этом примере, один и тот же простой делитель может появляться несколько раз. Разложение:

n = p1 · p2 · ... · pt

числа n на (конечное число) простых множителей p1, p2, ... ,pt называется разложением на простые множители числа n. Основная теорема арифметики может быть перефразирована, чтобы сказать, что любое разложение на простые числа будет тождественным, за исключением порядка делителей. Таким образом, на практике для большинства чисел есть много простых алгоритмов разложения на множители, все они должны дать тот же результат.

Если p - простое число и p делит произведение ab целых чисел, то p делит a или p делит b. Это предложение известно как Лемма Евклида.[4] Она используется в некоторых доказательствах уникальности разложения на множители.

Простота единицы[править | править код]

Большинство древних греков даже не считали числом, поэтому они не могли считать его простым.[5] К Средним векам и эпохе Возрождения многие математики включали в качестве первого простого числа.[6] В середине 18-го века Христиан Гольдбах внес в список в качестве первого простого числа в своей знаменитой переписке с Леонардом Эйлером; однако сам Эйлер не считал простым числом.[7] В 19-м веке многие математики по-прежнему считали число простым числом. Например, список простых цифр Деррика Нормана Лемера до числа, переизданный 1956 году, начинался с в качестве первого простого числа. Говорят, что Анри Лебег является последним математиком, который назвал простым.[8] К началу 20-го века математики стали приходить к консенсусу о том, что не является простым числом, а скорее формирует свою специальную категорию - «единицу».[6]

Большая часть математической работы по-прежнему будет верной при назывании простым числом, но основная теорема Евклида об арифметике (упомянутая выше) не будет выполняться, как указано. Например, число может быть разложено как 3 · 5 и 1 · 3 · 5; если бы была допущена в качестве простого числа, эти два варианта считались бы разной факторизацией в простые числа, следовательно утверждение этой теоремы пришлось бы изменить. Точно так же решето Эратосфена не будет работать правильно, если бы считалась простым: модифицированная версия решета, которая предполагает, что является простым числом, исключает все множители кратные (то есть все остальные числа) и дает на выходе только одно число - . Кроме того, простые числа имеют несколько свойств, которых нет у числа , таких как отношение числа к его соответствующему значению функции тождества Эйлера или суммы функции делителей.[9]

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

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

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

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

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

Простых чисел бесконечно много. Это утверждение упоминается как теорема Евклида в честь древнегреческого математика Евклида, поскольку первое известное доказательство этого утверждения приписывается ему. Известно еще много доказательств бесконечности простых чисел, в том числе аналитическое доказательство Эйлера, доказательство Голдбаха на основе чисел Ферма,[10] доказательство Фурстенберга с использованием общей топологии и элегантное доказательство Куммера.

Доказательство Евклида[править | править код]

Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20[11]). Доказательство рассматривает любое конечное множество S простых чисел. Основная идея - рассмотреть произведение всех этих чисел плюс один:

Как и любое другое натуральное число, N делится хотя бы на одно простое число (возможно, что N является простым).

Ни один из простых делителей числа N, не может быть членом конечного множества S простых чисел, с которого мы начали, поскольку при делении числа N на любое число из множества S дает остаток равный 1. Следовательно простые числа, по которым N раскладывается на множители, являются простыми числами находящимися вне изначального множества. Таким образом, любое конечное множество простых чисел можно расширить на большее конечное множество простых чисел.

Часто ошибочно сообщается, что Евклид начинает с предположения, что первоначально рассмотренное множество содержит все простые числа, что приводит к противоречию или что оно содержит именно n наименьших простых чисел, а не любое произвольное конечное множество простых чисел.[12] Произведение наименьших n простых чисел плюс 1 обычно называется n-м Евклидовым числом.

Доказательство Евклида может быть кратко воспроизведено так:

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

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

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

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

Для любого произвольного вещественного числа х существует простое р, для которого эта частичная сумма больше чем х. [13] Это показывает, что существует бесконечно много простых чисел, так как если бы их существовало конечное число, то сумма достигала бы максимального значения в наибольшем простом числе, а не была бы неограниченной. Точнее, скорость роста S(p) двукратно логарифмическая, что определяется второй теоремой Мертенса. Для сравнения, сумма

не стремится к бесконечности, когда n стремится к бесконечности (см. задачу Базеля). В этом смысле простые числа встречаются чаще, чем квадраты натуральных чисел. Теорема Бруна утверждает, что сумма обратных парных простых чисел,

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

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

Наибольшее известное простое[править | править код]

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа[14]. Один из рекордов поставил в своё время Эйлер, найдя простое число 231 − 1 = 2 147 483 647.

Наибольшим известным простым числом по состоянию на январь 2016 года является 274 207 281 − 1. Оно содержит 22 338 618 десятичных цифр и является простым числом Мерсенна (M74 207 281). Его нашли 17 сентября 2015 года в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS, однако все проверки завершились лишь 7 января 2016 года[15].

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

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

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

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

  • Числа Мерсенна — числа вида , где n — натуральное число[17]. При этом число Мерсенна может быть простым, только если n — простое число. Как уже было отмечено выше, эффективным тестом простоты является тест Люка — Лемера[18].
  • Числа Ферма — числа вида , где n — неотрицательное целое число[19]. Эффективным тестом простоты является тест Пепина. По состоянию на февраль 2015 года известно только 5 простых чисел Ферма (для n = 0, 1, 2, 3, 4), двадцать восемь следующих чисел Ферма (до включительно) оказались составными[20], однако не доказано, что других простых чисел Ферма нет[21].
  • Числа Вудала — числа вида [22]. Эффективным тестом простоты является тест Люка — Лемера — Ризеля[23].
  • Числа Каллена — числа вида [24][25].
  • Числа Прота — числа вида , причём k нечётно и [26]. Эффективным тестом простоты для чисел Прота является тест Бриллхарта — Лемера — Селфриджа (англ. Brillhart–Lehmer–Selfridge test)[27]. Числа Каллена и числа Ферма являются частным случаем чисел Прота (соответственно при k = n и при k = 1, )[28].
  • Числа Миллса — числа вида где  — константа Миллса.

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

Некоторые свойства[править | править код]

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

Формулы для нахождения простых чисел[править | править код]

В разное время предпринимались попытки указать выражение, значениями которого при разных значениях входящих в него переменных были бы простые числа[29]. Л. Эйлер указал многочлен принимающий простые значения при n = 0, 1, 2, …, 40. Однако при n = 41 значение многочлена является составным числом. Можно доказать, что не существует многочлена от одной переменной n, который принимает простые значения при всех целых n[29]. П. Ферма предположил, что все числа вида 22k + 1 простые; однако Эйлер опроверг эту гипотезу, доказав, что число 225 + 1 = 4 294 967 297 — составное[29].

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

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

Открытые вопросы[править | править код]

Распределение простых чисел pn = fsn); Δsn = pn+1² — pn². Δpn = pn+1 — pn; Δpn = 2, 4, 6, … .

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

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

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

Приложения[править | править код]

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

Вариации и обобщения[править | править код]

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

Примечания[править | править код]

  1. Простое число // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 4.
  2. Последовательность A000040 в OEIS, см. также список простых чисел
  3. Dudley, Underwood (1978), Elementary number theory (2nd ed.), W. H. Freeman and Co., ISBN 978-0-7167-0076-0 , Section 2, Theorem 2  (англ.)
  4. Dudley, Underwood (1978), Elementary number theory (2nd ed.), W. H. Freeman and Co., ISBN 978-0-7167-0076-0 , Section 2, Lemma 5  (англ.)
  5. См, например, David E. Joyce's комментарий на Начала (Евклид), Книга VII, определения 1 и 2.
  6. 1 2 Why is the number one not prime? (from the Prime Pages' list of frequently asked questions) by Chris K. Caldwell.  (англ.)
  7. See for instance: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160-188. Variae observationes circa series infinitas, Theorema 19, p.187. (англ.)
  8. Derbyshire, John (2003), "The Prime Number Theorem", Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Washington, D.C.: Joseph Henry Press, с. 33, ISBN 978-0-309-08549-6, OCLC 249210614  (англ.)
  9. ""Arguments for and against the primality of 1". (англ.)
  10. Letter in Латынь from Goldbach to Euler, July 1730.
  11. James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63, English translation of Euclid's proof (англ.)
  12. Hardy, Michael (2009). «Prime Simplicity». Mathematical Intelligencer 31 (4): 44–52. DOI:10.1007/s00283-009-9064-8. (англ.)
  13. Apostol, Tom M. (1976), Introduction to Analytic Number Theory, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90163-3 , Section 1.6, Theorem 1.13 (англ.)
  14. Рекорды простых чисел по годам
  15. Mersenne Prime Number discovery - 274 207 281 - 1 is Prime!
  16. EFF Cooperative Computing Awards (англ.)
  17. Последовательность A001348 в OEIS
  18. Последовательность A000668 в OEIS: простые числа Мерсенна
  19. Последовательность A000215 в OEIS
  20. Keller, Wilfrid (February 15, 2015), Prime Factors of Fermat Numbers, <http://www.prothsearch.net/fermat.html#Summary>. Проверено 1 марта 2016. 
  21. Виолант-и-Хольц, Альберт. Загадка Ферма. Трёхвековой вызов математике. — М.: Де Агостини, 2014. — С. 78. — 151 с. — (Мир математики: в 45 томах, том 9). — ISBN 978-5-9774-0625-3.
  22. Последовательность A003261 в OEIS
  23. Последовательность A050918 в OEIS: простые числа Вудала
  24. Последовательность A002064 в OEIS
  25. Последовательность A050920 в OEIS: простые числа Каллена
  26. Последовательность A080075 в OEIS
  27. John Brillhart (April 1975). «New Primality Criteria and Factorizations of 2^m ± 1». Mathematics of Computation 29: 620–647. DOI:10.1090/S0025-5718-1975-0384673-1.
  28. Последовательность A080076 в OEIS: простые числа Прота
  29. 1 2 3 4 5 6 7 Энциклопедический словарь юного математика, 1985.
  30. Доказательство. Нечётное число p, не кратное 3, равно 1 или 2 по модулю 3 и равно 1, 3, 5 или 7 по модулю 8. При возведении в квадрат это даёт 1 по модулю 3 и 1 по модулю 8. Вычитая 1, получаем 0 по модулю 3 и 0 по модулю 8. Следовательно, кратно 3 и кратно 8; следовательно, оно кратно 24.
  31. Weisstein, Eric W. Green-Tao Theorem (англ.) на сайте Wolfram MathWorld.
  32. Эти 2 свойства непосредственно следуют из формул разложения суммы и разности степеней.
  33. 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.
  34. Yuri Matiyasevich, Diophantine Equations in the XX Century
  35. Matijasevic’s polynomial. The Prime Glossary.
  36. Weisstein, Eric W. Landau's Problems (англ.) на сайте Wolfram MathWorld.
  37. Неизвестный математик совершил прорыв в теории простых чисел-близнецов
  38. Bounded Gaps Between Primes

Литература[править | править код]

Ссылки[править | править код]