2. Територія простого числа. Гіпотеза Ґольдбаха
Деякі великі проблеми появляються дуже рано в нашій математичної освіти, хоча ми можемо й не помітити цього. Невдовзі після вивчення множення, ми стикаємося з поняттям простого числа. Деякі числа можна отримати множенням двох менших чисел; наприклад, 6 = 2×3. Інші, скажімо 5, не можна так розкласти; найбільше, що ми можемо зробити: 5 = 1×5, що не містить двох
менших чисел. Числа, що можна розкласти, називають складеними; ті, що не можна – простими. Прості числа видаються нехитрою штукою. Як тільки зможете помножити цілі числа, то зможете зрозуміти, що таке просте число. Прості числа – основні будівельні блоки для цілих чисел, і вони трапляються по всій математиці. А також вони глибоко загадкові, і, здається, розкидані майже навмання. Поза сумнівом, прості числа – це загадка. Можливо, це наслідок їх означення – не стільки те, що вони є, як те, що вони не є. З іншого боку, вони фундаментальні для математики, тому ми не можемо, просто жахнувшись, підняти руки і здатися. Ми повинні дійти згоди з простими числами, і вивідати їх найглибші таємниці.
Кілька особливостей очевидні. За винятком найменшого простого числа, 2, всі прості числа непарні. За винятком 3, сума їх цифр не може бути кратною 3. За винятком 5, вони не можуть закінчуватися цифрою 5. Незалежно від цих правил і кількох тонших, ви не можете подивитися на якесь число і відразу ж визначити, чи воно просте. Існують формули для простих чисел, але значною мірою вони оманливі, бо не забезпечують корисної нової інформації про прості числа; це просто розумні способи кодування означення «простого числа» у формулі. Прості числа подібні до людей: вони індивідууми і не підпорядковуються стандартним правилам.
Протягом тисячоліть розуміння математиками простих чисел поступово зростало, і час від часу розв’язували ще одну велику проблему про них. Проте багато питань досі залишається без відповіді. Деякі спрощені і їх легко сформулювати; інші езотеричніші. У цьому розділі обговорюється, що ми робимо, і чого не знаємо про ці дратівливі, але фундаментальні, числа. Він починається з установлення деяких базових понять, зокрема розкладання на прості множники (факторизація) – як виразити певне число через множення простих чисел. Навіть цей знайомий процес веде до труднощів, як тільки ми починаємо питати за по-справжньому ефективні методи знаходження простих множників числа. Дивно те, що, видається, відносно легко перевірити число, чи воно просте, але якщо складене, знаходження його простих множників часто набагато складніше.
Розібравшись з основами, ми перейдемо до найвідомішої нерозв’язаної проблеми стосовно простих чисел, 250-річної Ґольдбахової гіпотези. Недавній прогрес у цьому питанні був разючий, але ще не вирішальний. Кілька інших проблем дають короткий зразок того, що ще належить дізнатися про цю багату, але непокірну галузь математики.
Прості числа та розкладання на множники знайомі зі шкільної аритметики, але більшість з цікавих особливостей простих чисел рідко вчили на цьому рівні, і практично нічого не доводили. Є вагомі підстави для цього: доводити, навіть, здавалось би, очевидні властивості, напрочуд важко. Натомість учні вивчають деякі прості методи роботи з простими числами, і наголошується на розрахунках з відносно невеликими числами. Як результат, наш ранній досвід простих чисел дещо вводить в оману.
Стародавні греки знали деякі основні властивості простих чисел, і знали, як їх довести. Прості числа та множники – основна тема сьомої книжки Евклідових «Елементів», великої геометричної класики. Ця особлива книжка містить геометричне представлення ділення і множення в аритметиці. Греки вважали за краще працювати з довжинами ліній, аніж з числами як такими, але ці результати легко переформулювати мовою чисел. Евклід дбає про те, щоб доводити твердження, які можуть здатися очевидними: наприклад, теорема 16 книжки VII доводить, що, коли два числа перемножуються, результат не залежить від порядку, в якому вони взяті. Тобто АВ = ВА – основний закон алгебри.
У шкільній аритметиці прості множники використовуються, щоб знайти найбільший спільний дільник (або найбільший спільний множник) двох чисел. Наприклад, щоб знайти найбільший спільний дільник 135 і 630, ми розкладаємо їх на прості множники:
135 = 3
3 × 5
630 = 2 × 3
2 × 5 × 7
Тоді кожне просте число беремо з найбільшим показником степеня, спільним для обох розкладів на множники, отримуючи 3
2 × 5. Помноживши, отримуємо 45 – це найбільший спільний дільник. Ця процедура створює враження, що розклад на прості множники необхідний, щоб знайти найбільший спільний дільник. Власне, логічний зв'язок іде іншим шляхом. Теорема 2 книжки VII «Елементів» представляє метод знаходження найбільшого спільного дільника двох цілих чисел без їх факторизації. Він працює через повторне віднімання меншого числа від більшого, а потім застосування подібного процесу до отриманої різниці і меншого числа, і продовжується доти, поки не буде різниці. Для 135 і 630, типовий приклад використання досить малих чисел, процес іде так. Відніміть 135 повторно від 630:
630 - 135 = 495
495 - 135 = 360
360 - 135 = 225
225 - 135 = 90
Через те що 90 менше, ніж 135, перейдіть до двох чисел, 90 і 135:
135 - 90 = 45
Через те що 45 менше, ніж 90, перейдіть до 45 і 90:
90 - 45 = 45
45 - 45 = 0
Тому найбільший спільний дільник 135 і 630 – 45.
Ця процедура працює, бо на кожному етапі замінює початкову пару чисел простішою парою (одне з чисел менше), що має той же найбільший спільний дільник. Зрештою одне з чисел ділить інше точно, і на цьому етапі ми зупиняємося. Сьогоднішній термін для явного методу розрахунку, який гарантовано знаходить відповідь на певну проблему – «алгоритм». Тож процедуру Евкліда тепер називають Евклідовим алгоритмом. Це логічно передує розкладові на прості множники. Дійсно, Евклід використовує свій алгоритм, щоб довести основні властивості простих множників, і цим займаються університетські курси з математики й сьогодні.
Евклідова теорема 30 вкрай важлива для всієї галузі. У сучасних термінах, у ній ідеться, що якщо якесь просте число ділить добуток двох чисел – тобто отримане множенням їх між собою – то воно мусить ділити одне з них. Теорема 32 стверджує, що число або просте, або має простий множник. Зводячи їх докупи, легко зробити висновок, що кожне число є добуток простих множників, а також, що цей вираз єдиний, якщо не враховувати порядок, в якому множники записані. Наприклад,
60 = 2 × 2 × 3 × 5 = 2 × 3 × 2 × 5 = 5 × 3 × 2 × 2
і так далі, але єдиний спосіб отримати 60 – переставити перший розклад на множники. Тут немає факторизації, наприклад, подібної до чогось на кшталт 60 = 7 x
щось. Існування факторизації випливає з теореми 32. Якщо число просте, зупиніться. Якщо ні, знайдіть простий множник, розділіть, щоб отримати менше число, і повторіть. Єдиність випливає з теореми 30. Наприклад, якби була факторизація на кшталт 60 = 7 ×
щось, то 7 мало б розділити одне з чисел 2, 3 або 5, а це не так.
Тут мені потрібно прояснити невеликий, але важливий момент: винятковий статус числа 1. Відповідно до означення, в указаній раніше формі, 1 явно просте: якщо ми спробуємо розбити його, найбільше, що ми можемо зробити, це 1 = 1 × 1, де нема менших чисел. Проте така інтерпретація згодом створює проблеми в теорії, тому за останнє століття-два, математики ввели додаткове обмеження. Число 1 таке особливе, що його слід розглядати і не як просте, і не як складене. Натомість це третій вид звіра, одиниця. Одна з підстав розглядати 1 як окремий випадок, а не як справжнє просте число, полягає в тому, що якщо ми називаємо 1 простим, то єдиність втрачається. Справді, 1×1 = 1 вже демонструє збій, а l×l×l×l×l×l×l×l = 1 втикає нас у нього носами. Ми могли б змінити єдиність, сказавши «єдиний, за винятком 1», але це просто ще один спосіб сказати, що 1 особливе.
Значно пізніше, в теоремі 20 IX книжки Евклід доводить ще один ключовий факт: "Простих чисел більше ніж будь-яка встановлена величезна кількість простих чисел". Тобто кількість простих чисел нескінченна. Це чудова теорема з розумним доведенням, але вона відкрила величезну банку з черв’яками, тобто усунення проблеми породило багато інших проблем. Якщо простих чисел нескінченно багато, то, видається, нема жодного патерну, яким ми можемо описати, як вони виглядають?
Ми маємо бути готові до цього питання, бо не можемо ігнорувати простих чисел. Вони істотні риси математичного ландшафту. Вони особливо поширені та корисні в теорії чисел. Ця галузь математики вивчає властивості цілих чисел. Можливо, звучить трохи елементарно, але насправді теорія чисел – одна з найглибших і найскладніших галузей математики. Пізніше ми побачимо багато доказів цього твердження. 1801 року Ґаус, провідний теоретик своєї доби, можливо, один з провідних математиків усіх часів, можливо, навіть найбільший з них, – написав передовий підручник з теорії чисел, «Аритметичні дослідження» («Disquisitiones Arithmeticae»). Він зазначив, що серед високорівневих проблем ми не повинні випустити з уваги два вкрай базові питання: "Проблема відрізняння простих чисел від складених і розкладання останніх на прості множники, як відомо, одна з найважливіших і найкорисніших в аритметиці».
У школі зазвичай вчать тільки одного способу знаходження простих множників числа: спробуйте всі можливі множники почергово, поки не знайдете ті, що точно підходять. Якщо ви не знайшли якогось множника до того часу, як досягнете квадратного кореня з початкового числа, точніше – найбільшого цілого числа, що менше або дорівнює цьому квадратному кореневі – то число просте. Інакше ви знаходите множник, ділите на нього, і повторюєте. Ефективніше пробувати лише прості множники, для чого потрібно мати список простих чисел. Ви зупиняєтеся на квадратному корені, бо найменший множник будь-якого складеного числа не більший за його квадратний корінь. Однак ця процедура безнадійно неефективна, коли числа стають великими. Наприклад, якщо число
1 080 813 321 843 836 712 253, то його розклад на прості множники:
13 929 010 429 × 77 594 408 257
і доведеться спробувати перші 624 401 249 простих чисел почергово, щоб знайти менший з двох множників. Звісно, з комп'ютером це зробити досить легко, але якщо почати з 100-знакового числа, що може виявитися добутком двох 50-знакових чисел, і використовувати систематичний пошук послідовних простих чисел, то Всесвіт дійде кінця раніше, ніж комп'ютер знайде відповідь.
Справді, сучасні комп'ютери зазвичай можуть розкладати на множники 100-знакові числа. Мій комп'ютер затратить менш ніж секунду, щоб знайти прості множники 10
99+ 1, що виглядає як 1000 ... 001 з 98 нулями. Це добуток 13 простих чисел (одне з них наявне двічі), з яких найменше 7, а найбільше –
141 122 524 877 886 182 282 233 539 317 796 144 938 305 111 168 717.
Але якщо я скажу комп'ютерові розкласти на множники 10
199+1, з 200 цифрами, він думатиме віками і нічого не досягне. Проте 100-знаковий розрахунок вражає. У чому секрет? В ефективніших методах, ніж пробувати всі потенційні прості множники почергово.
Тепер ми знаємо, набагато більше, ніж Ґаус про першу з його проблем (перевіряння на прості числа) і набагато менше, ніж хотілося б про другу (факторизацію). Поширена думка, що перевіряння на простоту набагато простіше, ніж факторизація. Зазвичай це викликає подив у нематематиків, які вчили в школі, що перевіряють, чи число просте, за допомогою того ж методу, який використовують для факторизації: спробуйте всі можливі дільники. Виявляється, що є швидкі способи довести, що число просте, і без цього. Вони також дають змогу нам довести, що число складене, без знаходження жодного з його множників. Просто покажіть, що воно не пройшло перевірку на простоту.
Прапрабатько всіх сучасних тестів на простоту – теорема Ферма, яку не слід плутати зі знаменитою останньою теоремою Ферма, розділ 7. Ця теорема заснована на модулярній аритметиці, яку іноді називають "годинниковою аритметикою", бо числа ідуть колом, як ті, що на циферблаті годинника. Виберіть якесь число – для 12-годинного аналогового годинника це 12 – і назвіть його модулем. У будь-якому аритметичному обчисленні з цілими числами тепер можна замінювати будь-що кратне 12 нулем. Наприклад, 5×5 = 25, але 24 – це двічі 12, тому, віднімаючи 24, ми отримаємо 5×5 = 1 за модулем 12. Модулярна аритметика дуже красива, тому що майже всі звичайні правила аритметики все ще працюють. Головна відмінність полягає в тому, що не завжди можна поділити одне число на інше, навіть якщо воно не дорівнює нулеві. Модулярна аритметика також корисна, бо вона надає чіткий спосіб розглядати питання про подільність: які числа діляться на вибраний модуль, і який залишок, коли ні? Ґаус представив модулярну аритметику в «Аритметичних дослідженнях», і сьогодні її широко використовують в інформатиці, фізиці й техніці, а також математиці.
Теорема Ферма стверджує, що якщо ми вибираємо якийсь простий модуль р, і беремо будь-яке число а, що не кратне р, то (р - 1)-й степінь a дорівнює 1 в аритметиці за модулем р. Припустимо, наприклад, що р = 17 і а = 3. Тоді теорема передбачає, що, коли ми розділимо 3
16 на 17, остача – 1. Як перевірка,
3
16 = 43 046 721 = 2 532 160 × 17 + 1.
Ніхто при здоровому глузді не хотів би так займатися розв’язанням аритметичних задач зі, скажімо, 100-знаковими простими числами. На щастя, є швидкий спосіб виконувати такий розрахунок. Річ у тому, що якщо відповідь не дорівнює 1, то модуль, з якого ми почали, складений. Так теорема Ферма створює основу ефективного тесту, що забезпечує необхідну умову для того, щоб число було просте.
На жаль, тест не достатній. Багато складених чисел, відомих як числа Кармайкла, проходять тест. Найменше – 561, а 2003 року Ред Алфорд, Ендрю Ґренвіл, і Карл Померанс виявили, всім на диво, що їх нескінченно багато. Здивування було тому, що вони знайшли доведення; фактичний результат був меншою несподіванкою. Насправді вони показали, що існує принаймні x
2/7 чисел Кармайкла, менших або рівних х, якщо х досить велике.
Проте складніші варіанти теореми Ферма можна перетворити на справжні тести на простоту, такий як опублікував 1976 року Ґері Мілер. На жаль, доведення справедливості тесту Мілера залежить від нерозв’язаної великої проблеми, узагальненої гіпотези Рімана, розділ 9. У 1980 році Майкл Рабін перетворив Мілерів тест у ймовірнісний, тест, який може іноді давати неправильну відповідь. Винятки, якщо вони існують, дуже рідкісні, але їх не можна виключити цілком. Найефективніший детерміністичний (тобто гарантовно правильний) тест на сьогодні – тест Адлемена – Померанса – Румлі, названий на честь Ленарда Адлемена, Померанса і Роберта Румлі. У ньому використано ідеї з теорії чисел, складніші, ніж теорема Ферма, але в тому ж дусі.
Я досі ясно пам'ятаю лист від одного багатонадійного аматора, який запропонував варіант спробного ділення. Спробувати всі можливі дільники, але почати з квадратного кореня і рухатися в сторону
зменшення. За цим методом іноді знаходять відповідь швидше, ніж коли робити звичайним порядком, але якщо числа стають більші, то він стикається з такими ж труднощами, що і звичайний метод. Якщо спробувати його на моєму вищевказаному прикладі, 22-знаковому числі 1 080 813 321 843 836 712 253, то квадратний корінь – це приблизно 32 875 725 419. Ви повинні спробувати 794 582 971 простий дільник, перш ніж знайдете той, який підходить. Це
гірше, ніж при пошуку у звичайному напрямку.
1956 року знаменитий логік Курт Ґедель, у листі до Джона фон Ноймана, повторив заклик Ґауса. Він запитав, чи можна вдосконалити спробне ділення, і якщо так, то якою мірою. Фон Нойман не зайнявся цим питанням, але протягом багатьох років інші відповідали Ґеделеві, відкривши практичні методи знаходження простих чисел до 100-знакових, іноді й більших. Ці методи, з яких найвідоміший так зване квадратичне решето, були відомі приблизно з 1980 року. Однак майже всі з них або ймовірнісні, або неефективні в такому сенсі.
Як зростає час виконання комп'ютерного алгоритму зі збільшенням розміру входових даних? Щодо перевірки на простоту, розмір входових даних не відповідне число, а скільки цифр воно має. Основна відмінність у таких питаннях полягає між двома класами алгоритмів, які називаються P і не-P. Якщо час роботи зростає як деякий фіксований степінь розміру входових даних, то алгоритм класу P; інакше це не-P. Грубо кажучи, алгоритми класу P корисні, тоді як алгоритми не-P непрактичні, але між ними є ділянка нічийної землі, де в гру вступають інші міркування. Тут P означає «поліномний час», чудернацький спосіб говорити про степені, а ми повернемося до теми ефективних алгоритмів у розділі 11.
За стандартом класу P спробне ділення виконується дуже погано. Це цілком задовільно в авдиторії, де числа, які трапляються, складаються з двох чи трьох цифр, але зовсім безнадійно для 100-знакового числа. Спробне ділення твердо в класі не-P. Справді, час роботи становить приблизно 10
n/2 для n-знакового числа, що зростає швидше, ніж будь-який фіксований степінь n. Такий тип зростання, який називають експоненційним,
справді поганий, обчислювальна країна-хмарних-зозуль.
До 1980-х років усі відомі алгоритми перевірки на простоту, за винятком імовірнісних або тих, чия справедливість не була доведена, мали експоненційну швидкість зростання. Однак 1983 року знайдено алгоритм, що дратівливо міститься в нічийній зоні, що прилягає до P-території: вищезгаданий тест Адлемена – Померанса – Румлі. Поліпшена версія Анрі Коена (Henri Cohen) і Гендріка Ленстри (Hendrik Lenstra) має час роботи n, піднесений до степеня log log n, де log означає логаритм. Технічно, log log n може бути яким завгодно великим, тому цей алгоритм не належить до класу Р. Але це не заважає йому бути практичним: якщо n – гуголплекс, тобто 1 із 10
100 нулями, тоді log log n приблизно 230. Як ідеться в старому анекдоті: «Доведено, що log log n прямує до нескінченності, але ніколи не помічали, щоб це сталося».
Перший тест на простоту в класі Р відкрили 2002 року Маніндра Аґравал (Manindra Agrawal) та його учні Нірадж Каял (Neeraj Kayal) і Нітін Саксена (Nitin Saxena), які в той час були студентами. Я подав деякі деталі в примітці[10]. Вони довели, що час роботи їхнього алгоритму пропорційний щонайбільше n
12; що невдовзі покращили до n
7,5. Однак, хоча їхній алгоритм належить до класу P, а отже класифікується як "ефективний", його переваги не проявляються, поки число n не стане справді дуже великим. Він має обійти тест Аделмена – Померанса – Румлі, коли кількість
цифр у n приблизно l0
1000. Немає місця для такого великого числа в пам'яті комп'ютера, чи, власне, у відомому Всесвіті. Однак тепер, коли ми
знаємо, що алгоритм класу P для тесту на простоту існує, варто шукати кращі. Ленстра і Померанс знизили степінь від 7,5 до 6. Якщо різні інші припущення щодо простих чисел істинні, то степінь можна зменшити до 3, що вже видається практичним.
Однак найзахопливіший аспект алгоритму Аґравала – Каяла – Саксени не результат, а метод. Він простий – для математиків, в усякому разі – і новий. Основна ідея – варіант теореми Ферма, але замість роботи з числами, команда Аґравала використовувала поліном. Це комбінація степенів змінної х, наприклад 5x
3 + 4x - 1. Ви можете додавати, віднімати і множити поліноми, і звичайні алгебричні закони залишаються чинними. Розділ 3 пояснює поліноми докладніше.
Це справді чудова ідея: розширити сферу дискурсу і перенести проблему в нову царину мислення. Це одна з тих ідей, таких простих, що потрібно бути генієм, щоб їх помітити. Вона розроблена на основі статті Аґравала і його наукового керівника Сомената Бісваса 1999 року, що дає ймовірнісний тест на простоту на основі аналога теореми Ферма у світі поліномів. Аґравал був переконаний, що ймовірнісний елемент можна видалити. 2001 року його учні зробили вирішальне, швидше технічне, спостереження. Пошуки привели команду в глибокі числотеоретичні води, але зрештою все звелося до однієї перешкоди, існування простого числа р, такого що р - 1 має досить великий простий дільник. Трохи розпитування і пошуку в інтернеті привело до теореми, що довів 1985 року Етьєн Фуврі (Etienne Fouvry), використовуючи глибокі та технічні методи. Це було саме те, що їм було потрібно, щоб довести, що їхній алгоритм запрацював, і останній шматочок пазла став акуратно на місце.
У дні, коли теорія чисел була надійно захована всередині своєї маленької вежі зі слонової кістки, все це не мало б значення для решти світу. Але за останні 20 років прості числа стали важливими в криптографії, науці про секретні коди. Коди важливі не тільки для військового використання; комерційні компанії теж мають свої секрети. В епоху інтернету нас усіх це стосується: ми не хочемо, щоб злочинці діставали доступ до наших банківських рахунків, номерів кредитних карток чи, зі зростанням кількості крадіжок особистих даних, імені нашого кота. Але інтернет – такий зручний спосіб оплачувати рахунки, страхувати автомобіль, а також резервувати квитки, що ми повинні прийняти певний ризик того, що наша конфіденційна, особиста інформація може потрапити в чужі руки.
Виробники комп'ютерів і постачальники інтернет-послуг намагаються зменшити цей ризик, надаючи доступ до різних систем шифрування. Залучення комп'ютерів змінило як криптографію, так і криптоаналіз, темне мистецтво ламання кодів. Розроблено багато нових кодів і один з найвідоміших, що винайшли Рон Рівест (Ron Rivest), Аді Шамір (Adi Shamir) і Ленард Адлемен у 1978 році, використовує прості числа. Великі, приблизно стоцифрові. Система Рівеста – Шаміра – Адлемена використовувана в багатьох комп’ютерних операційних системах, вбудована в основні протоколи безпечного спілкування в інтернеті, а також широко використовувана урядами, корпораціями та університетами. Це не означає, що кожен новий результат щодо простих чисел істотний для безпеки вашого онлайнового банківського рахунку, але він додає певного трепету з приводу будь-якого відкриття, що пов’язує прості числа з обчисленням. Тест Аґравала – Каяли – Саксени – саме той випадок. Математично він елегантний і важливий, але не має безпосереднього практичного значення.
Це, однак, висвітлює загальне питання криптографії Рівеста – Шаміра – Адлемена по-новому і дещо тривожно. Досі нема жодного алгоритму класу P, щоб розв’язувати другу проблему Ґауса, факторизацію. Більшість експертів вважає, що нічого подібного не існує, але вони не такі впевнені, як раніше. А що нові відкриття, такі як тест Аґравала – Каяли – Саксени, можуть лишатися непоміченими, чекаючи свого часу, то основані на таких простих ідеях, як поліномні варіанти теореми Ферма, криптосистеми, засновані на розкладанні на прості множники, можуть бути не такими безпечними, як ми наївно уявляємо. Не повідомляйте поки що ім'я свого кота в інтернеті.
Навіть базова математика простих чисел швидко приводить до просунутіших понять. Таємниця стає ще глибшою, коли ми ставимо тонші питання. Евклід довів, що простих чисел нескінченна кількість, тому ми не можемо просто перерахувати їх і зупинитися. Ми не можемо дати якусь просту, помічну алгебричну формулу для послідовних простих чисел, так як x2 задає квадрати. (Щодо цього існують прості формули, але вони «обманюють», вбудовуючи прості числа у формулу замасковано, і не говорять нам нічого нового[11].) Щоб зрозуміти природу цих невловних, непередбачних чисел, ми можемо проводити експерименти, шукати натяки на схему, і намагатися довести, що ці позірні патерни зберігаються незалежно від того, якими великими стають прості числа. Наприклад, ми можемо запитати, як прості числа розподілені серед усіх цілих чисел. Таблиці простих чисел переконливо засвідчують, що вони мають тенденцію рідшати, в міру того як більшають. Таблиця 1 показує, скільки простих чисел є в різних діапазонах 1000 послідовних чисел.
Числа в другому стовпчику переважно зменшуються в міру просування вниз рядками, хоча іноді бувають короткі періоди, коли відбувається навпаки: наприклад, за 114 іде 117. Це ознака нерегулярності простих чисел, але, попри це, є чітка загальна тенденція: прості числа рідшають зі збільшенням їх величини. Причину далеко шукати не треба: що більше число, то більше потенційних множників. Прості числа повинні уникати всіх цих множників. Це як ловити непрості числа сіткою: що дрібніша сітка, то менше простих чисел просмикнеться.
діапазон кількість простих чисел
1–1000 168
1001–2000 135
2001–3000 127
3001–4000 119
4001–5000 118
5001–6000 114
6001–7000 117
7001–8000 106
8001–9000 110
9001–10000 111
Таблиця 1. Кількість простих чисел у послідовних інтервалах 1000 чисел.
"Сітка" навіть має свою назву: решето Ератосфена. Ератосфен з Кирени був давньогрецький математик, який жив близько 250 р. до н.е. Він також був спортсмен і захоплювався поезією, географією, астрономією та музикою. Він перший обґрунтовано оцінив розмір Землі, спостерігаючи за положенням Сонця опівдні у двох різних місцях, Александрії та Сієні — сучасному Асуані. Опівдні Сонце було прямо над головою в Сієні, але приблизно на 7 градусів від вертикалі в Александрії. А що цей кут дорівнює одній п'ятдесятій частині кола, обвід Землі мусить в 50 разів перевищувати відстань від Александрії до Сієни. Ератосфен не міг безпосередньо виміряти цю відстань, тому він запитав торговців, скільки часу знадобилося, щоб відбути подорож на верблюді, і оцінив, яку відстань верблюд зазвичай проходить за день. Він дав явну цифру в одиниці, відомій як
стадій, але ми не знаємо, яка була довжина цієї одиниці. Історики зазвичай вважають, що Ератосфенова оцінка була досить точна.
Його решето — це алгоритм пошуку всіх простих чисел шляхом послідовного видалення всіх кратних чисел, що вже відомі як прості. Рисунок 2 ілюструє метод для чисел до 102, організований так, щоб полегшити процес вилучання. Щоб побачити, що відбувається, я пропоную вам побудувати діаграму для себе. Почніть прямо з цієї ґратки, поки що без ліній, які перекреслюють числа. Потім ви можете додавати ці лінії одну за іншою. Пропустіть 1, бо це одиниця. Наступне число 2, тож, це просте число. Викресліть усі числа, кратні 2: вони лежать на горизонтальних лініях, починаючи з 4, 6 і 8. Наступне не викреслене число — 3, тож, це просте число. Викресліть усі кратні 3: вони лежать на горизонтальних лініях, починаючи з 6, уже закресленій, і 9. Наступне не викреслене число — 5, тож, це просте число. Закресліть усі числа, кратні 5: вони лежать на діагональних лініях, нахилених вгору та праворуч, починаючи з 10. Наступне не викреслене число — 7, тож, це просте число. Закресліть усі числа, кратні 7: вони лежать на діагональних лініях, нахилених вниз і вправо, починаючи з 14. Наступне не викреслене число — 11, тож, це просте число. Перше кратне 11, яке ще не було викреслене, через те що воно має менший дільник, дорівнює 121, яке міститься поза зображенням, тому зупиніться. Решта затінених чисел прості.
Рис. 2. Решето Ератосфена.
Решето Ератосфена – це не просто історична цікавинка; це все ще один із найефективніших відомих методів для створення великих списків простих чисел. А подібні методи привели до значного прогресу в тому, що становить, певно, найвідомішу нерозв’язану велику проблему простих чисел: гіпотезу Ґольдбаха. Німецький математик-любитель Християн Ґольдбах листувався з багатьма відомими діячами свого часу. У 1742 році він висловив низку цікавих припущень щодо простих чисел у листі до Леонарда Ойлера. Пізніше історики помітили, що за кілька років до того Рене Декарт сказав приблизно те саме. Першим із тверджень Ґольдбаха було: «Кожне ціле число, яке можна записати у вигляді суми двох простих чисел, також можна записати у вигляді суми будь-якої кількості простих чисел, доки всі доданки не стануть одиницями». Друге, додане на берегах його листа, було: «Кожне ціле число, більше за 2, можна записати у вигляді суми трьох простих чисел». Із сьогоднішнім означенням «простого числа» є очевидні винятки з цих тверджень. Наприклад, 4 не сума трьох простих чисел, бо найменше просте число дорівнює 2, тому сума трьох простих чисел має бути принаймні 6. Але за часів Ґольдбаха число 1 вважали простим числом. Можна легко перефразувати його здогадки, використовуючи сучасну домовленість.
У своїй відповіді Ойлер згадав попереднє спілкування з Ґольдбахом, коли той зазначив, що його перша гіпотеза випливає з простішої, його третьої гіпотези: «Кожне парне ціле число – сума двох простих чисел». З панівною домовленістю про те, що 1 – просте число, ця гіпотеза також передбачає другу гіпотезу, бо будь-яке число можна записати або як n + 1, або n + 2, де n парне. Якщо n – сума двох простих чисел, початкове число – сума трьох простих чисел. Думка Ойлера щодо третьої гіпотези була однозначна: «Я вважаю це цілком певною теоремою, хоча не можу її довести». Це майже підсумовує її сьогоднішній статус.
Сучасна домовленість, коли 1 не просте число, розділяє гіпотези Ґольдбаха на дві різні. Парна гіпотеза Ґольдбаха стверджує:
Кожне парне ціле число, більше за 2, – сума двох простих чисел.
Непарна гіпотеза Ґольдбаха така:
Кожне непарне ціле число, більше за 5, – сума трьох простих чисел.
Парна гіпотеза імплікує непарну, але не навпаки[12]. Корисно розглядати обидві гіпотези окремо, бо ми все ще не знаємо, чи будь-яка з них істинна. Непарна гіпотеза здається трохи легшою, ніж парна, у тому сенсі, що досягнуто більшого прогресу.
Деякі швидкі розрахунки підтверджують парну гіпотезу Ґольдбаха для
4= 2+2
6=3+3
8=5+3
10=7+3=5+5
12=7+5
14=11+3=7+7
16=13+3=11+5
18=13+5=11+7
20=17+3=13+7
Легко продовжити вручну, скажімо, до 1000 або близько того – більше, якщо ви наполегливі. Наприклад, 1000 = 3 + 997, а 1 000 000 = 17 + 999 993. У 1938 році Нільс Піпінг (Nils Pipping) перевірив парну гіпотезу Ґольдбаха для всіх парних чисел до 100 000.
Також стало очевидно, що в міру того, як відповідне число більшає, з’являється все більше способів записати його як суму простих чисел. Це розумно. Якщо взяти велике парне число та продовжувати віднімати прості числа по черзі, на скільки висока ймовірність, що
всі результати будуть складені? Потрібно трапитися лише одному простому числу серед отриманого списку різниць, і гіпотеза перевіряється для заданого числа. Використовуючи статистичні властивості простих чисел, ми можемо оцінити ймовірність такого результату. Аналітики Ґодфрі Гаролд Гарді та Джон Літлвуд виконали такий розрахунок у 1923 році та вивели правдоподібну, але нестрогу формулу для кількості різних способів вираження заданого парного числа n як суми двох простих чисел: приблизно n/[2(log n)
2]. Це число зростає, у міру того як n більшає, і воно також узгоджується з числовими доказами. Але навіть якби цей розрахунок можна було б зробити строгим, можуть траплятися випадкові рідкісні винятки, тому він не дуже допомагає.
Основна перешкода для доведення гіпотези Ґольдбаха – те, що вона поєднує в собі дві дуже різні властивості. Прості числа означуються в термінах множення, а припущення стосуються додавання. Тому надзвичайно важко пов’язати бажаний висновок з будь-якими резонними властивостями простих чисел. Важіль начебто нікуди вставити. Це мусило бути музикою для вух видавництва «Фейбер & Фейбер» у 2000 році, коли воно запропонувало мільйондоларовий приз за доведення гіпотези, щоб рекламувати роман «Дядько Петрос і Ґольдбахова гіпотеза» Апостолоса Доксіадіса. Реченець був стислий: розв’язок потрібно було надіслати до квітня 2002 року. Ніхто не претендував на премію, що й не дивно, враховуючи, що проблема залишалася нерозв’язаною понад 250 років.
Гіпотезу Ґольдбаха часто переформульовують як питання про додавання множин цілих чисел. Парна гіпотеза Ґольдбаха – найпростіший приклад для цього конкретного способу мислення, тому що ми додаємо разом лише дві множини цілих чисел. Для цього візьміть будь-яке число з першої множини, додайте будь-яке число з другої множини, а потім візьміть множину всіх таких сум. Наприклад, сума {1, 2, 3} і {4, 5} містить 1 + 4, 2 + 4, 3 + 4, 1 + 5, 2 + 5, 3 + 5, що є {5, 6 , 7, 8}. Деякі числа трапляються більше ніж один раз, наприклад, 6 = 2 + 4 = 1 + 5. Я називатиму такий тип повторення «перекривом» (overlap).
Тепер можна переформулювати парну гіпотезу Ґольдбаха: якщо ми додамо множину простих чисел до самої себе, результат міститиме кожне парне число, більше за 2. Це переформулювання може здатися трохи банальним – так і є – але воно переміщує проблему у сферу, де є деякі потужні загальні теореми. Число 2 трохи заважає, але ми можемо його легко позбутися. Це єдине парне просте число, і якщо ми додамо його до будь-якого іншого простого числа, результат буде непарний. Отже, що стосується парної гіпотези Ґольдбаха, ми можемо забути про 2. Однак нам потрібно 2 + 2, щоб представити 4, тому ми також мусимо обмежити увагу парними числами від щонайменше 6.
Як простий експеримент розглянемо парні числа до 30 включно. У цьому діапазоні дев’ять непарних простих чисел: {3, 5, 7, 11, 13, 17, 19, 23, 29}. Додавши їх, ви отримаєте рисунок 3: я позначив грубим шрифтом суми, які менші або дорівнюють 30 (діапазон парних чисел, який охоплюють усі прості числа до 29). З’являються дві прості моделі. Вся таблиця симетрична відносно своєї головної діагоналі, бо a + b = b + a. Числа, виділені грубим шрифтом, займають приблизно верхню ліву половину таблиці, над товстою (діагональною) лінією. У всякому разі, вони мають тенденцію виступати за її межі посередині. Це відбувається тому, що загалом великі прості числа трапляються рідше, ніж маленькі. Додаткова область випину більш ніж компенсує два 32 у верхньому правому та нижньому лівому кутах.
Тепер ми приблизно оцінимо. Я міг би бути точнішим, але й так досить добре. Кількість гнізд у таблиці дорівнює 9×9 = 81. Близько половини чисел у цих гніздах містяться у верхньому лівому трикутнику. Через симетрію вони постають парами, за винятком тих, що вздовж діагоналі, тому кількість непов’язаних гнізд становить десь 81/4, приблизно 20. Кількість парних цілих чисел у діапазоні від 6 до 30 – 13. Отже, 20 (і більше) сум, виділених грубим шрифтом, мають вулучити лише в 13 парних чисел. Існує більше потенційних сум двох простих чисел у цьому підхожому діапазоні, ніж парних чисел. Це як кинути 20 м’ячів у 13 кокосів на ярмарку. У вас є обґрунтовані шанси вразити багато з них. Попри це, ви можете промахнутися в кілька кокосів. Деяких парних чисел усе ще може бракувати.
Рис. 3. Суми пар простих чисел до 30. Грубий шрифт: суми, що дорівнюють 30 або менше. Товста лінія: діагональ. Затінена область: усунення симетрично пов’язаних пар. Затінена область займає трохи більше від однієї чверті квадрата.
У цьому випадку ні, але такий рахувальний аргумент не може виключити цю можливість. Однак це говорить нам про те, що мусить бути чимале перекриття, коли одне й те саме число, виділене грубим шрифтом, трапляється кілька разів у відповідній чверті таблиці. Чому? Тому що 20 сум мають увійти в множину лише з 13 членами. Отже, у середньому кожне число, виділене грубим шрифтом, з’являється приблизно 1,5 раза. (Фактична кількість сум рівна 27, тому краща оцінка вказує, що кожне число, виділене грубим шрифтом, з’являється двічі.) Якщо якихось парних чисел бракує, перекривання мусить бути ще більшим.
Ми можемо грати в ту саму гру з більшою верхньою межею – скажімо, 1 мільйон. Формула, яка називається теоремою про прості числа, розділ 9, забезпечує просту оцінку кількості простих чисел до будь-якої заданої величини x. Формула: x/log x. Тут оцінка – приблизно 72 380. (Точна цифра — 78 497.) Відповідна затінена область займає приблизно одну чверть таблиці, тому в ній подано близько n
2/4 = 250 мільярдів чисел, виділених грубим шрифтом: суми двох простих чисел у цьому діапазоні. Це значно більше, ніж кількість парних чисел у діапазоні, який становить пів мільйона. Тепер обсяг перекриття має бути гігантським, коли кожна сума повторюється в середньому 500 000 разів. Тому ймовірність того, що якесь конкретне парне число випаде, значно зменшується.
Доклавши більших зусиль, ми можемо перетворити цей підхід на оцінення ймовірності того, що деяке парне число в заданому діапазоні не сума двох простих чисел, припускаючи, що прості числа розподілені випадково і з частотностями, заданими теоремою про прості числа, тобто приблизно x/logx простих чисел менше від будь-якого заданого x. Це те, що Гарді та Літлвуд зробили. Вони знали, що їхній підхід не строгий, бо прості числа означуються певним процесом і насправді вони не випадкові. Проте розумно очікувати, що фактичні результати будуть відповідати цій імовірнісній моделі, бо означувальна властивість простих чисел, здається, має дуже незначний зв’язок з тим, що відбувається, коли ми два з них додаємо.
Кілька стандартних методів у цій галузі переймають подібний погляд, але приділяючи особливу увагу тому, щоб аргументація була строга. Приклади – методи решета, які базуються на решеті Ератосфена. Загальні теореми про щільність чисел у сумах двох множин – пропорція чисел, які трапляються, коли множини стають дуже великими – забезпечують інші корисні інструменти.
Коли математична гіпотеза зрештою виявляється правильною, її історія часто йде за стандартною схемою. Протягом певного періоду часу різні люди доводять істинність припущень за умови застосування спеціальних обмежень. Кожен такий результат покращує попередній шляхом послаблення деяких обмежень, але з часом цей процес вичерпується. Нарешті, нова і набагато дотепніша ідея завершує це доведення.
Наприклад, гіпотеза в теорії чисел може стверджувати, що кожне додатне ціле число можна представити якимось чином, використовуючи, скажімо, шість спеціальних чисел (простих чисел, квадратів, кубів тощо). Тут ключові риси – кожне додатне ціле число та шість спеціальних чисел. Початкові досягнення приводять до набагато слабших результатів, але послідовні етапи процесу повільно покращують їх.
Першим етапом часто стає доведення в такому ключі: кожне натуральне число, яке не ділиться на 3 або 11, за винятком якоїсь кінцевої їх кількості, можна представити членами деякої гігантської кількості спеціальних чисел – скажімо, 10
666. Теорема зазвичай не вказує, скільки є винятків, тому результат не можна застосувати безпосередньо до будь-якого конкретного цілого числа. Наступний етап полягає в тому, щоб зробити межу ефективною: тобто довести, що кожне ціле число, більше за , можна так представити. Потім обмеження на подільність на 3 виключається, а далі через подібне просування – на 11. Після цього послідовні автори зменшують одне з чисел 10
666 або 10 у степені 10
42, часто обидва. Типовим удосконаленням може бути те, що кожне ціле число, яке перевищує 5,8 × 10
17, можна представити, використовуючи не більше ніж 4298 спеціальних чисел, наприклад.
Тим часом інші дослідники працюють, починаючи з невеликих чисел, часто за допомогою комп’ютера, доводячи, що, скажімо, кожне число, менше чи рівне 1012, можна представити, використовуючи щонайбільше шість спеціальних чисел. Протягом року 1012 за п’ять етапів різні дослідники або групи покращили до 11,0337 × 10
29. Ці покращення ані рутинні, ані легкі, але спосіб їх досягнення передбачає складні спеціальні методи, які не забезпечують жодного натяку на загальніший підхід, і кожен подальший внесок складніший і довший. Після кількох років такого поступового вдосконалення із застосуванням тих самих загальних ідей, але з потужнішими комп’ютерами та новими підправленнями, це число зросло до 10
43. Але тепер цей метод зупинився, і всі погоджуються, що хоч би скільки було підправлень, це ніколи не приведе до повної гіпотези.
У цей момент гіпотеза зникає з поля зору, тому що над нею більше ніхто не працює. Іноді прогрес практично зупиняється. Іноді проходить двадцять років без нічого нового … і тоді, позірно нізвідки, Чізбурґер і Фрайз оголошують, що, переформулювавши гіпотезу в термінах комплексних метаергодичних квазікуп і застосувавши візантійську теорію квіслінгів, вони отримали повне доведення. Після кількох років суперечок про тонкощі логіки та заповнення кількох прогалин математична спільнота визнає, що доведення правильне, і негайно запитує, чи є кращий спосіб досягти того самого результату, чи просувати його далі.
У дальших розділах ви багато разів побачите, як цей патерн спрацьовує. А що такі виклади стають стомливими, незалежно від того, як Баґінз і Крум пишаються своїм останнім покращенням експоненти в гіпотезі Джекила – Гайда з 1,773 до 1,771 + ε для будь-якого додатного ε, я опишу кілька репрезентативних внесків і пропущу решту. Це не означає заперечувати важливість роботи Баґінза та Крума. Можливо, вона навіть проклала шлях до великого прориву Чізбурґера – Фрайза. Але лише експерти, які стежать за розвитком історії, ймовірно, затамувавши дух, чекатимуть наступного незначного покращення.
Надаоі я надаватиму менше деталей, але подивімося, як це відбувається для Ґольдбаха.
Були доведені теореми, які певною мірою підтверджують гіпотезу Ґольдбаха. Перший великий прорив стався в 1923 році, коли Гарді та Літлвуд використали свої аналітичні методи, щоб довести непарну гіпотезу Ґольдбаха для всіх досить великих непарних чисел. Однак їхнє доведення спиралося на іншу велику гіпотезу, узагальнену гіпотезу Рімана, яку ми обговорюємо в розділі 9. Ця проблема все ще відкрита, тому їхній підхід мав значну прогалину. У 1930 році Лев Шнірельман усунув прогалину, використовуючи вигадливу версію своїх міркувань, засновану на методі сита. Він довів, що ненульову частину всіх чисел можна представити у вигляді суми двох простих чисел. Поєднавши цей результат із деякими загальними положеннями про додавання послідовностей, він довів, що існує деяке число C таке, що кожне ціле число, більше за 1, – сума не більше ніж C простих чисел. Це число стало відоме як Шнірельманова константа. Іван Матвєєвіч Віноґрадов отримав аналогічні результати в 1937 році, але його метод також не вказував, яке велике «досить велике». У 1939 році К. Бороздін довів, що воно не перевищує 3
14 348 907. До 2002 року Лю Мін-Чіт і Ван Тянь-Цзе зменшили цю «верхню межу» до e
3100, що становить приблизно 2 × 10
1346. Це набагато менше, але воно все ще завелике для перевірки проміжних чисел комп’ютером.
У 1969 році Н. І. Клімов отримав першу конкретну оцінку Шнірельманової константи: вона не перевищує 6 мільярдів. Інші математики значно зменшили це число, і до 1982 року Ганс Рісель (Hans Riesel) і Роберт Вон (Robert Vaughan) знизили його до 19. Хоча 19 набагато краще, ніж 6 мільярдів, докази вказували на те, що Шнірельманова константа не більш як 3. У 1995 році Лешек Канєцкі (Leszek Kaniecki) зменшив верхню межу до 6, з п’ятьма простими числами для будь-якого непарного числа, але він мав припускати істинність гіпотези Рімана. Його результати в поєднанні з числовим перевірянням Й. Ріхштайном гіпотези Рімана до 4 × 10
14 доведуть, що Шнірельманова константа не перевищує 4, знову ж припускаючи гіпотезу Рімана. У 1997 році Жан-Марк Дешуєр (Jean-Marc Deshouillers), Ґоув Ефінґер (Gove Effinger), Герман те Ріле (Herman te Riele) та Дмітрій Зінов’єв показали, що узагальнена гіпотеза Рімана (розділ 9) припускає непарну гіпотезу Ґольдбаха. Тобто кожне непарне число, крім 1, 3 і 5, – сума трьох простих чисел.
А що гіпотеза Рімана наразі не доведена, то варто спробувати позбутися цього припущення. У 1995 році французький математик Олів'є Рамаре́ зменшив верхню оцінку для представлення непарних чисел до 7, не використовуючи гіпотези Рімана. Насправді він довів дещо сильніше: кожне парне число – сума щонайбільше шести простих чисел. (Щоб мати справу з непарними числами, відніміть 3: результат парний, отже, це сума шести або менше простих чисел. Початкове число — ця сума плюс просте 3, що вимагає семи або менше простих чисел.) Головним проривом було покращення наявних оцінок частки чисел у певному діапазоні, які становлять суму двох простих чисел. Ключовий результат Рамаре полягає в тому, що для будь-якого числа n, більшого за e
67 (приблизно 1,25 × 10
29), принаймні одна п’ята чисел між n і 2n – сума двох простих чисел. Використовуючи методи сита в поєднанні з теоремою Ганса-Гайнріха Остмана (Hans-Heinrich Ostmann) про суми послідовностей, уточненою Дешуєром, це приводить до доведення того, що кожне парне число, більше за 10
30, – сума щонайбільше шести простих чисел.
Позостала перешкода – прогалина між 4 × 10
14, де Йорґ Ріхштайн перевірив теорему комп’ютером, і 10
30. Як зазвичай, ці числа завеликі для прямого комп’ютерного пошуку, тому Рамаре довів серію спеціальних теорем про кількість простих чисел у малих інтервалах. Ці теореми залежать від істинності гіпотези Рімана до певних меж, які можна перевірити комп’ютером. Тож доведення складається переважно з концептуальних висновків олівцем і папером за допомогою комп’ютера в цьому конкретному аспекті. Рамаре завершив свою статтю, зазначивши, що «в принципі» подібний підхід міг би зменшити кількість простих чисел із 7 до 5. Однак існували величезні практичні перешкоди, і він написав, що такого доведення «неможливо досягти на сучасних комп’ютерах».
У 2012 році Теренс Тао подолав ці труднощі за допомогою нових і зовсім інакших ідей. Він опублікував статтю в інтернеті, яка, коли я пишу, розглядається для публікації. Його головна теорема: кожне непарне число – сума щонайбільше п’яти простих чисел. Це зменшує Шнірельманову константу до 6. Тао відомий своєю здатністю розв’язувати складні задачі в багатьох галузях математики. Його доведення використовує кілька потужних методів для розв’язання проблеми та потребує комп’ютерної допомоги. Якби число 5 у теоремі Тао можна було зменшити до 3, непарна гіпотеза Ґольдбаха була б доведена, а межа Шнірельманової константи зменшена до 4. Тао припускає, що це можна зробити, хоча знадобляться додаткові нові ідеї.
Парна гіпотеза Ґольдбаха здається навіть складнішою. У 1998 році Дешуєр, Сауте (Saouter) і те Ріле перевірили її для всіх парних чисел до 10
14. До 2007 року Томас Олівейра і Сілва покращив це до 10
18, і його обчислення продовжуються. Ми знаємо, що кожне парне ціле число – сума щонайбільше шести простих чисел – це довів Рамаре в 1995 році. 1973 року Чен Цзін-Рун довів, що кожне достатньо велике парне ціле число – сума простого та напівпростого числа (або простого числа, або добутку двох простих чисел). Близько, але не дотягує. Тао заявив, що гіпотеза Ґольдбаха поза межами його методів. Додавання трьох простих чисел створює набагато більше перекривів в отриманих числах – у сенсі, обговорюваному у зв’язку з рисунком 3 – ніж два прості числа, необхідні для парної гіпотези Ґольдбаха, і методи Тао та Рамаре неодноразово використовують цю особливість.
Тож за кілька років ми можемо мати повне доведення непарної гіпотези Ґольдбаха, яка, зокрема, означає, що кожне парне число – сума щонайбільше чотирьох простих чисел. Але парна гіпотеза Ґольдбаха, ймовірно, буде така ж важка, як і для Ойлера та Ґольдбаха.
За 2300 років, відколи Евклід довів кілька основних теорем про прості числа, ми дізналися набагато більше про ці невловні, але життєво важливі числа. Але те, що ми тепер знаємо, дає чітке бачення довгого списку того, чого ми не знаємо.
Ми знаємо, наприклад, що існує нескінченна кількість простих чисел виду 4k + 1 і 4k + 3; загальніше, будь-яка аритметична послідовність[13] ak + b для фіксованих a і b містить нескінченну кількість простих чисел за умови, що a і b не мають спільного множника. Наприклад, припустимо, що a = 18. Тоді b = 1, 5, 7, 11, 13 або 17. Тому існує нескінченна кількість простих чисел кожної з форм 18k + 1, 18k + 5, 18k + 7, 18k + 11, 18k + 13 або 18k + 17. Це не правильно, скажімо, для 18k + 6, бо це кратне 6. Жодна аритметична послідовність не може містити
лише прості числа, але нещодавній великий прорив, теорема Ґріна – Тао, показує, що множина простих чисел містить довільно довгі аритметичні послідовності. Доведення, яке отримали у 2004 році Бен Ґрін і Тао, глибоке і складне. Це дає нам надію: на важкі відкриті питання, хоч би якими непроникними вони здавалися, іноді можна знайти відповіді.
Надівши капелюха алгебриста, ми відразу замислюємося про складніші формули, що містять k. Немає простих чисел форми k
2 і жодного, крім 3, для форми k
2 −1, бо ці вирази розкладаються на множники. Однак вираз k
2 + 1 не має очевидних множників, і тут можна знайти багато простих чисел:
2 = 1
2 + 1 5 = 2
2 + 1 17 = 4
2 + 1 37 = 6
2 + 1
і так далі. Довший приклад не має особливого значення
18 672 907 718 657 =(4 321 216)2 + 1.
Є припущення, що існує нескінченна кількість таких простих чисел, але жодне таке твердження ще не було доведене для будь-якого конкретного полінома, у якому є більший степінь, ніж перший. Дуже правдоподібна гіпотеза, що її висловив В. Буняковський у 1857 році: будь-який поліном від k, який не має очевидних дільників, представляє нескінченну кількість простих чисел. Винятки тут охоплюють не лише звідні поліноми, але й такі, як k
2 + k + 2, що завжди ділиться на 2, попри брак алгебричних множників.
Здається, деякі поліноми мають особливі властивості. Класичний випадок – це k
2 + k + 41 – просте число для k = 0, 1, 2, …, 40, а також для k = −1, −2,..., −40. Довгі серії простих чисел для послідовних значень k трапляються рідко, і про них дещо відомо. Але вся ця сфера дуже загадкова.
Майже така ж відома, як гіпотеза Ґольдбаха, і, мабуть, така ж складна, гіпотеза про прості числа-близнюки: існує нескінченна кількість пар простих чисел, які відрізняються на 2. Приклади:
3, 5 5, 7 11, 13 17, 19
Найдовші відомі прості пари-близнюки (на січень 2012):
3 756 801 695 685 × 2
666 669 +- 1,
які мають 200 700 десяткових цифр[14]. Вони були знайдені в рамках проєкту розподілених обчислень PrimeGrid у 2011 році. У 1915 році Віґо Брун використав варіант решета Ератосфена, щоб довести, що сума обернених величин усіх простих чисел-близнюків збігається, на відміну від суми обернених величин усіх простих чисел. Тож у цьому сенсі прості числа-близнюки відносно рідкісні. Він також довів, використовуючи схожі методи, що існує нескінченна кількість цілих чисел n таких, що n і n + 2 мають не більше ніж дев’ять простих множників. Гарді та Літлвуд використовували свої евристичні методи, щоб стверджувати, що кількість пар простих чисел-близнюків, менша за x, має бути асимптотичною до
2а n/(log n)
2,
де a — константа, значення якої становить приблизно 0,660161. Ідея, яка лежить в основі, полягає в тому, що для цієї мети можна припустити, що прості числа постають випадково, зі швидкістю, яка робить кількість простих чисел до x приблизно рівною x/logx. Є багато подібних припущень і евристичних формул, але, знову ж таки, немає строгих доведень.
Дійсно, існують сотні відкритих питань щодо простих чисел. Деякі з них просто цікаві, деякі глибокі та значні. З деякими з останніх ми познайомимося в розділі 9. Попри всі успіхи математиків за останні два з половиною тисячоліття, скромні прості числа не втратили ні привабливості, ні загадковості.
[10] Алгоритм Аґравала – Каяла – Саксени виглядає так:
Вхід: ціле число n.
1. Якщо n – точний степінь будь-якого меншого числа, вивести СКЛАДЕНЕ і зупинити.
2. Знайдіть найменше r таке, що найменший степінь r, який дорівнює 1 за модулем n, буде принаймні (log n)2.
3. Якщо якесь число, менше чи рівне r, має спільний множник з n, вивести СКЛАДЕНЕ і зупинити.
4. Якщо n менше чи дорівнює r, вивести ПРОСТЕ і зупинити.
5. Для всіх цілих чисел у діапазоні від 1 до заданої межі перевірити, чи поліном (х+а)n такий же, як хn +а, за модулем n і модулем хr-1. Якщо в будь-якому разі виконується рівність, вивести СКЛАДЕНЕ і зупинити.
6. Вивести ПРОСТЕ.
[11] Приклад того, що я маю на увазі, – формула [А в степені n
3], де дужки означають найбільше ціле число, менше або рівне їхньому вмістові [тому, що всередині]. 1947 року В. Г. Мілз (W. H.Mills) довів, що існує дійсна константа А така, що ця формула – просте число для всіх n. Припускаючи справедливість Ріманової гіпотези, найменше значення А, що спрацьовує, приблизно 1,306. Однак константа означена з використанням відповідної послідовності простих чисел, і формула лише символічний спосіб, щоб відтворити цю послідовність. Про більше формул, зокрема таких, що представляють усі прості числа, дивіться:
http://mathworld.wolfram.com/PrimeFormulas.html,
http://en.wikipedia.org/wiki/Formula_for_primes.
[12] Якщо n непарне, то n - 3 парне, а якщо n більше за 5, то n - 3 більше за 2. Відповідно до першої гіпотези, n - 3 = p + q, отже, n = p + q + 3.
[13] Я віддаю перевагу цьому термінові, а не застарілому, але, можливо, звичнішому, «аритметична прогресія». Більше ніхто не говорить про прогресії, крім аритметичних і геометричних. Час рухатися далі.
[14] Станом на серпень 2022 року найбільша відома пара простих близнюків – 2 996 863 034 895 × 21290000 ± 1, з 388 342 десятковими цифрами, знайдена 2016 року. –
Прим. перекл.
.
. [статей, може бути, але від слова "стать"]
. Може, вдасться подолати кострубатість до кінця перекладу 
