Что такое Простые числа
Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23. Единица не является ни простым числом, ни составным.
Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).
Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).
Все натуральные числа считаются либо простыми, либо составными (кроме 1).
Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4. (нет ни дробей, ни 0, ни чисел ниже 0).
Зачастую множество простых чисел в математике обозначается буквой P.
Простые числа до 1000
Как определить, является ли число простым?
Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.
Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).
Более структурированный метод — это решето Эратосфена.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
- Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
- Вычеркнуть все числа, которые делятся на 2 (кроме 2);
- Вычеркнуть все числа, которые делятся на 3 (кроме 3);
- И так далее по порядку со всеми невычеркнутыми числами до числа n (после 3 это 5, 7, 11, 13, 17 и т. д.).
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Взаимно простые числа
Это натуральные числа, у которых 1 — это единственный общий делитель. Например:
- 14 (это 2 х 7) и 15 (это 3 х 5), единственный общий делитель — 1; если числа следуют одно за другим (как 13 и 12 либо 10 и 11), то они всегда будут взаимно простыми;
- 7 (это 7 х 1) и 11 (это 11 х 1) — это два простых числа, а значит единственный общий делитель всегда будет только единица, простые числа всегда являются взаимно простыми;
- или 30 и 48 не являются взаимно простыми, т. к. 6 х 5 = 30 и 6 х 8 = 48 и 6 — это наибольший общий делитель, т. е.: НОД (30; 48) = 6.
Число Мерсенна
Простое число Мерсенна — это простое число вида:
До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).
Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.
Почему 1 не является простым числом?
Российские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.
Почему 4 не является простым числом?
Простое число — это натуральное число, больше единицы, которое делится без остатка на 1 и на само себя. Т. к. 4 можно разделить на 1, на 2 и на 4, из-за деления на 2 оно не является простым.
Самое большое простое число
21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:
Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).
Простые числа в математике
Простые числа — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.
Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом.
13 ÷ 4 = 3 (остаток 1).
Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.
30 не является примером простого числа, потому что его можно разделить на 1,2,3,5,6,10,15,30. Таким образом, 30 является примером составного числа, поскольку оно имеет более двух факторов.
Ноль, единица и числа меньше единицы не считаются простыми числами.
Основная теорема арифметики, лемма Евклида
Основная идея теоремы арифметики — это любое целое число больше 1 либо является простым числом, либо может быть получено путем умножения простых чисел вместе.
Фундаментальная теорема арифметики (название которой указывает на ее основную важность) гласит, что любое число может быть учтено в уникальном списке простых чисел.
Простое число (2,3,5,7,11. ) против составного (4=2×2, 6=2×3, 8=2x2x2, 12=2x2x3. ).
Этот ряд примеров можно продолжить:
- 10 равно 2×5;
- 11 — простое число;
- 12 — 2×2×3;
- 13 — это простое число;
- 14 равно 2×7;
- 15 равно 3×5;
- 16 равно 2×2×2×2;
- 17 является простым и т.д.
Таким образом, они либо простые, либо простые числа, умноженные друг на друга.
Число 42. Можем ли мы получить 42, умножив только простые числа?
Да, 2, 3 и 7 являются простыми числами, и при умножении вместе они составляют 42.
Число 7. 7 уже является простым числом
Число 22. 22 может быть получено путем умножения простых чисел 2 и 11 вместе.
Никакая другая комбинация простых чисел не будет работать.
Лемма — это, как правило, незначительное, доказанное утверждение, которое используется в качестве ступеньки к доказательству более сложной математической теории. По этой причине она также известна как «вспомогательная теорема».
В теории чисел лемма Евклида — это лемма, которая отражает фундаментальное свойство простых чисел, а именно: если простое число p делит произведение ab двух целых чисел a и b, то p должно разделить, по крайней мере, одно из этих целых чисел a и b.
Если p = 19, a = 133, b = 143, то ab = 133 × 143 = 19019, и поскольку это делится на 19, лемма подразумевает, что один или оба из 133 или 143 также должны быть. На самом деле 133 = 19 × 7.
Если предпосылка леммы не выполняется, т. е. p является составным числом, его следствие может быть либо истинным, либо ложным.
В случае p = 10, a = 4, b = 15 составное число 10 делит ab = 4 × 15 = 60, но 10 не делит ни 4, ни 15.
Это свойство является ключевым в доказательстве фундаментальной теоремы арифметики. Лемма Евклида показывает, что в целых числах неприводимые элементы также являются простыми элементами.
Таким образом, изучение чисел в основном сводится к изучению свойств простых чисел. Математики на протяжении тысячелетий довольно много выяснили о простых числах. Одно из самых известных доказательств Евклида показывает, что существует бесконечно много простых чисел.
Как определить простые числа
Сначала попробуйте разделить его на 2 и посмотреть, получится ли целое число. Если да, то оно не может быть простым числом. Если вы не получите целое число, затем попробуйте разделить его на простые числа: 3, 5, 7, 11 (9 делится на 3) и так далее, всегда делясь на простое число.
8 простых чисел до 20: 2, 3, 5, 7, 11, 13, 17 и 19.
Первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Таблица простых чисел до 1000:
| 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 | 211 | 223 | 227 |
| 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |
| 281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 |
| 349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 |
| 409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 |
| 463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |
| 541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 |
| 601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 |
| 659 | 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |
| 733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 |
| 809 | 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |
| 863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 |
| 941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
2 — наименьшее простое число. Это также единственное четное простое число — все остальные четные числа могут быть разделены сами по себе на 1 и 2, что означает, что у них будет, по крайней мере, 3 фактора.
Один из самых известных математиков классической эпохи, Евклид, записал доказательство того, что не существует самого большого простого числа. Самое большое известное простое число (по состоянию на ноябрь 2020 года) составляет 282 589 933-1, число, которое имеет 24 862 048 цифр при записи в базе 10. До этого самым большим известным простым числом было 277 232 917-1, состоящее из 23 249 425 цифр.
За исключением 2 и 3, все остальные простые числа могут быть выражены в общей форме как 6n + 1 или 6n — 1, где n — натуральное число.
Чтобы определить, является ли число простым или составным, нужно решить пример на делимость в следующем порядке (от простого к сложному): 2, 5, 3, 11, 7, и 13. Если вы обнаружите, что число делится на одно из них, и вы знаете, что оно составное, не нужно выполнять остальные тесты.
Если число меньше 121 не делится на 2, 3, 5 или 7, оно простое; в противном случае оно составное.
Если число меньше 289 не делится на 2, 3, 5, 7, 11, или 13, это простое число; в противном случае оно составное.
Примеры решения задач
Является ли 19 простым числом или нет?
Как понять, что число простое можно двумя способами.
Формула для простого числа равна 6n + 1
Запишем данное число в виде 6n + 1.
6(3) + 1 = 18 + 1 = 19
Проверьте на наличие факторов 19
Следовательно, с помощью обоих методов докажем, что 19 имеет только два фактора 1 и 19, что означает простое число.
53 — это простое число или нет?
Как доказать, что число простое, используя приведенную ниже формулу. Чтобы узнать простые числа, превышающие 40, можно:
n2 + n + 41, где n = 0, 1, 2, . 39
32 + 3 + 41 = 9 + 3 + 41 = 53
53 имеет только факторы 1 и 53.
Итак, 53 является простым числом по обоим методам.
Является ли число простым или составным?
Число 185 заканчивается на 5, поэтому оно делится на 5. Оно составное.
Как проверить простое ли число 243?
Число 243 заканчивается нечетным числом, поэтому оно не делится на 2. Он не заканчивается на 5 или 0, поэтому он не делится на 5. Его цифровой корень равен 9 (потому что 2 + 4 + 3 = 9), так что оно делится на 3.
Доступное объяснение гипотезы Римана
Вы ведь помните, что такое «простые числа»? Эти числа не делятся ни на какие другие, кроме самих себя и 1. А теперь я задам вопрос, которому уже 3000 лет:
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, p. Чему равно p? 31. Каким будет следующее p? 37. А следующее p ? 41. А следующее? 43. Да, но… как нам узнать, каким будет следующее значение?
Введение
Свойства простых чисел изучались многими великими людьми в истории математики. С первого доказательства бесконечности простых чисел Евклида до формулы произведения Эйлера, связавшей простые числа с дзета-функцией. От формулировки теоремы о простых числах Гаусса и Лежандра до её доказательства, придуманного Адамаром и Валле-Пуссеном. Тем не менее, Бернхард Риман до сих пор считается математиком, сделавшим единственное крупнейшее открытие в теории простых чисел. В его опубликованной в 1859 году статье, состоявшей всего из восьми страниц, были сделаны новые, ранее неизвестные открытия о распределении простых чисел. Эта статья по сей день считается одной из самых важных в теории чисел.
После публикации статья Римана оставалась главным трудом в теории простых чисел и на самом деле стала основной причиной доказательства в 1896 году теоремы о распределении простых чисел. С тех пор было найдено несколько новых доказательств, в том числе элементарные доказательства Сельберга и Эрдёша. Однако до сих пор остаётся загадкой гипотеза Римана о корнях дзета-функции.
Сколько всего простых чисел?
Давайте начнём с простого. Все мы знаем, что число является или простым, или составным. Все составные числа состоят из простых и могут быть разложены на их произведения (a x b). В этом смысле простые числа являются «строительными блоками» или «фундаментальными элементами» чисел. В 300 году до нашей эры Евклид доказал, что их количество бесконечно. Его изящное доказательство имеет следующий вид:
Предположим, что множество простых чисел не бесконечно. Создадим список всех простых чисел. Тогда P пусть будет произведением всех простых чисел списка (перемножим все простые числа из списка). Прибавим к результату 1: Q = P +1. Как и все числа, это натуральное число Q должно быть или простым, или составным:
- Если Q простое, то мы нашли простое число, которого нет в нашем «списке всех простых чисел».
- Если Q не простое, то оно составное, т.е. составлено из простых чисел, одно из которых, p, будет делителем Q (потому что все составные числа являются произведениями простых). Каждое простое p, из которого составлено P, очевидно является делителем P. Если p является делителем и для P, и для Q, то оно должно быть и делителем для их разности, то есть единицы. Ни одно простое число не является делителем 1, поэтому число p не может находиться в списке — ещё одно противоречие тому, что список содержит все простые числа. Всегда будет существовать ещё одно простое p, не находящееся в списке и являющееся делителем Q. Следовательно, простых чисел бесконечно много.
Почему простые числа так сложно понять?
Сам факт того, что любой новичок понимает изложенную выше задачу, красноречиво говорит о её сложности. Даже арифметические свойства простых чисел, несмотря на активное изучение, плохо нами понимаются. Научное сообщество настолько уверено в нашей неспособности понимать поведение простых чисел, что разложение на множители больших чисел (определение двух простых чисел, произведением которых является число) остаётся одной из фундаментальных основ теории шифрования. На это можно смотреть следующим образом:
Мы хорошо понимаем составные числа. Это все числа, не являющиеся простыми. Они состоят из простых чисел, но мы можем с лёгкостью написать формулу, прогнозирующую и/или генерирующую составные числа. Такой «фильтр составных чисел» называется решетом. Самым знаменитым примером является так называемое «решето Эратосфена», придуманное примерно в 200 году до нашей эры. Его работа заключается в том, что оно просто помечает значения, кратные каждому простому числу вплоть до заданной границы. Допустим, возьмём простое число 2, и пометим 4,6,8,10, и так далее. Затем возьмём 3, и пометим 6,9,12,15, и так далее. В результате у нас останутся только простые числа. Хоть его очень легко понять, решето Эратосфена, как вы можете представить, не особо эффективно.
Одной из функций, серьёзно упрощающих нашу работу, будет 6n ± 1. Эта простая функция выдаёт все простые числа, за исключением 2 и 3, и удаляет все числа, кратные 3, а также все чётные числа. Подставим n = 1,2,3,4,5,6,7 и получим следующие результаты: 5,7,11,13,17,19,23,25,29,31,35,37,41,43. Единственными не простыми числами, сгенерированными функцией, являются 25 и 35, которые можно разложить на множители 5 x 5 и 5 x 7. Следующими не простыми числами, как вы могли догадаться, будут, 49 = 7 x 7, 55 = 5 x 11, и так далее. Всё легко, правда?
Для визуального отображения этого я использовал то, что называю «лестницей составных чисел» — удобный способ показать, как расположены и сочетаются сгенерированные функцией составные числа. В первых трёх столбцах показанного ниже изображения мы видим, как красиво поднимаются по каждой лестнице составных чисел простые числа 5, 7 и 11, вплоть до значения 91. Хаос, возникающий в четвёртом столбце, показывающем, как решето убрало всё, кроме простых чисел — отличная иллюстрация того, почему простые числа так сложно понять.
Фундаментальные ресурсы
Как же это всё связано с понятием, о котором вы могли слышать — с «гипотезой Римана»? Ну если говорить просто, то чтобы больше понять о простых числах, математики в 19-м веке перестали пытаться спрогнозировать местонахождение простых чисел с абсолютной точностью, и вместо этого начали рассматривать феномен простых чисел в целом. Мастером этого аналитического подхода стал Риман, и в рамках такого подхода была создана его знаменитая гипотеза. Однако прежде чем я начну её объяснять, необходимо познакомиться с некоторыми фундаментальными ресурсами.
Гармонические ряды
Гармонические ряды — это бесконечные ряды чисел, которые впервые исследовал в 14-м веке Николай Орем. Его имя связано с концепцией музыкальных гармоник — обертонов, которые выше частоты основного тона. Ряды имеют следующий вид:
Первые члены бесконечного гармонического ряда
Орем доказал, что эта сумма является несходящейся (то есть не имеющей конечного предела; она не приближается и не стремится к какому-то определённому числу, а устремлена в бесконечность).
Дзета-функции
Гармонические ряды являются особым случаем более общего типа функций под названием дзета-функция ζ(s). Вещественная дзета-функция задаётся для двух вещественных чисел r и n:
Дзета-функция
Если подставить n = 1, то мы получим гармонический ряд, который расходится. Однако при всех значениях n > 1 ряд сходится, то есть сумма при увеличении r стремится к некому числу, а не уходит в бесконечность.
Формула произведения Эйлера
Первая связь между дзета-функциями и простыми числами была установлена Эйлером, когда он показал, что для двух натуральных (целочисленных и больше нуля) чисел n и p, где p является простым, справедливо следующее:
Произведение Эйлера для двух чисел n и p, где оба больше нуля, а p является простым.
Это выражение впервые появилось в статье 1737 года под названием Variae observationes circa series infinitas. Из выражения следует, что сумма дзета-функции равна произведению величин, обратной единице, минус величина, обратная простым числам в степени s. Эта потрясающая связь заложила фундамент современной теории простых чисел, в которой с тех пор дзета-функция ζ(s) начала использоваться как способ изучения простых чисел.
Доказательство формулы — это одно из самых любимых моих доказательств, поэтому я изложу его, хоть для наших целей это и не обязательно (но настолько же оно прекрасно!):
Доказательство формулы произведения Эйлера
Эйлер начинает с общей дзета-функции
Дзета-функция
Сначала он умножает обе части на второй член:
Дзета-функция, умноженная на 1/2 s
Затем он вычитает получившееся выражение из дзета-функции:
Дзета-функция минус 1/2 s , умноженное на дзета-функцию
Он повторяет этот процесс, далее умножая обе стороны на третий член
Дзета-функция минус 1/2 s , умноженное на дзета-функцию, умноженное на 1/3 s
А затем вычитает получившееся выражение из дзета-функции
Дзета-функция минус 1/2 s , умноженное на дзета-функцию минус 1/3 s , умноженное на дзета-функцию
Если повторять этот процесс до бесконечности, в конце концов у нас останется выражение:
1 минус все величины, обратные простым числам, умноженное на дзета-функцию
Если этот процесс вам знаком, то это потому, что Эйлер по сути создал решето, очень похожее на решето Эратосфена. Он отфильтровывает из дзета-функции числа, не являющиеся простыми.
Затем разделим выражение на все его члены, являющимися обратными простым числам величинами, и получим:
Функциональная связь дзета-функции с простыми числами для первых простых чисел 2,3,5,7 и 11
Упростив выражение, мы показали следующее:
Формула произведения Эйлера — равенство, показывающее связь между простыми числами и дзета-функцией
Разве это было не красиво? Подставим s = 1, и найдём бесконечный гармонический ряд, повторно доказав бесконечность простых чисел.
Функция Мёбиуса
Август Фердинанд Мёбиус переписал произведение Эйлера, создав новую сумму. Кроме величин, обратных простым числам, функция Мёбиуса также содержит каждое натуральное число, являющееся произведением чётного и нечётного количества простых множителей. Числа, исключённые из его ряда — это такие числа, которые делятся на какое-то простое число в квадрате. Его сумма, обозначаемая как μ(n), имеет следующий вид:
Функция Мёбиуса — изменённая версия произведения Эйлера, заданная для всех натуральных чисел
Сумма содержит величины, обратные:
- Каждому простому числу;
- Каждому натуральному числу, являющемуся произведением нечётного количества разных простых чисел, взятому со знаком «минус»; и
- Каждому натуральному числу, являющемуся произведением чётного количества различных простых чисел, взятому со знаком «плюс»;
Ряд/сумма единиц, разделённых на дзета-функцию ζ(s)
Сумма не содержит те обратные величины, которые делятся на квадрат одного из простых чисел, например, 4,8,9, и так далее.
Функция Мёбиуса μ(n) может принимать только три возможных значения: префикс (1 или -1) или удаление (0) членов из суммы:
Три возможных значения функции Мёбиуса μ(n)
Хотя впервые эта хитрая сумма была формально определена Мёбиусом, примечательно, что за 30 лет до него об этой сумме писал в заметках на полях Гаусс:
Функция распределения простых чисел
Вернёмся к простым числам. Чтобы понять, как распределяются простые числа при движении вверх по числовой прямой, не зная точно, где они находятся, полезно будет подсчитать, сколько их встречается до определённого числа.
Именно эту задачу выполняет предложенная Гауссом функция распределения простых чисел π(x): она даёт нам количество простых чисел, меньших или равных заданному вещественному числу. Поскольку мы не знаем формул для нахождения простых чисел, формула распределения простых чисел известна нам только как график, или ступенчатая функция, увеличивающаяся на 1, когда x является простым числом. На графике ниже показана функция до x = 200.
Функция распределения простых чисел π(x) до значения x = 200.
Теорема о распределении простых чисел
Теорема о распределении простых чисел, сформулированная Гауссом (и независимо от него Лежандром), гласит:
Теорема о распределении простых чисел
Обычным языком это можно изложить так: «При движении x к бесконечности функция распределения простых чисел π(x) будет приближаться к функции x/ln(x)». Другими словами, если забраться достаточно далеко, и график распределения простых чисел поднимется до очень высокого числа x, то при делении x на натуральный логарифм x соотношение этих двух функций будет стремиться к 1. Ниже на графике показаны две функции для x = 1000:
Функция распределения простых чисел π(x) и приблизительная оценка по теореме распределения простых чисел до x = 1000
С точки зрения вероятностей, теорема о распределении простых чисел гласит, что если случайным образом выбрать натуральное число x, то вероятность P(x) того, что это число будет простым, примерно равно 1 / ln(x). Это означает, что средний разрыв между последовательными простыми числами среди первых x целочисленных значений приблизительно равен ln(x).
Интегральный логарифм
Функция Li(x) определена для всех положительных вещественных чисел, за исключением x = 1. Она задаётся интегралом от 2 до x:
Интегральное представление функции интегрального логарифма
Построив график этой функции рядом с функцией распределения простых чисел и формулой из теоремы о распределении простых чисел, мы видим, что Li(x) на самом деле является лучшим приближением, чем x/ln(x):
Интегральный логарифм Li(x), функция рапределения простых чисел π(x) и x/ln(x) на одном графике
Чтобы узнать, насколько лучше это приближение, мы можем построить таблицу с большими значениями x, количеством простых чисел до x и величиной погрешности между старой (теорема о распределении простых чисел) и новой (интегральный логарифм) функциями:
Количество простых чисел до заданной степени десятки и соответствующие погрешности для двух приближений
Как легко можно заметить, интегральный логарифм намного лучше в приближении, чем функция из теоремы о распределении простых чисел, он «ошибся» в большую сторону всего на 314 890 простых чисел для x = 10 в степени 14. Тем не менее, обе функции сходятся к функции распределения простых чисел π(x). Li(x) сходится гораздо быстрее, но при стремлении x к бесконечности соотношение между функцией распределения простых чисел и функциями Li(x) и x/ln(x) приближается к 1. Покажем это наглядно:
Схождение соотношений двух приближенных значений и функции распределения простых чисел к 1 при x = 10 000
Гамма-функция
Гамма-функция Γ(z) стала важным объектом для изучения с тех пор, когда в 1720-х годах Даниил Бернулли и Христиан Гольдбах исследовали задачу обобщения функции факториала на нецелые аргументы. Это обобщение функции факториала n! (1 x 2 x 3 x 4 x 5 x …. n), сдвинутое вниз на 1:
Гамма-функция, определённая для z
Её график очень любопытен:
График гамма-функции Γ(z) в интервале -6 ≤ z ≤ 6
Гамма-функция Γ(z) определена для всех комплексных значений z больше нуля. Как вы наверно знаете, комплексные числа — это класс чисел с мнимой частью, записываемых как Re(z) + Im(z), где Re(z) — это вещественная часть (обычное вещественное число), а Im(z) — мнимая часть, обозначаемая буквой i. Комплексное число обычно записывается в виде z = σ + it, где сигма σ — вещественная часть, а it — мнимая. Комплексные числа полезны тем, что они позволяют математикам и инженерам работать с задачами, недоступными обычным вещественным числам. В графическом виде комплексные числа расширяют традиционную одномерную числовую прямую в двухмерную числовую плоскость, называемую комплексной плоскостью, в которой вещественная часть комплексного числа откладывается по оси x, а мнимая — по оси y.
Чтобы гамма-функцию Γ(z) можно было использовать, её обычно переписывают в виде
Функциональная связь гамма-функции Γ(z)
С помощью этого равенства мы можем получить значения для z ниже нуля. Однако оно не даёт значений для отрицательных целых чисел, потому что они не определены (формально они являются вырожденностями или простыми полюсами).
Дзета и гамма
Связь между дзета-функцией и гамма-функцией задаётся следующим интегралом:
Дзета-функция Римана
Ознакомившись со всеми необходимыми фундаментальными ресурсами, мы можем наконец приступать к установлению связи между простыми числами и гипотезой Римана.
Немецкий математик Бернхард Риман родился в 1826 году в Брезеленце. Будучи студентом Гаусса, Риман опубликовал работу в области математического анализа и геометрии. Считается, что наибольший вклад он внёс в области дифференциальной геометрии, где заложил фундамент языка геометрии, позже использованного Эйнштейном в общей теории относительности.
Его единственный труд в теории чисел, статья 1859 года Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse («О простых числах меньше заданной величины») считается самой важной статьёй в этой области математики. Всего на четырёх страницах он изложил:
- Определение дзета-функции Римана ζ(s) — дзета-функции с комплексными значениями;
- Аналитическое продолжение дзета-функции на все комплексные числа s≠1;
- Определение кси-функции Римана ξ(s) — целой функции, связанной с дзета-функцией Римана через гамма-функцию;
- Два доказательства функционального уравнения дзета-функции Римана;
- Определение функции распределения простых чисел Римана J(x) с помощью функции распределения простых чисел и функции Мёбиуса;
- Явную формулу количества простых чисел меньше заданного числа с использованием функции распределения простых чисел Римана, определённой с помощью нетривиальных нулей дзета-функции Римана.
Дзета-функция Римана
Мы видели тесную связь между простыми числами и дзета-функцией, показанную Эйлером в его произведении. Однако за исключением этой связи об их взаимоотношениях было мало что известно, и чтобы показать их, потребовалось изобретение комплексных чисел.
Риман первым рассмотрел дзета-функцию ζ(s) для комплексной переменной s, где s = σ + it.
Дзета-функция Римана для n, где s = σ + it — это комплексное число, в котором σ и t являются вещественными числами.
Этот бесконечный ряд, названный дзетой-функцией Римана ζ(s), является аналитическим (то есть имеет определяемые значения) для всех комплексных чисел с вещественной частью больше 1 (Re(s) > 1). В этой области определения он сходится абсолютно.
Чтобы проанализировать функцию в областях за пределами обычной области сходимости (когда вещественная часть комплексной переменной s больше 1), функцию нужно переопределить. Риман успешно с этим справился, выполнив аналитическое продолжение до абсолютно сходящейся функции на полуплоскости Re(s) > 0.
Переписанный вид дзета-функции Римана, где
Это новое определение дзета-функции аналитично в любой части полуплоскости Re(s) > 0, за исключением s = 1, где она является вырожденностью/простым полюсом. В этой области определения она называется мероморфной функцией, потому что она голоморфна (комплексно дифференцируема в окрестности каждой точки в области её определения), за исключением простого полюса s = 1. Кроме того, она является превосходным примером L-функции Дирихле.
В своей статье Риман на этом не остановился. Он перешёл к аналитическому продолжению своей дзета-функции ζ(s) на всю комплексную плоскость, воспользовавшись гамма-функцией Γ(z). Чтобы не усложнять пост, я не буду приводить эти вычисления, но крайне рекомендую вам посмотреть их самостоятельно, чтобы убедиться в удивительной интуиции и мастерстве Римана.
В его методе используется интегральное представление гаммы Γ(z) для комплексных переменных и тета-функции Якоби ϑ(x), которые можно переписать таким образом, чтобы появилась дзета-функция. Решая относительно дзета, получаем:
Функциональное уравнение дзеты для всей комплексной плоскости за исключением двух вырожденностей при s = 0 и s = 1
В таком виде мы замечаем, что член ψ(s) уменьшается быстрее чем любая степень x, а значит, интеграл сходится ко всем значениям s.
Зайдя ещё дальше, Риман заметил, что первый член в скобках (-1 / s(1 — s) ) является инвариантом (не меняется), если заменить s на 1 — s. Благодаря этому Риман ещё больше расширил полезность уравнения, устранив два полюса в s=0 и s=1, и задав кси-функцию Римана ξ(s) без вырожденностей:
Кси-функция Римана ξ(s)
Нули дзета-функции Римана
Корни/нули дзета-функции, когда ζ(s)=0, можно разделить на два вида, которые называются «тривиальными» и «нетривиальными» нулями дзета-функции Римана.
Существование нулей с вещественной частью Re(s) < 0
Тривиальные нули — это нули, которые легко найти и объяснить. Наиболее заметны они в следующем функциональном виде дзета-функции:
Разновидность функционального дзета-уравнения Римана
Это произведение становится равным нулю, когда нулём становится синус. Это происходит при значениях kπ. То есть при отрицательном чётном целом числе s = -2n дзета-функция становится нулём. Однако для положительных чётных целых чисел s = 2n нули сокращаются полюсами гамма-функции Γ(z). Это легче увидеть в исходном функциональном виде; если подставить s = 2n, то первая часть члена становится неопределённой.
Итак, дзета-функция Римана имеет нули в каждом отрицательном чётном целом s = -2n. Это тривиальные нули, и их можно увидеть на графике функции:
График дзета-функции Римана ζ(s) с нулями в s= -2, -4, -6 и так далее
Существование нулей с вещественной частью Re(s) > 1
Из формулировки дзеты Эйлера мы можем мгновенно увидеть что дзета ζ(s) не может быть нулём в области с вещественной частью s больше 1, потому что сходящееся бесконечное произведение может быть нулём только если равен нулю один из его множителей. Доказательство бесконечности простых чисел отрицает это.
Формула произведения Эйлера
Существование нулей с вещественной частью 0 ≤ Re(s) ≤ 1
Мы нашли тривиальные нули дзеты в отрицательной полуплоскости, когда Re(s) < 0, и показали, что в области Re(s) > 1 не может быть нулей.
Однако область между этими двумя областями, называемая критической полосой, была основным центром внимания аналитической теории чисел в течение последних сотен лет.
График вещественной и мнимой частей дзета-функции Римана ζ(s) в интервале -5 < Re < 2, 0 < Im < 60
На показанном выше графике я отобразил вещественные части дзеты ζ(s) красным, а мнимые — синим. Мы видим первые два тривиальных нуля в левом нижнем углу, где вещественная часть s равна -2 и -4. Между 0 и 1 я выделил критическую полосу и отметил пересечения вещественных и мнимых частей дзеты ζ(s). Это нетривиальные нули дзета-функции Римана. Поднимаясь к более высоким значениям, мы увидим больше нулей и две кажущиеся случайными функции, которые становятся плотнее при увеличении значений мнимой части s.
График вещественной и мнимой частей дзета-функции Римана ζ(s) в интервале -5 < Re < 2, 0 < Im < 120
Кси-функция Римана
Мы определили кси-функцию Римана ξ(s) (вид функционального уравнения, в котором устранены все вырожденности, то есть оно определено для всех значений s) так:
Кси-функция Римана без вырожденностей
Эта функция удовлетворяет соотношению
Симметричная взаимосвязь между положительными и отрицательными значениями кси-функции Римана
Это означает, что функция симметрична относительно вертикальной линии Re(s) = 1/2, то есть ξ(1) = ξ(0), ξ(2) = ξ(-1), и так далее. Эта функциональная связь (симметрия s и 1-s) в сочетании с произведением Эйлера показывают, что кси-функция Римана может иметь нули только в интервале 0 ≤ Re(s) ≤ 1. Другими словами, нули кси-функции Римана соответствуют нетривиальным нулям дзета-функции Римана. В известном отношении, критическая линия R(s) = 1/2 для дзета-функции Римана ζ(s) соответствует вещественной линии (Im(s) = 0) для кси-функции Римана ξ(s).
Посмотрев на два показанных выше графика, можно сразу заметить, что у всех нетривиальных нулей дзета-функции Римана ζ(s) (нулей кси-функции Римана) вещественная часть Re(s) равна 1/2. В своей статье Риман вкратце упомянул это свойство, и его поверхностное примечание в результате оказалось одним из величайших его наследий.
Гипотеза Римана
Это современная формулировка недоказанного предположения, сделанного Риманом в его знаменитой статье. Она гласит, что все точки, в которых дзета равна нулю (ζ(s) = 0) на критической полосе 0 ≤ Re(s) ≤ 1, имеют вещественную часть Re(s) = 1/2. Если это верно, то все нетривиальные нули дзеты будут иметь вид ζ(1/2 + it).
Эквивалентная формулировка (изложенная самим Риманом) заключается в том, что все корни кси-функции Римана ξ(s) вещественны.
На графике ниже линия Re(s) = 1/2 является горизонтальной осью. Вещественная часть Re(s) дзеты ζ(s) показана красной линией, а мнимая часть Im(s) — синей. Нетривиальные нули — это пересечения между красным и синим графиками на горизонтальной прямой.
Первые нетривиальные нули дзета-функции Римана на прямой Re(s) = 1/2.
Если гипотеза Римана окажется истинной, то все нетривиальные нули функции будут встречаться на этой прямой как пересечения двух графиков.
Причины верить в гипотезу
Существует множество причин верить истинности гипотезы Римана относительно нулей дзета-функции. Наверно, самым убедительной для математиков причиной являются последствия, которые она будет иметь для распределения простых чисел. Численная проверка гипотезы при очень высоких значениях предполагает, что она истинна. На самом деле, численное подтверждение гипотезы настолько сильно, что в других областях, например, в физике или химии, его можно было бы считать экспериментально доказанным. Однако в истории математики было несколько гипотез, проверенных до очень высоких значений, и тем не менее оказавшихся неверными. Дербишир (2004) рассказывает историю числа Скьюза — чрезвычайно большого числа, указавшего верхний предел и доказавшего таким образом ложность одной из гипотез Гаусса о том, что интегральный логарифм Li(x) всегда больше, чем функция распределения простых чисел. Она была опровергнута Литлвудом без примера, а затем было показано, что она неверна выше очень огромного числа Скьюза — десять в степени десять, в степени десять, в степени 34. Это доказало, что несмотря на доказанность ошибочности идеи Гаусса, пример точного местонахождения такого отклонения от гипотезы находится далеко за пределами даже современных вычислительных мощностей. Такое может произойти и в случае с гипотезой Римана, которая была проверена «всего лишь» до десятки в степени двенадцати нетривиальных нулей.
Дзета-функция Римана и простые числа
Взяв за основу истинность гипотезы Римана, сам Риман начал исследовать её последствия. В своей статье он писал: «…есть большая вероятность того, что все корни являются вещественными. Разумеется, здесь нужно строгое доказательство; сделав несколько безуспешных попыток, я отложу его поиск, потому что оно кажется необязательным для следующей цели моих исследований». Его следующей целью была связь нулей дзета-функции с простыми числами.
Вспомним функцию распределения простых чисел π(x), подсчитывающую количество простых чисел вплоть до вещественного числа x. Риман использовал π(x) для определения собственной функции распределения простых чисел, а именно функции распределения простых чисел Римана J(x). Она задаётся следующим образом:
Функция распределения простых чисел Римана
Первое, что можно заметить в этой функции — она не бесконечна. При каком-то члене функция распределения будет равна нулю, потому что не существует простых чисел для x < 2. То есть взяв для примера J(100), мы получим, что функция состоит из семи членов, потому что восьмой член будет содержать восьмой корень 100, который приблизительно равен 1.778279. то есть этот член распределения простых чисел становится равным нулю, а сумма становится равной J(100) = 28.5333…
Как и функция распределения простых чисел, функция Римана J(x) — это ступенчатая функция, значение которой увеличивается так:
Возможные значения функции распределения простых чисел Римана
Чтобы связать значение J(x) с количеством простых чисел до x, включая его, мы вернёмся к функции распределения простых чисел π(x) при помощи процесса, называемого обращением Мёбиуса (здесь я его показывать не буду). Полученное выражение будет иметь вид
Функция распределения простых чисел π(x) и её связь с функцией распределения простых чисел Римана и с функцией Мёбиуса μ(n)
Вспомним, что возможные значения функции Мёбиуса имеют вид
Три возможных значения функции Мёбиуса μ(n)
Это значит, что теперь мы можем записать любую функцию распределения простых чисел как функцию распределения простых чисел Римана, что даст нам
Функция распределения простых чисел, записанная как функция распределения простых чисел Римана для первых семи значений n
Это новое выражение по-прежнему является конечной суммой, потому что J(x) равна нулю при x < 2, так как не существует простых чисел меньше 2.
Если теперь мы ещё раз рассмотрим пример с J(100), то получим сумму
Функция распределения простых чисел для x = 100
Что, как мы знаем, является количеством простых чисел ниже 100.
Преобразование формулы произведения Эйлера
Затем Риман использовал в качестве начальной точки произведение Эйлера и получил метод для аналитической оценки простых чисел на неподдающемся исчислению языке матанализа. Начав с Эйлера:
Произведение Эйлера для первых пяти простых чисел
Сначала взяв с обеих сторон логарифм а затем переписав знаменатели в скобках, он вывел взаимоотношение
Логарифм переписанной формулы произведения Эйлера
Затем, воспользовавшись хорошо известным рядом Тейлора-Маклорена, он разложил каждый логарифмический член в правой части, создав бесконечную сумму бесконечных сумм, по одной для каждого члена в ряду простых чисел.
Разложение Тейлора для первых четырёх членов логарифма произведения Эйлера
Рассмотрим один из таких членов, например:
Второй член — это разложение Маклорена для 1/3^s
Этот член, как и каждый другой член вычисления, представляет часть площади под функцией J(x). В виде интеграла:
Интегральный вид второго члена разложения Маклорена для 1/3^s
Другими словами, с помощью произведения Эйлера Риман показал, что можно представить дискретную ступенчатую функцию распределения простых чисел в виде непрерывной суммы интегралов. На графике ниже взятый нами пример члена показан как часть площади под графиком функции распределения простых чисел Римана.
Функция распределения простых чисел Римана J(x) до x = 50, в котором выделены два интеграла
Итак, каждое выражение в конечной сумме, составляющей ряд величин, обратных простым числам из произведения Эйлера, может быть выражена в виде интегралов, составляющих бесконечную сумму интегралов, соответствующих площади под функцией распределения простых чисел Римана. Для простого числа 3 это бесконечное произведение интегралов имеет вид:
Бесконечное произведение интегралов, составляющих площадь под функцией распределения простых чисел, представленной целочисленной 3
Если собрать все эти бесконечные суммы вместе в один интеграл, то интеграл под функцией распределения простых чисел Римана J(x) может быть записан в простом виде:
Логарифм дзеты, выраженный в виде бесконечного ряда интегралов
Или в более известном виде
Современный эквивалент произведения Эйлера, связывающий дзета-функцию с функцией распределения простых числе Римана
Благодаря этому Риману удалось связать на языке матанализа свою дзета-функцию ζ(s) с функцией распределения простых чисел Римана J(x) в равенстве, эквивалентном формуле произведения Эйлера.
Величина погрешности
Получив этот аналитический вид произведения Эйлера, Риман приступил к формулированию собственной теоремы о распределении простых чисел. Он представил её в следующем явном виде:
«Теорема о распределении простых чисел Римана», предугадывающая количество простых чисел меньше заданной величины x
Это явная формула Римана. Она стала усовершенствованием теоремы о распределении простых чисел, более точной оценкой количества простых чисел вплоть до числа x. Формула состоит из четырёх членов:
- Первый, или «основной» член — это интегральный логарифм Li(x), который является улучшенным приближением функции распределения простых чисел π(x) из теоремы о распределении простых чисел. Это самый большой член, и как мы видели, он завышает количество простых чисел до заданного значения x.
- Второй, или «периодический» член — это сумма интегрального логарифма x в степени ρ, суммированная по ρ, что является нетривиальными нулями дзета-функции Римана. Этот член регулирует завышение значений основного члена.
- Третий член — это константа -log(2) = -0.6993147…
- Четвёртый и последний член — это интеграл, равный нулю при x < 2, потому что не существует простых чисел меньше 2. Его максимальное значение равно 2, когда его интеграл примерно равен 0.1400101….
Ступенчатая функция распределения простых чисел π(x), аппроксимируемая явной формулой функции распределения простых чисел Римана J(x) с помощью первых 35 нетривиальных нулей ρ дзета-функции Римана.
В показанном выше графике я аппроксимировал функцию распределения простых чисел π(x) с помощью явной формулы функции распределения простых чисел Римана J(x) и суммировал первые 35 нетривиальных нуля дзета-функции Римана ζ(s). Мы видим, что периодический член заставляет функцию «резонировать» и начать приближаться к форме функции распределения простых чисел π(x).
Ниже показан тот же график с использованием большего количества нетривиальных нулей.
Ступенчатая функция распределения простых чисел π(x), аппроксимируемая явной формулой распределения простых чисел Римана J(x) с помощью первых 100 нетривиальных нулей ρ дзета-функции Римана.
С помощью явной функции Римана можно с очень большой точностью аппроксимировать количество простых чисел вплоть до заданного числа x. На самом деле, в 1901 году Нильс Кох доказал, что использование нетривиальных нулей дзета-функции Римана для коррекции погрешности функции интегрального логарифма эквивалентно «наилучшей» границе для величины погрешности в теореме о распределении простых чисел.
Как проверить число на простоту?
Как быстро проверить, является ли данное натуральное число n простым? Такая задача часто возникает на практике. Один из примеров — шифр RSA 1 . Это асимметричный шифр: шифрование производится закрытым ключом (известен только отправителю), а расшифровка — открытым (известен всем). Чтобы сгенерировать такую пару ключей для шифра RSA, нужно выбрать два больших числа p и q, причем оба числа должны быть простыми — иначе шифр невозможно будет расшифровать.
Проще всего действовать по определению, перебирая все числа от 1 до n и проверяя, не является ли какое-то из них делителем. Этот способ можно немного усовершенствовать: если n = ab, то меньший из двух делителей a и b окажется меньше или равен \(\sqrt
Время работы такого алгоритма, однако, будет огромным. Например, если в двоичной записи числа n тысяча разрядов (это минимальная длина криптографического ключа RSA, гарантирующая безопасность), то число проверок равно \(\sqrt
Начнем с малой теоремы Ферма (МТФ): если n — простое число, то для любого a от 1 до n − 1 число a n − 1 при делении на n дает остаток 1 (т. е. a n − 1 ≡ 1(mod n)). Значит, если мы вдруг нашли такое a, что остаток оказался другим, то n заведомо не простое! Разумеется, перебирать все a в попытке найти нужное — затея не лучше, чем перебирать возможные делители. Но мы попробуем угадать a, выбирая его случайным образом.
Эта идея не такая безнадежная, как может показаться на первый взгляд. Действительно, пусть оказалось, что a0 n − 1 \(\not≡\) 1(mod n), а a1 n − 1 ≡ 1(mod n) (т. е. если мы выбрали a0 , то мы угадали, а если выбрали a1, то нет). Тогда (a0 ⋅ a1) n − 1 ≡ a0 n − 1 ⋅ a1 n − 1 ≡ a0 n − 1 \(\not≡\) 1(mod n) . Таким образом, если мы угадали с выбором a0, то также удачным будет выбор a0 ⋅ a1. Более того, если a0 взаимно просто с n, то для разных значений a1 числа a1 ⋅ a2 будут различны по модулю n. Таким образом, среди всех чисел от 1 до n − 1, взаимно простых с n, окажется не менее половины «удачных»: действительно, каждому «неудачному» числу a1 соответствует как минимум одно уникальное «удачное», равное остатку от деления a0 ⋅ a1 на n (где a0 — одно фиксированное «удачное» число).
Итак, алгоритм — его называют тестом Ферма — действует так. Выбираем случайное a в диапазоне от 2 до n − 1 (число 1 выбирать бессмысленно). Если a не взаимно просто с n — это можно быстро проверить с помощью алгоритма Евклида 2 , то n заведомо составное. Иначе вычисляем остаток от деления a n − 1 на n, и если он не равен 1, то n — составное. Если же равен, то вероятность того, что мы выбрали «неудачное» a, а для другого a получился бы неединичный остаток, не превосходит 1/2. Возвести a в большую степень можно методом последовательного деления показателя пополам («быстрое возведение в степень»); при этом после каждого шага лучше брать остаток по модулю n, чтобы избежать слишком больших чисел. Повторяя алгоритм k раз, каждый раз выбирая случайное a независимо, мы уменьшим эту вероятность до 1/2 k , что очень быстро стремится к нулю с ростом k.
Подведем итог. Если тест Ферма отвечает, что n составное, то он совершенно точно прав; если говорит, что простое — то может ошибиться, но с очень малой вероятностью. Эту вероятность мы контролируем за счет изменения параметра k — например, можем сделать ее меньше, чем вероятность сбоя техники. Тогда на практике алгоритм будет неотличим от точного — а работает он намного быстрее, чем перебор делителей!
К сожалению, у теста Ферма есть фатальный недостаток. Существуют так называемые числа Кармайкла: эти вредные числа не являются простыми, но удовлетворяют МТФ для любого a, взаимно простого с n. В таком случае мы не сможем найти ни одного «удачного» a0, и приведенное выше рассуждение недействительно. (Вероятность же случайно наткнуться на число a, не взаимно простое с n, мала.) Самые маленькие числа Кармайкла: 561, 1105, 1729. Числа Кармайкла относительно редки, однако, к сожалению, их бесконечно много 3 . (Иначе можно было бы «починить» тест Ферма, добавив в начале сверку с конечным списком чисел Кармайкла.)
Итак, получается алгоритм: выбираем случайное a от 2 до n − 1, взаимно простое с n (если нашлось не взаимно простое — немедленно отвечаем, что n составное); вычисляем остаток от деления \(a^<\frac
Существуют и другие вероятностные тесты на простоту. А можно ли построить алгоритм проверки на простоту, который работает быстро и при этом выдает ответ точно, а не с некоторой (пусть и сколь угодно близкой к 1) вероятностью? Такие тесты называются детерминированными. Таков тест Миллера (1976). Этот тест быстрый и детерминированный, однако доказательство того, что он работает правильно, опирается на недоказанное утверждение — расширенную гипотезу Римана. Быстрый детерминированный тест, корректность которого доказана полностью, был предложен сравнительно недавно — это тест Агравала — Каяла — Саксены или AKS-тест (2002). Однако вероятностные тесты все еще работают быстрее, чем AKS-тест.
1 Подробнее о шифре RSA читайте в статье В.А. Успенского «Как теория чисел помогает в шифровальном деле» (Соросовский образовательный журнал, 1996, №6).
2 Вагутен В. Алгоритм Евклида и основная теорема арифметики («Квант», 1972, №6); Абрамов С. Самый знаменитый алгоритм («Квант», 1985, №11).