- Перевод
Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 - 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.
У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители - это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.
Числа называются дружественными, если сумма собственных делителей одного числа равна другому, и наоборот – например, 220 и 284. Можно сказать, что совершенное число является дружественным для самого себя.
Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.
Также он показал, что если число 2 n -1 является простым, то число 2 n-1 * (2 n -1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.
В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».
А затем случился большой перерыв в истории исследования простых чисел, связанный со Средними веками.
Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.
Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.
Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2 n -2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2 341 - 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.
Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.
Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2 n +1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 2 32 + 1 = 4294967297 делится на 641, и следовательно, не является простым.
Числа вида 2 n - 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.
Но не все числа вида 2 n - 1, где n – простое, являются простыми. К примеру, 2 11 - 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.
Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M 19 , было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M 31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M 127 - простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.
В 1952 была доказана простота чисел M 521 , M 607 , M 1279 , M 2203 и M 2281 .
К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M 25964951 , состоит из 7816230 цифр.
Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 2 32 +1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.
Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд ∑ (1/n), но и ряд вида
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
Получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.
На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как
π(n) = n/(log(n) - 1.08366)
А Гаусс – как логарифмический интеграл
π(n) = ∫ 1/log(t) dt
С промежутком интегрирования от 2 до n.
Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.
В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:
- гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
- гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
- бесконечно ли количество простых чисел вида n 2 + 1 ?
- всегда ли можно найти простое число между n 2 and (n + 1) 2 ? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
- бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
- существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26 .
- бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
- n 2 - n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n 2 - 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
- бесконечно ли количество простых чисел вида n# + 1? (n# - результат перемножения всех простых чисел, меньших n)
- бесконечно ли количество простых чисел вида n# -1 ?
- бесконечно ли количество простых чисел вида n! + 1?
- бесконечно ли количество простых чисел вида n! – 1?
- если p – простое, всегда ли 2 p -1 не содержит среди множителей квадратов простых чисел
- содержит ли последовательность Фибоначчи бесконечное количество простых чисел?
Самые большие близнецы среди простых чисел – это 2003663613 × 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.
Самое большое факториальное простое число (вида n! ± 1) – это 147855! - 1. Оно состоит из 142891 цифр и было найдено в 2002.
Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Yandex.RTB R-A-339285-1
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Определение 1
Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .
Определение 2
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Определение 3
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Определение 4
Составное число – это натуральное число, имеющее более двух положительных делителей.
Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а, то есть оно будет делиться само на себя и на 1 . Дадим определение целых чисел.
Определение 5
Натуральные числа, которые не являются простыми, называют составными.
Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.
Рассмотрим теорему, которая объясняет последнее утверждение.
Теорема 1
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Доказательство 1
Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.
Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 < b 1 < b было выполнено.
Из условия видно, что а делится на b , b делится на b 1 , значит, понятие делимости выражается таким образом: a = b · q и b = b 1 · q 1 , откуда a = b 1 · (q 1 · q) , где q и q 1 являются целыми числами. По правилу умножения целых чисел имеем, что произведение целых чисел – целое число с равенством вида a = b 1 · (q 1 · q) . Видно, что b 1 – это делитель для числа а. Неравенство 1 < b 1 < b не соответствует, потому как получим, что b является наименьшим положительным и отличным от 1 делителем а.
Теорема 2
Простых чисел бесконечно много.
Доказательство 2
Предположительно возьмем конечное количество натуральных чисел n и обозначим как p 1 , p 2 , … , p n . Рассмотрим вариант нахождения простого числа, отличного от указанных.
Примем на рассмотрение число р, которое равняется p 1 , p 2 , … , p n + 1 . Оно не равняется каждому из чисел, соответствующих простым числам вида p 1 , p 2 , … , p n . Число р является простым. Тогда считается, что теорема доказана. Если оно составное, тогда нужно принять обозначение p n + 1 и показать несовпадение делителя ни с одним из p 1 , p 2 , … , p n .
Если это было бы не так, тогда, исходя из свойства делимости произведения p 1 , p 2 , … , p n , получим, что оно делилось бы на p n + 1 . Заметим, что на выражение p n + 1 делится число р равняется сумме p 1 , p 2 , … , p n + 1 . Получим, что на выражение p n + 1 должно делиться второе слагаемое этой суммы, которое равняется 1 , но это невозможно.
Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.
Так как простых чисел очень много, то таблицы ограничивают числами 100 , 1000 , 10000 и так далее.
При составлении таблицы простых чисел следует учитывать то, что для такой задачи необходима последовательная проверка чисел, начиная с 2 до 100 . При отсутствии делителя оно фиксируется в таблицу, если оно составное, то в таблицу не заносится.
Рассмотрим пошагово.
Если начать с числа 2 , то оно имеет только 2 делителя: 2 и 1, значит, его можно занести в таблицу. Также и с числом 3 . Число 4 является составным, следует разложить его еще на 2 и 2 . Число 5 является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа 100 .
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа 2 , 3 , 4 , … , 50 .
Теперь необходимо зачеркнуть все числа, которые кратны 2 . Произвести последовательное зачеркивание. Получим таблицу вида:
Переходим к вычеркиванию чисел, кратных 5 . Получим:
Вычеркиваем числа, кратные 7 , 11 . В конечном итоге таблица получает вид
Перейдем к формулировке теоремы.
Теорема 3
Наименьший положительный и отличный от 1 делитель основного числа а не превосходит a , где a является арифметическим корнем заданного числа.
Доказательство 3
Необходимо обозначить b наименьший делитель составного числа а. Существует такое целое число q , где a = b · q , причем имеем, что b ≤ q . Недопустимо неравенство вида b > q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .
Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа, которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .
Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n . В примере, где n = 50 , у нас имеется, что n = 50 . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50 . Поиск чисел производится при помощи вычеркивания.
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Пример 1
Доказать что число 898989898989898989 является составным.
Решение
Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.
Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.
Пример 2
Определить составное или простое число 11723 .
Решение
Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .
Отсюда видим, что 11723 < 200 , то 200 2 = 40 000 , а 11 723 < 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Для более точной оценки числа 11723 необходимо записать выражение 108 2 = 11 664 , а 109 2 = 11 881 , то 108 2 < 11 723 < 109 2 . Отсюда следует, что 11723 < 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
При разложении получим, что 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 – это все простые числа. Весь данный процесс можно изобразить как деление столбиком. То есть разделить 11723 на 19 . Число 19 является одним из его множителей, так как получим деление без остатка. Изобразим деление столбиком:
Отсюда следует, что 11723 является составным числом, потому как кроме себя и 1 имеет делитель 19 .
Ответ: 11723 является составным числом.
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
Простые числа представляют собой одно из самых интересных математических явлений, которое привлекает к себе внимание ученых и простых граждан на протяжении уже более двух тысячелетий. Несмотря на то, что сейчас мы живем в век компьютеров и самых современных информационных программ, многие загадки простых чисел не решены до сих пор, есть даже такие, к которым ученые не знают, как подступиться.
Простые числа - это, как известно еще из курса элементарной арифметики, те которые делятся без остатка только на единицу и самое себя. Кстати, если натуральное число делится, кроме выше перечисленных, еще на какое-либо число, то оно именуется составным. Одна из самых знаменитых теорем гласит, что любое составное число может быть представлено в виде единственно возможного произведения простых чисел.
Несколько любопытных фактов. Во-первых, единица является уникальной в том плане, что, по сути, не принадлежит ни к простым, ни к составным числам. В то же время в научной среде все же принято относить ее именно к первой группе, так как формально она полностью удовлетворяет ее требованиям.
Во-вторых, единственным четным числом, затесавшимся в группу «простые числа» является, естественно, двойка. Любое другое четное число сюда попасть попросту не может, так как уже по определению, кроме себя и единицы, делится еще и на два.
Простые числа, список которых, как было указано выше, можно начинать с единицы, представляют собой бесконечный ряд, такой же бесконечный, как и ряд натуральных чисел. Опираясь на основную теорему арифметики, можно прийти к выводу, что простые числа никогда не прерываются и никогда не заканчиваются, так как в противном случае неизбежно прервался бы и ряд натуральных чисел.
Простые числа не появляются в натуральном ряду беспорядочно, как это может показаться на первый взгляд. Внимательно проанализировав их, можно сразу заметить несколько особенностей, наиболее любопытные из которых связаны с так называемыми числами-«близнецами». Называют их так потому, что каким-то непостижимым образом они оказались по соседству друг с другом, разделенные только четным разграничителем (пять и семь, семнадцать и девятнадцать).
Если внимательно к ним присмотреться, то можно заметить, что сумма этих чисел всегда кратна трем. Более того, при делении на тройку левого собрата в остатке всегда остается двойка, а правого - единица. Кроме того, само распределение этих чисел по натуральному ряду можно спрогнозировать, если представить весь этот ряд в виде колебательных синусоид, основные точки которых образуются при делении чисел на три и два.
Простые числа являются не только объектом пристального рассмотрения со стороны математиков всего мира, но уже давно и успешно используются в составлении различных рядов чисел, что является основой, в том числе, для шифрографии. При этом следует признать, что огромное количество загадок, связанных с этими замечательными элементами, все еще ждут своих разгадок, многие вопросы имеют не только философское, но и практичное значение.
Простое число — это натуральное (целое положительное) число , которое делится без остатка только на два натуральных числа: на и на само себя. Иными словами, простое число имеет ровно два натуральных делителя: и само число .
В силу определения, множество всех делителей простого числа является двухэлементным, т.е. представляет собой множество .
Множество всех простых чисел обозначают символом . Таким образом, в силу определения множества простых чисел, мы можем записать: .
Последовательность простых чисел выглядит так:
Основная теорема арифметики
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа являются элементарными «строительными блоками» множества натуральных чисел.
Разложение натурального числа title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют каноническим :
где — простое число, и . Например, каноническое разложение натурального числа выглядит так: .
Представление натурального числа в виде произведения простых также называют факторизацией числа .
Свойства простых чисел
Решето Эратосфена
Одним из наиболее известных алгоритмов поиска и распознавания простых чисел является решето Эратосфена . Так этот алгоритм был назван в честь греческого математика Эратосфена Киренского, которого считают автором алгоритма.
Для нахождения всех простых чисел, меньших заданного числа , следуя методу Эратосфена, нужно выполнить следующие шаги:
Шаг 1.
Выписать подряд все натуральные числа от двух до , т.е. .
Шаг 2.
Присвоить переменной значение , то есть значение равное наименьшему простому числу.
Шаг 3.
Вычеркнуть в списке все числа от до кратные , то есть числа: .
Шаг 4.
Найти первое незачёркнутое число в списке, большее , и присвоить переменной значение этого числа.
Шаг 5.
Повторить шаги 3 и 4 до достижения числа .
Процесс применения алгоритма будет выглядеть следующим образом:
Все оставшиеся незачёркнутые числа в списке по завершении процесса применения алгоритма будут представлять собой множество простых чисел от до .
Гипотеза Гольдбаха
Обложка книги «Дядюшка Петрос и гипотеза Гольдбаха»
Несмотря на то, что простые числа изучаются математиками достаточно давно, на сегодняшний день остаются нерешёнными многие связанные с ними проблемы. Одной из наиболее известных нерешённых проблем является гипотеза Гольдбаха , которая формулируется следующим образом:
- Верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел (бинарная гипотеза Гольдбаха)?
- Верно ли, что каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел (тернарная гипотеза Гольдбаха)?
Следует сказать, что тернарная гипотеза Гольдбаха является частным случаем бинарной гипотезы Гольдбаха, или, как говорят математики, тернарная гипотеза Гольдбаха является более слабой, чем бинарная гипотеза Гольдбаха.
Гипотеза Гольдбаха получила широкую известность за пределами математического сообщества в 2000-м году благодаря рекламному маркетинговому трюку издательских компаний Bloomsbury USA (США) и Faber and Faber (Великобритания). Указанные издательства, выпустив книгу «Uncle Petros and Goldbach’s Conjecture» («Дядюшка Петрос и гипотеза Гольдбаха»), пообещали выплатить в течение 2-х лет с момента издания книги приз 1 миллион долларов США тому, кто докажет гипотезу Гольдбаха. Иногда упомянутый приз от издательств путают с премиями за решение «Задач тысячелетия» (Millennium Prize Problems). Не стоит заблужаться, гипотеза Гольдбаха не отнесена «Институтом Клэя» к «задачам тысячелетия», хотя и является при этом тесно связанной с гипотезой Римана — одной из «задач тысячелетия».
Книга «Простые числа. Долгая дорога к бесконечности»
Обложка книги «Мир математики. Простые числа. Долгая дорога к бесконечности»
Дополнительно рекомендую прочесть увлекательную научно-популярную книгу , в аннотации к которой сказано: «Поиск простых чисел - одна из самых парадоксальных проблем математики. Ученые пытались решить ее на протяжении нескольких тысячелетий, но, обрастая новыми версиями и гипотезами, эта загадка по-прежнему остается неразгаданной. Появление простых чисел не подчинено какой-либо системе: они возникают в ряду натуральных чисел самопроизвольно, игнорируя все попытки математиков выявить закономерности в их последовательности. Эта книга позволит читателю проследить эволюцию научных представлений с древнейших времен до наших дней и познакомит с самыми любопытными теориями поиска простых чисел».
Дополнительно процитирую начало второй главы этой книги: «Простые числа представляют из себя одну из важных тем, которые возвращают нас к самым истокам математики, а затем по пути возрастающей сложности приводят на передний край современной науки. Таким образом, было бы очень полезно проследить увлекательную и сложную историю теории простых чисел: как именно она развивалась, как именно были собраны факты и истины, которые в настоящее время считаются общепринятыми. В этой главе мы увидим, как целые поколения математиков тщательно изучали натуральные числа в поисках правила, предсказывающего появление простых чисел, - правила, которое в процессе поиска становилось все более и более ускользающим. Мы также подробно рассмотрим исторический контекст: в каких условиях математики работали и в какой степени в их работе применялись мистические и полурелигиозные практики, которые совсем не похожи на научные методы, используемые в наше время. Тем не менее медленно и с трудом, но была подготовлена почва для новых воззрений, вдохновлявших Ферма и Эйлера в XVII и XVIII в.в.»
Как было сделано это наблюдение, красочно рассказывает М. Гарднер в «Математических досугах» (М., «Мир», 1972). Вот этот кусочек (с. 413417):
В зависимости от расположения целых чисел простые числа могут образовывать тот или иной узор. Однажды математику Станиславу М. Уламу пришлось присутствовать на одном очень длинном и очень скучном, по его словам, докладе. Чтобы как-то развлечься, он начертил на листке бумаги вертикальные и горизонтальные линии и хотел было заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1 и двигаясь по спирали против часовой стрелки. Без всякой задней мысли он обводил все простые числа кружками. Вскоре, к его удивлению, кружки с поразительным упорством стали выстраиваться вдоль прямых. На рис. 203 показано, как выглядела спираль со ста первыми числами (от 1 до 100). [ Это усечённая на два оборота версия вышеприведённого рисунка 1, поэтому я его не привожу. E.G.A. ] Для удобства числа вписаны в клетки, а не стоят на пересечении линий.
Вблизи центра выстраивания простых чисел вдоль прямых ещё можно было ожидать, поскольку плотность простых чисел вначале велика и все они, кроме числа 2, нечётны. Если клетки шахматной доски перенумеровать по спирали, то все нечётные числа попадут на клетки одного и того же цвета. Взяв 17 пешек (соответствующих 17 простым числам, не превосходящим числа 64) и расставив их наугад на клетки одного цвета, вы обнаружите, что пешки выстроились вдоль диагональных прямых. Однако не было оснований ожидать, что и в области больших чисел, где плотность простых чисел значительно меньше, те также будут выстраиваться вдоль прямых. Улама заинтересовало, как же будет выглядеть его спираль, если её продолжить до нескольких тысяч простых чисел.
В вычислительном отделе Лос-Аламосской лаборатории, где работал Улам, имелась магнитная лента, на которой было записано 90 млн. простых чисел. Улам вместе с Майроном Л. Стейном и Марком Б. Уэллсом составили программу для вычислительной машины MANIAC, позволившую нанести на спираль последовательные целые числа от 1 до 65 000. Получившийся при этом узор (иногда его называют «скатертью Улама») изображён на рис. 204. [ А это уже расширенная версия вышеприведённого рисунка 2, поэтому я его привожу. E.G.A. ] Обратите внимание на то, что даже у края картины простые числа продолжают послушно укладываться на прямые.
Прежде всего бросаются в глаза скопления простых чисел на диагоналях, но вполне ощутима и другая тенденция простых чисел выстраиваться вдоль вертикальных и горизонтальных линий, на которых все клетки, свободные от простых чисел, заняты нечётными числами. Простые числа, попадающие на прямые, продолженные за отрезок, который содержит последовательные числа, лежащие на каком-то витке спирали, можно считать значениями некоторых квадратичных выражений, начинающихся с члена 4x ². Например, последовательность простых чисел 5, 19, 41, 71, стоящих на одной из диагоналей на рис. 204, это значения, принимаемые квадратичным трёхчленом 4x ² + 10x + 5 при x , равном 0, 1, 2 и 3. Из рис. 204 видно, что квадратичные выражения, принимающие простые значения, бывают «бедными» (дающими мало простых чисел) и «богатыми» и что на «богатых» прямых наблюдаются целые «россыпи» простых чисел.
Начав спираль не с 1, а с какого-нибудь другого числа, мы получим другие квадратичные выражения для простых чисел, выстраивающихся вдоль прямых. Рассмотрим спираль, начинающуюся с числа 17 (рис. 205, слева). Числа вдоль главной диагонали, идущей с «северо-востока» на «юго-запад», порождаются квадратичным трёхчленом 4x ² + 2x + 17. Подставляя положительные значения x , мы получаем нижнюю половину диагонали, подставляя отрицательные значения верхнюю. Если рассмотреть всю диагональ и переставить простые числа в порядке возрастания, то окажется (и это приятный сюрприз), что все числа описываются более простой формулой x ² + x + 17. Это одна из многих «производящих» формул для простых чисел, открытых ещё в XVIII веке великим математиком Леонардом Эйлером. При x , принимающем значения от 0 до 15, она даёт только простые числа. Следовательно, продолжив диагональ до тех пор, пока она не заполнит квадрат 16×1 6, мы увидим, что вся диагональ заполнена простыми числами.
Самый знаменитый квадратичный трёхчлен Эйлера, производящий простые числа, x ² + x + 41, получится, если начать спираль с числа 41 (рис. 205, справа). Этот трёхчлен позволяет получить 40 последовательных простых чисел, заполняющих всю диагональ квадрата 40×4 0! Давно известно, что из 2398 первых значений, принимаемых этим трёхчленом, ровно половина простые. Перебрав все значения знаменитого трёхчлена, не превышающие 10 000 000, Улам, Стейн и Уэллс обнаружили, что доля простых чисел среди них составляет 0,475... . Математикам очень бы хотелось открыть формулу, позволяющую получать при каждом целом x различные простые числа, но пока такой формулы обнаружить не удалось. Может быть, её и не существует.
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| Рис. 205 . Диагонали, заполненные простыми числами, порождаемыми квадратичными трёхчленами x ² + x + 17 (слева) и x ² + x + 41 (справа). | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Спираль Улама подняла много новых вопросов, относящихся к закономерностям и случайностям в распределении простых чисел. Существуют ли прямые, на которых лежит бесконечно много простых чисел? Какова максимальная плотность распределения простых чисел вдоль прямых? Существенно ли различаются плотности распределения простых чисел в квадрантах «скатерти» Улама, если считать, что она продолжается неограниченно? Спираль Улама забава, но её следует принимать всерьёз.