Книга
← К списку книгЗагрузка разделов…
активнаАктивные записи участвуют в каталоге и синках. Неактивная книга скрыта, но не удалена из базы.
Книга
ЧТО МЫ ЗНАЕМИ ЧЕГО НЕ ЗНАЕМО ПРОСТЫХ ЧИСЛАХ
ЧТО МЫ ЗНАЕМИ ЧЕГО НЕ ЗНАЕМО ПРОСТЫХ ЧИСЛАХ
WACLAW S1ERPINSK1
CO WIEMY,A CZEGO NIE WIEMYО LICZBACH PIERWSZYCH
Перевод с польского
К Г. МЕЛЬНИКОВА
磅》Ж理^
WARSZAWA
PANSTUOWE ZAKLADY WYDAWNICTW SZKOLNYCH
ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВОФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА . 1963 . ЛЕНИНГРАД
517 ・ 1
С 33
АННОТАЦИЯ
В книге выдающегос}! польского математика Вацлава Серпинского собраны наиболее важные, интересные и доступные широкому кругу читателей результаты, относящиеся к теорий простых чисел. Приводятся многочисленные указания на нерешенные проблемы.
Доказательства теорем даются лишь в тех случаях, когда они элементарны п не очень уто- М1ггелы!ы. В основном книга имеет информационный характер. Она может быть использована учащимися старших классов средней школы, имеющими склонность к математике, студентами и учителями. Последние найдут в этой книге большой материал для занятий математического кружка.
ВАЦЛАВ СЕРПИНСКИЙ
(К восьмадесяталетию со дня рождение)
14 марта 1962 г. исполнилось 80 лет со дня рождения выдающегося польского математика Вацлава Сер- пинского.
Интерес к математике и незаурядные способности обнаружились у Серпинского еще в школьные годы. В 1900 г. он поступил в Варшавский университет на физико-математический факультет, где в то время работал один из крупнейших Представителей петербургской шкоды теории чисел Г, Ф. Вороной.
Свою первую научную работу Серпинский посййтил теоретико-числовой проблеме, которую сформулировал Вороной в качестве темы для конкурсных студе>(ческих сочинений. В 1904 г. Серпинский представил сочинение «О суммировании ряда 2 T (九)/(也) при условии, что с(м) представляет число разложении л на сумму квадратов двух целых чисел». В том же году Варшавский университет на основании отзыва Вороного присудил Серцинскому за эту работу золотую медаль и присвоил ученую степень кандидата математических наук. С этого времени теория чисел становится излюбленным предметам занятий Серпинского. Число его арифметических работ быстро растет.
В 1905 г. Серпинский после забастовки учащейся молодежи, в которой он принимал участие, переезжает в Краков и поступает в Ягеллонский университет. Здесь ему была присвоена степень доктора..
В 1907 г. Серпинский получил свой первый результат по теории множеств. С этого момента начинается его исключительно плодотворная деятельность в области
3 В Серпинский 7
теории множеств и ее приложении к топологии, теории функций действительного переменного и другим областям математики. Серпинский быстро приобретает известность. В 1908 г. он начал преподавать во Львовском университете и вскоре получил там профессуру. В 1911 г. Краковская Академия наук награждает Сер- пинского за работы, опубликованные им в 1909一 1910 гг. на польском языке. Спустя два года эта же академия присуждает ему премию за «Очерк теории множеств», а в 1918 г. 一 за монографию «Теория чисел*. °
Во время первой мировой войны Серпинский был интернирован. Четыре года он провел в Москве и Вятке. Здесь он продолжал свою научную деятельность и имел полезные контакты с Н. Н. Лузиным и другими русскими математиками.
Весной 1917 г. Краковская Академия наук избрала Серпинского своим членом-корреспондентом.
С 1919 г. Серпинский 一 профессор Варшавского университета. Уже в следующем году он с профессорами С. Мазуркевичем и 3. Янишевским основал в Варшаве журнал《Fundamenta Mathematicae», который сыграл большую роль в развитии современной математики. Этот журнал продолжает выходить и в настоящее время.
В 1921 г. Серпинский был избран действительным членом Польской Академии наук. Необычайная творческая активность, выдающиеся педагогические, литературные и организационные способности Серпинского ставят его во главе польской математической школы. Университеты различных стран и континентов присваивают ему звание почетного профессора, степень доктора honoris causa. Ряд академий и научных обществ избирают его своим членом-корреспондентом и почетным членом. Имя Серпинского приобр«?тает огромную популярность. В обиход математиков входят термины: «Универсальная кривая Серпинского, «Треугольная кривая Серпинского»,《Ковер Серпинского» и др.
В годы второй мировой войны Серпинский ие прекращал научную работу и даже преподавдя в подпольном университете. После освобожд^яня Польши, с февраля 1945 г. Серпинский некоторое цреМя работал в Ягеллонском университете в Кракове, а осенью 1945 г.
вернулся в Варшаву. И снова большой труд по восстановлению университета, снова, как и в предвоенные годы, лекции в различных университетах Европы, Индии, Канады, США.
В 1949 г. Серпинский был награжден в Польше первой Государственной премией за научную деятельность. В 1951 г. он был избран вице-президентом Польской Академии наук.
В апреле 1957 г. Серпинский принял участие в юбилейной научной сессии АН СССР, посвященной 250-летию со дня рождения Л. Эйлера. В том же году Cq>- пинский возобновил издание м еж дун ародно го журнала 《Acta Arithmetical, посвященного вопросам теории чисел.
Список работ, опубликованных Серпинским, содержит свыше 600 названии. Среди них около 30 университетских учебников и монографии. Серпинский — член II иностранных академий и многих иаучных обществ. Более 20 его учеников являются в настоящее время профессорами в Польше и в других странах. Недавно степень доктора получил его ученик ——молодой талантливый математик Андрей Шинцель» работы которого в области теории чисел уже приобрели широкую известность, Вацлав Серпинский ——старейший академик Полыни ——по праву считается отцом польской шкалы математиков.
И. Г Мельников
ОТ ПЕРЕВОДЧИКА
Настоящим перевод книги польского академика Вацлава Серпинского несколько отличается от орнгм* нала, появившегося летом 1961 г. на польском языке.
В последнее время наши познания о простых числах немного пополнились. В связи с этим в марте 1962 г. автор прислал мне ряд поправок и дополнений к книге. Все они учтены в настоящем издании.
Я весьма признателен редактору книги Н. М. Розен- гауз, внесшей ряд улучшений в рукопись перевода.
Л. Мельников
ПРЕДИСЛОВИЕ
Цель этой книги — сообщить в наиболее доступной форме о том, что мы знаем и чего не знаем о простых числах. С простыми числам^ мы встречаемся уже в элементарной арифметике, но они играют важную роль и в других разделах математики, главным образом в теории чисел и алгебре.
Математика считается, и справедливо, наукой дедуктивной. Тем не менее не следует умалять роль, которую сыграла в математике индукция, и притом не так называемая полная индукция, а индукция, основан* ная на наблюдении большого числа случаев и ведущая ст них к предполагаемым общим теоремам. Особенно это относится к учению о Простых числах, где именно таким путем было открыто много ваш««х теорем, доказательства которых были на说拜ны лишь позднее. Но этот путь часто приводил и к ошибочным предположениям. Известны также различные предположения, которые для многих частных случаев проверены, но о которых до сих пор неизвестно, истинны они или нет. Обо всем этом будет идти речь в данной книге.
Книга не является учебником по теории простых чисел; она имеет в основном информационный характер. В книге доказываются лишь некоторые теоремы, именно те, доказательства которых совершенно элементарны и не очень громоздки. Читателя, желающего познакомиться с доказательствами других теорем и углубить свои знания о простых числах, отсылаю ко второй части моей книги «Теория чисел»!), где указывается и дополнительная литература.
Варшава, март 1961 г. Вацлав Серги^ский
1) См W. Sierpinski, Teoria liczb, II. Waraiawa, 1959. (Прим, перев)
Что такое простые числа?
К понятию простых чисел приводят уже самые простые задачи, которые возникают в связи с таким элементарным арифметическим действием, как умножение натуральных, т. е. целых положительных чисел.
Как известно, произведение двух натуральных чисел всегда Является числом натуральным» Следовательно, существуют натуральные числа, представляющие собой произведения двух натуральных чисел, больших единицы. Но существуют также натуральные числа, бдль- шие единицы, которые не являются произведениями двух натуральных чисел, ббльших единицы, например числа 2, 3, 5 или 13. Именно такие числа мы называем простыми.
Итак, простом числом мы называем каждое нату* ральное число, большее единицы, которое не является произведением двух натуральных чисел, больших ed〃・ ницы.
Напряшиеа^тся вопрос, имеем ли мы возможность относительно каждого натурального числа л > 1 установить, простое 0Ho или нет- Оказывается, само определение простых чш;ел позволяет ответить на этот вопрос.
Действительно, если натуральное число л > 1 не является простым, то оно представляет собой произведение двух натуральных чисел q н 6〉ббльших единицы» т. е. п = цб, где а > 1 и & > 1, откуда тотчас же следует, что п> а и п> Ь* Натуральное число л > 1, не являющееся простым, есть, таким образом, произведение двух натуральных чисел, меньших п. Такое число мы называем составным. Если число п составное, то /г == &瓦 где а и & — числа натуральные > 1 и <п. Частное п:а = b является натуральным числом,
следовательно, а есть делитель натурального числа п, больший 1 и меньший чем и. Поэтому, чтобы убедиться в том, что натуральное число и > 1 является простым, достаточно убедиться, что оно не имеет натурального делителя >1 и <п. Для этого достаточно выполнить и ——2 делений числа п поочередно на числа 2, 3,..., 孔——1. Если ни на одно из них число п не делится без остатка, то в этом и только в этом случае число п является простым.
Итак, по крайней мере теоретически, мы всегда сумеем (при помощи конечного числа делений) убедиться, является ли данное натуральное число п простым или нет. На практике описанный способ может порождать значительные трудности, когда п большое число. Так, до сих пор мы не можем, ввиду длинноты необходимых вычислений, применить этот способ к числу 2101 ——1, имеющему тридцать одну цифру (в десятичной системе счисления), хотя другам путем доказано, что это число является составным. Впрочем, до сих пор неизвестно ни одного разложения этого числа в произведение двух натуральных чисел, больших еди- нкнн (хотя мы и знаем, что такое разложевие существует). Также неизвестно, является ли число 2?" + 1 (имеющее 39 457 цифр) простым или нет.
Простые делители натуральных чисел
Докажем теперь несколько несложных теорем о простых числах. ,1
Теорема /. Каждое натуральное число л >1 имеет по меньшей мере один простой делитель.
Доказательство. Пусть и — натуральное число >1- Это число имеет делители, большие единицы, например само л. Среди делителей числа 制,больших единицы, существует наименьший. Обозначим его через р* Если бы число р не было простым, то, согласно определению простых чисел, р было бы произведением двух натуральных чисел, больших единицы： д ™(Л> а, В этом случае а было бы делителем числа р, а значит, и числа л, большим единицы и притом меныпнм р, что противоречит определению числа р・ Тесьма i доказана.
Теорема 2. Каждое составное число п_ имеет по меньшей мере один простой делитель wM加
Доказательство. Если м есть составное число, то п «= а&, где а и ft — натуральные числа >1 и V& Мы можем, очевидно, предположить, что а《6. Тогда п^ ab >炉，и, следовательно, a^Vn. Но а есть число >1. Поэтому» согласно теореме 1, число а имеет простой делитель р, который, очевидно, W。и» следовательно, wU^・ Но р как делитель делителя а числа и является делителем и числа п. Таким образом, число п имеет простой делитель р^У^л. Итак, теорема 2 до* казана.
Сколько существует простых чисел?
Чтобы ответить на этот вопрос, мы докажем следующую теорему.
Теорема 3・ Если п — натуральное число >2, то между п и пГ содержится по меныией мере одно простое число.
Доказательство. Так как п > 2, то целое число ^ = п! — 1, очевидно, >1 и, согласно теореме 1, имеет простой делитель р, который ^N, а следовательно, и <nl. Если допустить, что р<п, то р будет одним из сомножителей произведения nl = 1 ^2*3 ... п и, значит, будет делителем числа nl. Но, будучи также делителем числа ^, р будет делителем разности этих чисел, или числа л!—^ = 1, что невозможно. Таким образом, р > п, а так как уже выяснено, что р < п!, то имеем п <р <nlf Их значит, теорема 3 доказана.
Итак, для каждого натуральнаго числа существует простое число, большее его. Отсюда следует, что простых чисел бесконечно много, об этом знал уже Евклид. В частности» отсюда следует, что существует простое число, имеющее (в десятичной системе счисления) по крайней мере тысячу цифр. Однако ни одного такого числа еще в I960 г. мы не знали. Наибольшее известное тогда простое число 毋幻丁 一 1 имела 969 цифр, (Подробнее об этом числе будет сказано в § 25.) 「
Стоит подчеркнуть, что в течение последнего десятилетия здесь наблюдался значительный прогресс. К началу 1951 г. наибольшим известным простым числом было число 2127—1, имеющее 39 цифр (то, что это число простое, было доказано у冰е в 1876 г.)- В настоящее же время наибольшим известным простым числом является число 24423 — 1, имеющее 1332 цифры.
В связи с теоремой 3 заметим, что в 1850 г. П. Л. Чебышев доказал более сильную теорему (так называемый постулат Бертрана), согласно которой для натуральных п > 3 между п и 2п — 2 содержится хотя бы одно Простое число. Отсюда следует, что в теореме 3 число 才 можно заменить числом 2п. В настоящее время имеется элементарное доказательство этой теоремы, но оно довольно длинное *)■ Можно также доказать, что для натуральных п > 5 между п и 2п содержатся по меньшей мере два простых числа).
Из теоремы Чебышева легко вывести, что для каждого натурального числа s существует по крайней мере три простых числа, имеющих по s цифр каждое. Действительно, каждое из чисел Ю8*1, 2 ТОТ 4 -108-1 и 8* 10е*1 имеет s цифр, а в силу теоремы Чебышева для s > 1 существуют простые числа р, q и г такие, что
Ю’т <?<2 -101-1 <^<4-101-1 <r<8-101-1,
и, следовательно, каждое из чисел р, q, г имеет по s цифр.
Для s = 1 мы имеем четыре однозначных простых числа: 2, 3, 5 и 7. Двузначных простых чисел имеется 21, трехзначных—143. Существуют хотя бы три простых числа, имеющие по сто цифр каждое. Недавно Р. М. Робинзон нашел такие числа: 81 -2824 + 1, 63 X X 2*26 + 1, 35・2827 + 1.
До сих пор мы не знаем ни одного простого числа, имеющего тысячу цифр, хотя известно, что существуют по меньшей мере три таких числа.
9 См., например, W. Sierpinski, Arytmetyka teoretyczna, Wyd. 2, Warszawa, 1§$9, str. 88—94.
Как можно найти все простые числа, меньшие данного числа?
Способ, о котором будет идти речь, известен был уже ~в древности: он носит название решета Эратосфена.
Предположим, что мы хотим найти все простые числа, не превосходящие некоторого натурального числа а. С этой целью выпишем все последовательные натуральные числа от 1 до а и будем вычеркивать из этой последовательности все числа, которые не являются простыми: прежде всего число 1, а затем для каждого натурального числа п > 1 все числа, большие чем п и делящиеся на п. Легко видеть, что таким путем каждое составное число окажется вычеркнутым и останутся только простые числа.
Итак, из последовательности 1, 2, 3, 4, ...» а мы вычеркнем число 1, затем числа, большие чем 2 и делящиеся на 2, далее числа, большие чем 3 и делящиеся на 3. Чисел, делящихся на 4, вычеркивать нам уже не придется, так как они вычеркнуты как числа >2 и делящиеся на 2. Таким образом, далее мы будем вычеркивать числа, большие чем 5 и делящиеся на 5 и т. д. При этом мь! можем уже не вычеркивать ни одно из чнсе丄 > М q. Действительно, если п ——составное число >V Q и《а, то, согласно теореме 2, число 巴 имеет простои делитель p^V п9 следовательно, <： V а, и число п окажется вычеркнутым как число, большее р и делящееся на р.
Так, например, желая получить все простые числа 《100, вычеркнем из последовательности 1, 2, 3,…，120 число 1, затем числа >2 и делящиеся на 2, далее числа >3 и делящиеся на 3, затем числа >5 и делящиеся на 5 и, наконец, числа >7 и делящиеся на 7. Все числа, оставшиеся в нашей последовательности, будут простыми. Таким путем мы получим следующую последовательность (в которой все простые числа выделены жирным шрифтом):
L 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18. 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51/52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66*
4 В. Серпинский 15
68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82t 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94» 95,维 97, 98f 99, 100.
Обозначим n-e по порядку простое число через рп. Тогда Pi = 2, "2 = 3, Рз = 5, р4 n 7, р5 n 11, Рн)= 29, Pas = 97. Легко можно подсчитать, что рюо те 541-
В 1909 г. были изданы таблицы простых чисел, меньших 10 миллионов *), в которых для каждого натурального числа《10 170 000, не делящегося на 2, 3, 5 или 7, дается его наименьший простой делитель. В 1951 г. были опубликованы таблицы простых чисел до li-го миллиона ),
Якуб Филипп Кулик (1793—1863 гг.) составил таблицы простых чисел, содержащихся в первых ста миллионах ). Эти таблицы после проверки были исполь* зоваиы при составлении таблиц простых чисел 11-го миллиона, изданных в 1951 г. Недавно (1959 г.) К Л. Бейкер и Ф. Ю. Груибергер составили микрофильм, содержащий все простые числа W₽eeo@ow = =104 395 301).
Простые числа близнецы
Относительно бесконечной последовательности последовательных простых чисел, т. е. последователь кости
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 возникает ряд вопросов. Лншь на некоторые из них удается легко дать ответ.
Так, например, два наименьших простых числа 2 и 3 являются последовательными натуральными числами. Напрашивается вопрос, существуют ли другие последовательные натуральные числа, которые оба были бы
простыми. Легко доказать, что таких чисел иет. В самом деле, из каждых двух последовательных натуральных чисел одно является четным, и, значит, если оно >2, то оио составное.
Однако существует много пар последовательных нечетных Чисел, которые оба являются простыми, например пары 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31, 41 и 43. Такие пары мы называем парами чисел близнецов. До 30 миллионов имеется 152 892 таких пар.
Уж^.對рно поставлен вопрос, существуем ли беско* нечно m^5FSF?D простнх &нс占1 блСзнецоЬ. На этот во* npoti MKt lie знаем ответа Итак, мы не знаем, представимо ли число 2 бесконечным числом способов в виде разности двух простых чисел.*
Внс&а&анд предполоисение, что каяслозетное число можиУНеско^ечн&м числом способов нреД^^йггь в 加А© £^ПосгН』в^х носЛедовагёЛьных простых чнсё1 Одна* ко мы ие можем доказать даже того, что каждое~чет- ное 而С^о “npeacrafigS^^in^KQM тще гптя бы одним способом, что проверено для многих последовательных четных чисел, например, 2 = 5 — 3, 4=11 — 7, 6 = -29 — 23, 8 = 97 — 89, 10 - 149— 139, 12 =211 — 199, 14 = 127— 113, 16= 1847— 1831, 18 = 541 — 523, 20 = =907 — 887. Ёрлее топь мы не можем доказать даже того, что каждое четное _число представляет собой разность двухлроегыхласел (хотя бы и иепоследователь-» ных).
Но мн можем найти все нечетные числа, представляющие собой разность двух простых чисел. Действительно, если натуральное нечетное число п является разностью двух простых чисел, п 0 P —仇 то одно из этих простых чисел должно быть четным, а другое не- четным, следовательно, одно из чисел р и д, и как легко видеть, именно число д, должно быть равно 2. Таким образом, имеем м = р — 2, где р ——простое нечетное число. Итак, все натуральные нечетные числа» которые являются разностью двух простых чисел» меньше простых нечетных чисел на 2, следовательно, это числа 1, 3, 5» 9* 11, »,» Такмх чисел бесконечно много.
Однако существует бес кояевдом даго и таких нё- четных aacgj^jicayopHe нё"УвМ|6¥ёя МАНб^ю двух простых/ чисел?"иапримерГ все числа вида 6^ + 1, где Л — натурадЕноечКлбГ…ВТ" самомдоле» равенство
4*——」曾
6左 + 1 = p — 2, где р — простое число, невозможно, так как из него следует, что 〃 = 6也 + 3 = 3(2也 + 1), т. е. что р есть составное число.
Гипотеза Гольдбаха
В 1742 г. Хр. Гольдбах высказал предположение, что каждое четное число >2 является суммой двух простых чисел. Это предположение до с取 пор ме доказано и не опровергнуто. Оно проверено для всех четных чисел вплоть до 100 000. Была аыскааана и более сильная гипотеза, а именно, что каждое четное число >6 является суммой даух различных простых чисел. Эту гипотезу С. Голашевскии проверил для всех чисел 《50 000.
Лкжно доказать, что последняя гипотеза равносильна утверждению, что каждое натуралкное Есло >17 является, суммой трех различных простых чисел. А. Шинцель доказал, что из гипотезы Гбльдбаха следуем что каждое нечетное число >17 является суммой трех различных, простых чисел.
Из гипотезы Гольдбаха следует также, что нечетное число >7 является суммой трех простых нечетных чисел. Действительно, если п есть натуральное число и 2п + I >7, то 2п + 1 — 3 = 2(л — 1) > 4. Согласно гипотезе Гольдбаха, четное число 2(п—1) > 4 есть сум- ■ма двух простых чисел р + ?, причем р и ^ не могут быть четными, так как наше число >4. Таким образом, числа " н g являются нечетными, и, значит, число 2п + 十 1 = 3 + " + g есть сумма трех простых нечетных чисел.
Мы не знаем, является ли каждое нечетное число >7 суммой трех простых нечетных чисел, однако для достаточно больших нечетных чисел это было доказано И. М. Виноградовым в 1937 г. Мы даже знаем такое число а (а = 33*в), что каждое нечетное число >а яв* ляется суммой трех простых нечетных чисел.
Таким образом, решению вопроса, является ли каждое нечетное число >7 суммой трех простых нечет* ных чисел, препятствует лишь громоздкость необходимых для этого вычислений, так как здесь достаточно исследовать только нечетные числа >7 и《Q, а для ка- 18
ждого данного нечетного числа можно при помощи kq・ вечного числа простых арифметических действий решить, является оно суммой трех простых нечетных чисел или нет.
Иначе обстоит дело с гипотезой Гольдбаха: здесь мы не можем сказать, что решению вопроса, верна или нет эта гипотеза, мешает только громоздкость необходимых вычислений.
Доказано, что каждое натуральноё число >1 есть сумма двадцати или менее простых чисел.
Доказано, что каждое натуральное число >11 есть сумма двух или более различных простых чисел. Например, 12 = 5 + 7, 13 2 + 11, 17 — 2 + 3 + 5 + 7, 29 = 3 + 7 + 19. А. Монковский же доказал, что каждое натуральное число >55 есть сумма различных простых чисел вида 4/г + 3, и доказал три аналогичных теоремы о суммах простых чисел каждого йз видов 4々 + 1, 6也 + 1 и 6fe + 5.
Из гипотезы Гольдбаха следует, что каждое целое нечетное число (положительное или отрицательное) может быть бесконечным числом способов представлено в виде р + ? — г, где р. ?, г— простые нечетные числа.
Действительно, для каждого целого числа Л существует простое нечетное число г такое, что 2左一1 + г > > 4 (в качестве г можно взять любое достаточно большое простое число). Но тогда 2尼一1 + г есть четное число >4 и, следовательно, согласно гипотезе Гольдбаха, 2Л — 1 + г = р + q, где р н q — простые нечетные числа. Таким образом, 2也一1 = р + q — г, причем простое число г может быть произвольно большим. Отсюда вытекает предложение, сформулированное выше.
Интересно отметить, что последнее предложение было доказано Дж. Г. ван дер Корпутом в 1923 г. Однако его доказательство весьма сложно 1)- ,
В связи с гипотезой Гольдбаха заметим, что каждое натуральное число >11 есть сумма двух составных чисел. Действительно, если п > 11 является числом четным, то п — 4" есть четное число >2, следовательно, число составное, н, значит, п есть сумма двух составных чисел: 4 и п — 4. Если же п > 11 является числом нечетным, то п — 9 есть четное число >2 и, сЛедовй-
U См. J. G. van der GorpuL Acta Mathematica, 44, 50.
тельно, составное, и, значит, п есть сумма двух составных чисел: 9 и 也一9. Отсюда, однако, нельзя сделать вывод, что исследование составных чисел легче, чем исследование простых чисел. Так, мы не можем, например, дать ответ на вопрос, существует ли средн чисел 尼=2沙+1, где п — \9 2, 3,・・・, бесконечно много составных (до сих пор мы знаем только 37 таких составных чисел, среди которых наибольшим является F^).
Г, Г. Гарди и Дж. Е. Литтлвуд высказали предположение (до сих пор не доказанное), что каждое достаточно большое натуральное число, не являющееся квадратом, есть сумма квадрата целого числа и простого числа. Легко доказать, что существует бесконечно много квадратов натуральных чисел, которые являются, а также таких, которые не являются суммой квадрата целого числа и простого числа.
Действительно» с одной стороны, если р есть про- ст^е нечетное число, то — является натуральным числом, и мы имеем
с другой же стороны, если 也=ЗА 十 2t где А — нату- ральное число, то равенство
%2 = *2 + 〃
при целом неотрицательном х и простом р невозможно, так как из него следовало бы, что п > х и
р =炉一炉=(% — х) (л + x),
откуда, принимая во внимание, что р есть простое число, п — х = 1 н п + х « р н, значит,
р~2п — 1 =3(»+1),
что при натуральном А исключено.
Другая теорема Гарди — Литтлвуда, согласно которой каждое достаточно большое натуральное число есть сумма двух квадратов целых чисел и простого числа, была доказана в Г959 г. Ю. В. Линником.
%
Гипотеза Гильбрайта
Н. Л. Гильбрайт высказал в 1958 г. следующее предположение.
Если мы выпишем последовательные простые числа, затем в первой строке — разности последовательных простых чисел, во второй ——абсолютные величины раэ- ностей последовательных чисел первой строки, в третьей ——абсолютные величины разностей последовательных чисел второй строки и т. д., то в каждой строке первым числом будет 1.
Так, например, первые 17 строк (следующих за последовательностью простых чисел) выглядят следую* щим образом:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,瑜 61
12242424626424662
1022222244222204
120000020200024
12000022220022
12000200«2020
1 20022002222
12020202000
1222222200
109060020
1 0000022
10 0^020
10 0 0 2 2
10 0 2 0
10 2 2
1 2 0
1 2
1
Fanoresa ГяльбрвЛта проверена для первых 63 418 строк. Однако мы не знаем Хщег。доказательства ее истинности.
Обозначим для натуральных п через ап наименьшее натуральное число такое, что (ап + 1)-е число п-й строки является первым числом этой строки, которое >2. Таким образом» мы имеем, например,内 =3, 如=8, Аз — 14. Подсчитано, что щ — 14, a5 n 25, а$ = 24, а7 ^ =23, &8 ™ 22, о^ = 25, а】。=59, а】4 二 97, а】5 = 174,敗2 ~ и 280, 023 ^ 740, 〃24 — 874, аз《=866, 45 = 2180, а§4 ^ 二 5940, .65 = 23 266, аэ4 ^ 31 533.
Если бы можно было доказать, что ап > 2 для натуральных п, то отсюда легко можно было бы установить истинность гипотезы Гильбрайта.
Разложение натурального числа на простые сомножители
Опираясь на теорему 1, докажем следующую тео рему.
Теорема 4・ Любое натуральное число > 1 является проазведением, каждый сомножитель которого есть простое число.
Доказательство. Пусть п — данное натуральное число >1. Согласно теореме 1, число п имеет (по крайней мере один) простой делитель р‘，и мы можем предположить, что *' есть наименьший простой делитель числа п. Итак, имеем л =± ргп\ где nf — натуральное число.
Если 九'=1, то п = pz и п является произведением, составленным только из одного простого сомножителя. Если же rf > 1, то г/ имеет простой делитель р〃，о котором мы може» предположить, что он есть наименьший простой делитель числа nz. Одновременно он является простым делителем числа 拉,причем на определения числа "' следует, что pz < pz,.
Таким образом, и7 == р"п", и либо п" = 1, и тогда и есть произведение двух простых чисел pz и "“ (не обязательно разных), либо W > 1, и тогда с числом п〃 мы можем поступить, как ранее с числами 也 н 冷'н т. д. Так как 冷—战‘ и рг > 1, то имеем 球 < п. Аналогично найдем, что n〃 f п‘ н т. д. Поэтому натуральные числа л, /г* /г",・..образуют убывающую последовательность, которая не может содержать более чем п членов. Следовательно, при некотором натуральном & число n^h>
будет последним членом этой последовательности. Но в таком случае 球衿=1, ибо в случае 球々)> 1 мы могли бы положить
孔伊)=р(*+1)д(й+0
и получили бы дальнейший член 球后+D нашей последовательности. Итак, имеем n = pzn\ п‘ = р"九〃，.... 球а-d = "(А)瓜九)и 球心=],откуда найдем
n=pW ^>Р^ ⑴
где pl р", ••・, "°)—простые числа, причем можно предполагать, что р‘ К р'У р"У ..・&"(%) (если для каждого из чисел п,也‘,...мы будем определять его наименьший простой делитель).
Среди сомножителей произведения (1) могут быть равные. Формулу (1) можно записать в виде:
拒=9：啥…右， ⑵
где s — натуральное число, q^ 仇，…，?s— различные простые числа, расположенные в порядке возрастания, @1, &，・・•， &8 — натуральные показатели степени.
Формула (2) называется каноническим разложением числа п на простые сомножители.
Итак, мы не только доказали теорему 4, но и ука- зали способ нахождения для каждого натурального числа п > 1 его канонического разложения на простые сомножители. Таким образом, нахождение этого разло- жения для любого данного натурального числа л > 1 теоретически всегда возможно. Однако на практике оно может потребовать проведения утомительных вычислений, которые для некоторых чисел оказываются столь длинными, что в настоящее время их невозможно осу- ществить даже при помощи самых лучших вычислитель' ных машин. Например, мы не знаем разложения на простые сомножители числа 2101 — 1 (имеющего 31 цифру)； доказано только, что оно является произведем нием двух различных простых сомножителей, меньший из которых (впрочем, до сих пор неизвестный) имеет не менее 11 цифр. Мы не знаем также разложения на простые сомножители числа 尸门=2步 + 1, о котором неизвестно даже, является ли оно простым или нет. Зато для числа F4945 = 23Ms + 1, имеющего более
чем 10582 цифр 5 6。21"5 = 32・2зО = 32・(2吗出 + > 30* (103)194 == 3-10583, откуда R945 > 2$ ・ ^^ 亍 =⑵о)з・ 1佃 > ]09.10M2), несколько лет назад был найден наименьший простой делитель. Этим делителем является число 5 • 21947 + 1, имеющее 587 цифр. Но мы не знаем разложения числа 尸壮参 на простые сомножители и даже не знаем других простых делителей этого числа (см. § 22).
Напрашивается вопрос, является ли разложение (2) числа п > 1 на простые сомножители единственным (если числа g】,q* …，q^ составляют возрастающую последовательность). Доказательство однозначности разложения опирается на несколько несложных теорем о простых числах.
Теорема 6 Простое число р имеет только два ма・ туральных делителя 1 и р.
Доказательство. Если бы число р, кроме делителей 1 и р, имело еще делитель а, то, очевидно, было бы 1 < а < р и р = аЬ, где b — натуральное число > 1, ибо если 6=1, то /? = 〃，что противоречит предположению относительно а. Таким образом, число р было бы произведением двух натуральных чисел, больших единицы, а это противоречит предположению о том, что р есть простое число. Итак, теорема 5 доказана.
Как легко видеть, справедлива также теорема, согласно которой натуральное число р» имеющее точно два натуральных делителя, является простым. Действительно, в этом случае должно быть р > 1. Далее, если бы р не было простым числом, то р являлось бы произведением двух натуральных чисел а к 3, больших единицы. Но из того, что р = аЬ и b > 1, следовало бы, что 1 < а <р, к е а было бы делителем числа р, отличным от 1 и р, Hf значит, число р имело бы по меньшей мере три различных натуральных делителя.
Таким образом, имеет место
Теорема 6・ Для того чтобы натуральное число было простым, необходимо и достаточно, чтобы оно имело точно два натуральных делителя (очевидно, единицу и самого себя).
Докажем теперь следующую теорему.
Теорема 7. Если 0 11b — ттуралъные числа и про* изведение ab делится на простое число р, то по крайней мере одно из чисел а и Ь делится на р.
Доказательство. Если бы теорема 7 не была справедлива, то существовало бы наименьшее простое число р, для которого она не верна. Для такого простого числа р существовало бы наименьшее произведение ab двух натуральных чисел а и 6, делящееся на р, несмотря на то, что нй один из сомножителей а и Ь не делится на р. Покажем, что тогда числа а и b были бы меньше, чем р. В самом деле, если, например, оказалось бы, что а > р, то мы имели бы равенство а — kp + + 〃ь где S V " и at > 0, ибо а не делится на р. Отсюда ab = (kp + 01)6 = kpb + &［瓦 и так как числа ab и kpb делятся на р, то и а】Ь делйтся на р・ Но Qi < р V <а и at не делится на р, причем sb < ab, что противоречит предположению относительно произведения ab. Итак, доказано, что а < р. Подобным же образом мн докажем, что Ь < р и, значит, ab < р2.
Далее, поскольку ab делится на р, имеем ab = /р, где / -— натуральное число, большее 1, так как иначе было бы р = ab, где а > 1 и 6 > 1 (ибо числа а и & не делятся на р).
С другой стороны, на основании неравенства аЬ < р2 получаем / < р. Число /, будучи натуральным числом > 1, имеет простой делитель gW!<"・ Учитывая теперь определение числа ", а также то, что произведение а瓦 делящееся иа 厶 делится также на простое число g V ", мы заключим, что хотя бы один нз сомножителей а и Ь должен делиться на q. Если, например, а делится на ?, то а = afq. Но / делится на д, следовательно, 2 =勿， где f — натуральное число. А так как ab = /р, то 废gb = tqp, откуда 优& = fp, причем, учитывая, что а = =а'% имеем а' < а, откуда ofb < ab、что противоречит предположению относительно произведення ab. Итак, предположение о том, что теорема 7 неверна, приводит к противоречию.
Из доказанной теоремы при помощи индукции можно получить следующее
С л едствие. Если а】, а?, ..., % — натуральные числа, произведение которых делится на простое число р, то по крайней мере одно из чисел %, а% .…&解 должно делиться ма р.
Доказательство. Это следствие справедливо для /и = 2. Предположим, что оно справедливо для m чнсел, и пусть числа аь 敗,一.,а^ a^+i являются
натуральными. Если произведение а^^^тйт^ делится на простое число р, то, согласно теореме 7, по крайней мере одно из двух чисел а^ ... ат и ат^ делится на р. Если число а】&2 •・・ &т делится на р, то в силу предположения, что следствие справедливо для т чисел, заключаем, что хотя бы одно из чисел。卜。龜・—,&足 делится на р. Итак, из справедливости следствия для m чисел следует его справедливость для m + 1 чисел.
Предположим теперь, что существуют натуральные числа, имеющие два различных канонических разложения на простые сомножители. Среди таких натуральных инсел существует, очевидно, наименьшее. Пусть это будет число п, которое кроме канонического разложение
n = q；哈…qg(2)
обладает разложением
п =尸｝尸** • •「，,(3)
где 「1, 「2, .•”「t — возрастающая последовательность простых чисел, а 力卜 力2, ...» bt—числа натуральные. Согласно (2), число п делится на д% и поэтому, в силу (3) и следствия теоремы 7, но крайней мере одно из чисел г(, 「2,・・・,г, должно делиться на gi・ Очевидно, это будет число 门，так как q\ — наименьший простой делитель числа (3). Но, согласно теореме 5, простое числи Г\ имеет только два натуральных делителя: 1 и 门， поскольку же простое число д〔 также является делителем числа 门,то должно быть r\ = д” Заменив в формуле (3) г】 на «1, мы, ввиду (2), получим для числа 也 1 где n = 9in\ следующее равенство:
"=0；「‘心…疗=g：「吟
Так как число п7 меньше чем п, то, в соответствии с предположением относительно числа 几，число %’ имеет только одно каноническое разложение на простые сомножители, откуда уже легко следует, что должно быть s = % 力=92, Г3 = 93, •…% =柒，％ к 仇，a = 62，.… as ^ bs. Таким образом, вопреки предположению, разложения (2) и (3) оказались идентичными. Следовательно, предположение, что существуют натуральные числа, имеющие два различных канойич^ских разложения на простые сомножители, приводит к противоречию.
Итак, доказана
Теорема 8. Каждое натуральное число п > 1 дает только одно разложение на простые сомножители, если «е обращать внимания на порядок сомножителей.
Какими цифрами могут начинаться и заканчиваться простые числа?
Последняя цифра простого числа, имеющего более чем одну цифру, не может быть четной, так как тогда число было бы >2 и четным и, следовательно, было бы составным; последняя цифра не может быть и 5, так как в этом случае число было бы >5 и делилось бы на 5 и, значит, было бы составным. Таким образом, последней цифрой простого числа >10 может быть только 1, 3, 7 или 9.
Ничего больше о цифрах простых чисел, превосходящих 10, в частности о комплексах нескольких последних или нескольких первых цифр простых чисел, сооб* щить нельзя, так как имеет место следующая теорема:
Если имеются две произвольные конечные последа-* вательности цифр (в десятичной системе счисления) а19 «2, •…，〃m и bu 瓦，...,bn, где bn = 1, 3, 7 или 9, то существует достаточно большое простое число р, у к。- торого первыми m цифрами будут последовательно а1я 。2 . •・,flm, а 办 последними цифрами будут последовав тельно 仇・ Ь» •…bn *).
Из этой теоремы, в частности, следует, что существуют простые числа, имеющие в начале и в конце до* статочно большое число цифр, равных 1 (в средней части числа могут быть цифры, отличные от 1). Но существует ли бесконечное множество простых чисел, все цифры которых являются единицами, мы не знаем. Мы знаем лишь несколько простых чисел, все цифры которых суть единицы, например, 11 я 11 111 111 111 111 111 111 111 =旦_・ Доказательство простоты последнего числа (предложенное М. Крайчиком)
erpinski, Sur les finals donnes, Actaerpinski, Sur les finals donnes, Acta4 Доказательство этой теоремы см. W. S i nombres premiers ayant des chiffres initiaux et Arithmetic, 5, 1959, 265—266.
erpinski, Sur les finals donnes, Acta
erpinski, Sur les finals donnes, Acta
сложно. Зато легко доказать, что если число, все цифры которого суть единицы, простое, то число его цифр также должно быть простым. Это условие^ оДиано,. т является достаточным, так как, например, ‘
111 == 3 • 37, 11111 = 41-271, 1 111 111 = 239-4649. [037 — 1
Число —§——，имеющее 37 цифр, также составное.
Найдены простые числа, составленные не только из одних цифр 1, которые остаются простыми при каждой перестановке их цифр. Среди двузначных таковыми являются числа: 13 и 31, 1 / и 71, 37 и 73, 79 и 97, среди трехзначных — числа: 113, 131, 311; 199, 919, 991; 337* 373, 733. Мы не знаем других таких чисел и не знаем, конечно ли их число. X. Е. Р^херт доказал, что для 3 < п < 6 • 10175 нет таких чисел, имеющих п цифр, кроме простых чисел, все цифры которых суть единицы.
Л. Мозер нашел все простые числа <100000, не меняющие своего значения, если их цифры выписать в обратном порядке. Их оказалось 102. Вот все такие числа <1000: 101, 131, 151, 181, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929. Неизвестно, существует ли бесконечно много таких простых чисел.
Мы не знаем, существует ли бесконечное множество простых чисел, первая и последняя цифры которых суть единицы, а остальные ——нули, как, например, число 101. Легко доказать» что такие простые числа должны быть вида 102" + 1, где п — натуральное число, однако это условие не является достаточным, так как, например, 1022 + 1 = 73- 137.
Нам известно мнзо простых чисел, среди цифр которых нет ни одного нуля, но мы не знаем, конечно или нет множество таких чисел. Можно доказать, что для всякого натурального числа т существуют простые числа, среди цифр которых имеется более чем т нулей. Мы не знаем, существует ли для всякого натурального числа m такое число а, что сумма всех цифр всякого простого числа р, большего а, будет больше чем /п.
Числа простых чисел, не превосходящих данное число
Для данного числа * обозначим через 冗(х) число простых чисел, не превосходящих х. Например, мы имеем： п(1) = 0, тс(2) = 1,农(3) = 2a 竄(4) =2* 野《5) =» 3,
気dO) N 心 m(10flj = 25, T(i000) = 168, т(10000) » 122», u(10«) n 5 761455, 寵(109) = 50 847 534, 當(HP)= =455 052 512.
Л. Лохер-Эрнст заметил, что для n > 50 выражение
дает достаточно хорошее приближенное значейие числа тс(п). Наяри1ч*ер, NIO) = 168, a f(10e) = 167,1. Для n = 1<F отношение п(п) : f(n) равно 1,(Ю7, а для п » =1Gm оно составляет 1,(Ю5.
Можно доказать элементарно (хотя доказательство будет длинным и сложным), что отношение ic(m) : f(n) стремится к еди««не, когда п возрастает неограниченно.
При больших m вычисление выражетгя /(п) представляет значительные трудности. Однако известны другие приближенные выражения для тс (п), например выражение -^^ (где In п о&)значает натуральный логарифм числа п). Ж. А员амар и Ш. де ла Валле-Пуссен в 1896 г. доказали, что отношение тс(п) к ^^ стремится к единице, когда п неограниченно возрастает. Отсюда следует, что отношение л-го простого числа ря к л In п стремится к единяле, когда л неогрантшно возрастает *)• Можно доказать, что миллиардное простое число (т. е. число рю*) имеет 11 цифр.
Легко доказать, что для натуральных n > 1 имеет те(П — 1) / я (п)
место неравенство ~ ；二丁 < —^, если п есть про- — . те<н)
стое число, и неравенство •；二［’ > ~, если п — число составное. Можно доказать, что отношение тс(п) к п стремится к нулю, когда п неограниченно возрастает. Вполне очевидло, что 冗("兀)=п для натуральных л.
Легко доказать, что существуют сколь угодно длинные последовательности, составленные нз последовательных натуральных тасел, которые не содержат ни одного простого числа. Примером последовательности.
состоящей из 加 таких чисел, может служить последовательность
(т + 1)I + 2,(加 + 1)! + 3, (т + 1)! + 4,{т + 1)! + (tn + 1),
ибо первое из чисел этой последовательности делится на 2, второе на 3 и т. д., последнее на m + 1 и, таким образом, все они являются числами составными.
Для /и = 100 это были бы огромные числа, однако уже между простыми числами 370 261 и 370 373 лежат 1J1 последовательных составных чисел. Среди ста последовательных чисел от 1 671 800 до 1 671 900 нет ни одного простого числа
Труднее было бы доказать, что существует простое число, которое с обеих сторон окружено произвольно большим числом составных чисел, т. е. что для каждого натурального числа m существует простое число р такое, что каждое из чисел р ——论 и р + kt где 论= у 1, 2,.・.,т, является составным.
Также трудным является доказательство теоремы Э. Ландау о том, что для достаточно больших натуральных чисел п мы имеем к(2к) V 2р(к), или, иначе говоря, что для таких п простых чисел 《孔 больше, чем простых чисел, лежащих между п и 2п.
Мы не знаем, для всех ли натуральных х > 1 и у>' > 1 выполняется неравенство ir(x + у) Wk(*) + 冗(У)・
Некоторые свойства л-го по порядку простого числа
Согласно теореме X. Ж. Шерка, доказанной им в 1830 г., для натуральных п при соответствующем вы* боре знаков + или — имеем следующие формулы:
用"=1 ±p1 士厶士士 。2“-2 + Р2“-1，
22n+l= 1 ±A 土?2土 ••• 土，2”-1 + 2夕2"。
Так, например,
网=1+0一02 -Р3+〃 + p5，
07= 1 +网一Pz 亠 р3 + р4-05+2网，‘
или 13= 1 +2 — 3 5 + 7+11, 17 = 1+ 2 - 3 ―■ 5 + + 7 --11 一+ 2*13.
Можно также доказать, что для натуральных п при соответствующем выборе знаков + или — имеем
p2-1= ±马士小土 -・■ ±p2n-l+P^
Например, "7 = "i + Р2 — Рз一Р4 + Ps + Ре, или 17 = н 2 十 3 — 5 — 7 4" 11 Ч" 13.
А. Шинцель доказал, что если а и Ь — положительные числа, причем а < 6, то существуют простые днска р и g такие, что а < у < 6.•
Можно доказать, что для каждого вещественного положительного х последовательность с общим членом Ри(пх)
—~— стремится к х, когда п неограниченно возрастает.
Доказано, что существует бесконечное множество простых чисел р таких, что последующее простое число ближе к числу р, чем простое число, предшествующее ему, а также таких, что предшествующее простое число ближе к числу р, чем простое число, следующее после р. Иными словами, доказано, что существует бесконечное множество натуральных чисел п таких, что Рп+1 —Рп < Л — А»т，Т. е. рп > Р"Т^?п+1 , а также, что существует бесконечно много натуральных чисел п таких, что рп V Pai^~P”i，・
Но мы не знаем, существует ли бесконечное множество таких п, для которых 办=,P〃-i 吉 Р计i . Высказано предположение, что ответ на этот вопрос должен быть положительным. Так, например, мы имеем 厶=上叱!^庄+1 для п = 16, 37, 40, 47, 55, 56, 240, 273.
П. Эрдеш и П. Туран доказали, что существует бесконечно много натуральных чисел /г таких, что 鰭〉Л»тР叶h и бесконечно много п таких, что 冠 < <厶一1乙+1・
Доказано, кроме того, что pn+i < "n-i + рп для п = 金3, 4, 5,…
Для последовательных простых чисел имеет место также следующая теорема (доказательство которой хотя и не трудное, но довольно длинное):
5 В Серпинский°"
Для каждого натурального m существует натурала ное чисм п такое, что
"Р2 рn
(Уже для m = 10п составляло бы несколько десятков тысяч, j
Можно указать четыре последовательных простых числа, дающих две пары чисел близнецов, например 11, 13, 17, 19 или 179, 181, 191, 193. Если такой комплекс составлен мз простых чисел р, р + 2, р + 6 и р + + 8, то мы говорим^ что ямеется четверка. В первом из указанных здесь примеров мы имеем четверку, а во втором нет. Другие примеры четверок мы получаем для р == 5, lOi, 191, 821, 1481, 3251. Высказано предположен ш№» что четверок существует бесконечно мяого.
В 呻вых десяти ниллио&ах, как подсчитал В. А. Голубев в 1959 г,, имеется 899 четверок, в первых же пятнадцати миллионах —1209. Самая далекая четверка, известная в настоящее время, была указана А. Ферье. Она получается при р = 2 863 308 731.
Многочлены и простые числа
Напрашивается вопрос, существует ли многочлен f(x) от переменной х с целыми коэффициентами, который для каждого натурального звачеяяя х дает простое число f(х). Докажи% что такого многочлена нет. Пусть
/任)=08^ +a1炉-1+...+小一1% + /
есть многочлен степени m с целыми коэффициентами О#, 01, . , ., Ощ, ГДе 的 # 0. ЕСЛИ бы МЫ ВЗЯЛИ Oq <0, то для достаточно больших х было бы f (х) < 0, поэтому будем предполагать, что % > 0. Тогда, как известно, существует такое целое число х©, что n = f “о) > 1 и f(x) > /(№)для х > Ха.
Докажем, что при любом натуральном 左 число /(х0 4- kn) будет составным. Пусть х и Л — натуральные чяела, тогда при всяком натуральном / число (%+力了--xi делится на ：(尤+刀)--% =瓦 откуда следует, что числа, о»(х + Л)«*^ — а^х^ для i=»0,1,2, tn делятся на Л и, зяачгкт, qgro f(x + h)—〃亢)также делится на й. Но в таком случае 〃友 + 启，——/(xj.
делится на 左4 или f(xQ'+ kn^— n = £м, _ что дает /(хв+Ы) =1 (/+1)/г и доказывает, что число /(Хо+Лд), которое, как мы знаем, >/(%©) =", делится на натуральное число /2 > 1 и, следовательно, является составным, что и требовалось доказать.
Итак, мы доказали, что если f(x) есть многочлен с целыми коэффициентами, где коэффициент при высшей степени х — число положителыюе, то для бесконечного множества натуральных чисел х число / (х) является составным.
Однако мы знаем такие многочлены, которые для многих последовательных натуральных чисел х принимают значения, являющиеся простыми числами^ Приме* ром такого многочлена может служить многочлен Эйлера х2 + х + 41, который для х = 0, 1,2,..., 39 дает разные простые числа. Высказано предположение, что существует бесконечно много натуральных чисел х, для которых х2 + х + 41 есть простое число.
Мы не знаем, существует ли такое натуральное число а >41, чтобы каждое &з чисел х2 + х + а для х = =0, 1, 2, ...» а — 2 было простым. Во всяком случае таких чисел а< 10® не существует.
Многочлен / — 79х + 1601 дает простые числа для х = 0, 1, 2, ..., 79, однако эти числа не все разные.
Возникает вопрос, существуют ли многочлены, которые для натуральных зиачениб переменной дают бесконечное множество простых чисел. Очевидно, существуют такие многочлены первой степени, например многочлен 2х+1, но мы не зиаем ни одного такого многочлена степени >1. Мы не знаем, является ли таким двучлен 尤2 + I, дающий простые числа для 尤=1, 2, 4, 6, 10. Подсчитано, что для х <110 000 есть 842 простых числа вида х?十 1 (где х ——натуральное число); для *V •< 100 000 есть 6656 таких чисел» для х < 180 000 их 11223. Высказано предположение, что для каждого натурального числа А существует бесконечно много простых чисел вида х? + fe, где х есть натуральное число.
Существует, очевидно* только одно простое число вида х3 + 1, где % — натуральное число» о диако выска* зано предположение, что существует бесконечно много простых чисел вида х* + 2* а также вида х3 ——2, fr® х ——натуральное чис^о (простые числа получаем npii х = 1, 3, 5, 29 и х = 9, 15, 19, 27 соотаетствеино)<
азаз5*
аз
аз
В 1962 г. Б. М. Бредихин доказал, что существует бесконечно много простых чисел вида х2 + у2 + 1, где х и у — целые числа. Можно доказать (хотя это и трудно), что существует бесконечное множество простых чисел вида х2 + у2 + z2 + 1, где х, 弘 z — натуральные числа. Позднее (в § 19) мы докажем, что существует бесконечно много простых чисел вида 炉十炉，где х и у — натуральные числа. Мы не знаем, существует ли бесконечное множество простых чисел, являющихся суммами кубов трех целых чисел.
Арифметические прогрессии, образованные из простых чисел
Доказано, что существует бесконечно много арифме- тических прогрессий, образованных из трех разных простых чисел. Мы знаем много прогрессий, образованных из трех различных простых чисел, первыми членами которых является число 3, наприйер: 3, 7, 11; 3, 11, 19; 3, 13, 23; 3, 17, 31; 3, 23, 43; 3, 31, 59; 3, 37, 71; 3, 41, 79; 3, 43» 83. Однако неизвестно, существует ли их бесконечно много.
Легко доказать, что не может быть арифметической прогрессии, образованной из трех разных простых чисел, первым членом которой было бы число 2 (так как третий член последовательности был бы четный >2). Высказано предположение, что существует бесконечно много арифметических прогрессий, образованных из трех простых чисел, первым членом которых является любое простое нечетное число.
Существует только одна арифметическая прогрессия с разностью 2, составленная из трех простых чисел, именно: 3, 5, 7 (так как из трех последовательных нечетных чисел одно всегда делится на 3), а также только одна такая арифметическая прогрессия с разностью 4, именно: 3, 7, 11. Очевидно, не может быть арифметических прогрессий, составленных из трех простых чисел, с нечетной разностью. Высказано предположение, что существует бесконечно много прогрессий с разностью 6, образованных тремя простыми числами. Таковыми являются, например, прогрессии: 5, 11, 17; 11, 17, 23; 17, 23, 29. Имеется также прогрессия с разностью 6, обра-
зованная из пяти простых чисел: 5, 11, 17, 23, 29. Однако она является единственной, так как в каждой прогрессии с разностью 6, составленной из пяти натуральных чисел, один из членов должен делиться на пять.
Напрашивается вопрос, существует ли арифметическая прогрессия, состоящая из любого числа разных простых чисел. Среди известных нам наибольшую длину имеет прогрессия, состоящая из 12 членов. Эта прогрессия была найдена В. А. Голубевым, ее первый член 23 143, а разность 30 030.
Мы не знаем, существует ли арифметическая прогрессия, образованная из ста разных простых чисел. М. Кантор доказал, что в арифметической прогрессии, составленной из п > 1 простых чисел, больших п, разность прогрессии должна делиться на каждое простое число <п. Отсюда следует, что если существует арифметическая прогрессия, образованная из ста разных простых чисел, то разность ее должна быть огромным чис- лом， имеющим по крайней мере несколько десятков цифр.
Высказано предположение, что если г есть натуральное число, делящееся на каждое простое число (где п ——заданное натуральное число > 1), то существует бесконечно много арифметических прогрессий с разностью г,"образованных из л последовательных простых чисел. Например, 47, 53, 59 есть арифметическая прогрессия с разностью 6, образованная тремя последовательными простыми числами. Другими такими прогрессиями являются 151, 157, 163; 167, 173, 179. Мы знаем также арифметические прогрессии с разностью 6, образованные из четырех последовательных простых чисел, например, 251, 257, 263, 269 или 1741, 1747, 1753,
Малая теорема Ферма
Теорема 9・ Если р — простое число, то для каж* доео целого числа а число。尸一а делится на р.
Доказательство. Пусть р — данное простое число. Теорема, очевидно, справедлива для числа а = I Предположим, что она справедлива для некоторого
натурального числа а. Согласно формуле Ньютона для двучлена, имеем
(a+1产=aР+(彳)。"’+ (6)。"2+ …+(Р)1)a+1， (1)
где для k = I, 2, ..., р ——1
/ р\ — Р S — D (р—2).. • (р —左 + DU/=1 • 2 …i，
причем, как известно, числа (?) являются целыми. Отсюда мы заключаем, что число 1 *2 ...左*(：) делится на р и, следовательно, согласно следствию теоремы 7, по крайней мере одно нз чисел 1, 2, •…，也，({) должно делиться на р. Но так как k<p, то ни одно из чисел 1, 2, •.., k не делится на р, следовательно, на р должно делиться число(^j- Отсюда, учитывая (1), мы заключаем, что число (а + 1)р —。卩一1 делится на р. Прибавив к нему число а^ ——а, делящееся на р (так как мы предполагаем, что теорема справедлива для числа а), мы обнаружим, что число (а + 1)р— (а + 1) делится на р, т. е. что теорема справедлива для числа а + I.
Таким образом, мы доказали посредством индукции» что теорема справедлива для каждого натурального числа а. Для числа 0 она, очевидно, также верна.
Если а — целое отрицательное число, то при р = 2 имеем а2 — а = а(а — 1), и так как из двух последовательных целых чис屮 а — 1 и а одно всегда четное» то всегда 2[а2 а !). Далее, прн р простом нечетном имеем (—о)р = —а% и поэтому (—а)р—(一а) »« 一(。卩一а). Следовательно теорема справедлива и для целых отрицательных чисел а. Таким образом, теорема 9 доказана полностью.
В качестве частного случая теоремы 9, для а = 2, мы получаем теорему, согласно которой для любого простого числа р число 2P — 2 делится на р. Возникает
>)Снмвол r/s означаем что число s делится на г. Читается так: ” делит «».
вопрос, будет ли верна обратная теорема, т. е. если п—» натуральное число > 1, такое, что п|2п —2, то должно ли п быть простым числом?
Для многих предполагаемых теорем, относящихся к простым числам, производилась проверка на большом числе частных случаев. Если бы мы проверили, например, все последовательные натуральные числа >1 и 《300, то обнаружили бы, что каждое такое натуральное число п, для которого 2П ——2 делится на п, является простым числом. Быть может, именно этот путь привел китайцев 25 веков назад к теореме, согласно которой, если для натурального числа п > 1 число 2门——2 делится на п, то число п простое. Однако эта теорема оказалась ложной, ибо число 2341 ——2, как мы сейчас покажем, делится на 341, а число 341 = 11 -31 является составным.
В том, что число 2341 — 2 делится на 341, мы можем убедиться следующим образом. Очевидно, 2341 — 2 = =(231)11 — 211 + 211—2. Число 210 — 1 = 1023 = 3-341 делится на 341. Значит, и число (210)3—1 также делится на 341 (так как для натуральных а, Ь, и k число 。左一决，как известно, делится на а —Ь). Числа 2口一2 = = 2(2】。一1) н 231 — 2 = 2[(21。)3 — 1] делятся на 341, откуда следует, что и число (231)11 — 2П делится на 341. Отсюда, в силу нашего равенства для числа 2341 — 2t тотчас же получаем, что это число делится на 341, что и требовалось доказать.
Естественно, возникает вопрос, существует ли бесконечно много натуральных чисел п, для которых китайская теорема неверна. Чтобы доказать, что ответ на этот вопрос является утвердительным, достаточно (имея в виду, что составное нечетное число 341 не удовлегет ряет теореме) доказать, что для каждого составного нечетного числа п, не удовлетворяющего указанной теореме, существует составное нечетное число, большее л; также не удовлетворяющее ей. •
Итак, предположим, что нечетное составное число 冷=а> где а и & — натуральные числа >1, не удовлетворяет китайской теореме и, значит, п|2п — 2. Число m = 2П — 1 = (2а)ь — 1 есть нечетное составное, так как оно делится на число 2а— 1, большее 1 (ибо а > >1) и меньшее чем m (ибо & > 1), причем т> п [(ибо n > 1). Таким образом, достаточно еще только
показать, что m|2m — 2. Мы имеем n|2n — 2, но п есть нечетное число, следовательно,九|2"一】—1, т. е. 2П~Х — 1 = ==knt где k — натуральное число. Отсюда 2м"4 r =22^Тт)・22^. (2п)» Число 2т~> — 1 = (2熊)就一I, таким образом, делится на число 2" — 10 m. Следовательно, и число 2m — 2 делится на т, и, значит, составное число т не удовлетворяет китайской теореме, что и требовалось доказать.
Возникает также вопрос, существуют ли составные четные числа, не удовлетворяющие китайской теореме. Только в I960 г. Д. X. Лемер нашел такое число: 161 038. Нахождение этого числа было очень сложным делом, проверить же, что оно является делителем числа 2161 038 — 2, нетрудно. Легко проверить, что 161 038 = = 2・73・1103, 161 037 = 32-29-617, 29— 1 «7-73, 229 — —1 = 1103-486 737, откуда следует, что число 2161 037 — —1 делится на 29— 1 и 239— 1, а значит, также на 73 и 1103. Таким образом, число 2161038 — 2 делится на 2, 73 и 1103, а так как эти числа являются разными простыми числами, то 2161038 — 2 делится на их произведение, т. е. на число 161 038, что и требовалось доказать.
В 1951 г. Н. Г. В. X. Биджер доказал, что существует бесконечно много четных чисел п, для которых число 2П — 2 делится на п.
Доказано также, что существует бесконечно много пар разных простых чисел ряд таких, что число 2Pq — —2 делится на pq. В 1958 г. А. Шинцель доказал, что для любого целого числа а и любого натурального т существуют разные простые числа р > m и q > т такие, что pq\a^ — а.
В связи с ложностью китайской теоремы напрашивается вопрос, существуют ли составные числа п такие, что для каждого целого а число d — а делится на л. Такие составные числа п мы называем абсолютно псевдопростыми1)- Высказано предположение (до сих пор не доказанное), что таких чисел имеется бесконечно много. Наименьшее из них есть число 561 = = 3-11-17.
Чтобы доказать, что число 561 есть абсолютно псевдопростое, достаточно доказать, что для всех целых а
*) Название псевдопростые оставлено для составных чисел л, для которых чнсло 2* — 2 делится на п.
число а561 — а делится на каждое из простых чисел 3, 11, 17.
Число а561 — а, очевидно, делится на 3, если а делится на 3. Если же а не делится на 3, то а есть число вида 3々 土 1» откуда а2 — 1 « (Зй ± I)2 — 1 = 3(3也 士 ± 2)比 следовательно, 3|а2— 1; отсюда 3|а2,28°— 1, а значит, и 31ase】一а.
Число а561 — а, очевидно, делится на 11, если число а делится на 11. Согласно теореме Ферма, для всех целых а имеем 11|а" — а = а (а10 — 1), так что если число а не делится на 11, то отсюда вытекает, что 11|а10 — 1 и, следовательно, 11|а10,56—1, откуда уже заключаем, что 11|а561 — а.
Число 0開1—а делится на 17, если число а делится на 17. Согласно теореме Ферма, для всех целых а имеем 17|а"一 @ Поэтому если чйсло а не делится на 17, то отсюда вытекает, что 17|а16— 1, откуда 17|д16'35— 1 и, значит, 17|@56i — @ (ибо 16・35 + 1 =561). Итак, мы доказали, что число 561 является абсолютно псевдо- простым.
Числами абсолютно псевдопростыми являются также
5• 29• 73, 7-13-31, 7-23-31, 7-31 *73.13-37.61, 5・17・29・113・337・673・2689;
известно и много других таких чисел.
Из малой теоремы Ферма вытекает, что если р — простое число >2, то число 2尸一〔—1 делится на р. Возникает вопрос, существуют ли простые числа р, для которых 2р~1 — 1 делится на р2. Мы знаем только два таких простых числа ", именно 1093 и 3511, и знаем, что нет других таких простых чисел р < 100 (Ю0; но мы не знаем, существуют ли такие числа, превосходящие 100 000, и конечно ли их количество. Мы не знаем также, существует ли бесконечно много простых чисел таких, для которых число 2Р-1 — 1 не делится на р2.
Из теоремы Ферма легко вытекает, что если р ~ простое число, то число 1 р~1 4- 2р~! 4- Зр-1 + ... + +(Р—1) р-1 + 1 делится на р. Г. Джуга высказал в 1950 г. предположение, что эта делимость имеет место только для простых чисел, и проверил его для всех чисел WO。00.
Доказательство теорем, согласно которым имеется бесконечно много простых чисел каждого из видов
4*4-1, 4*+3 и 6*十5
Пусть п означает любое натуральное число >1. Тогда число п! есть число четное, а нечетное число (п!)2 + 十 1 как число, большее единицы, согласно теореме 1, имеет простой делитель р, очевидно, нечетный и, следовательно, имеющий вид 4左 + 1 или 4左 + 3 (где k — целое число), причем р > п. Предположим, что р = = 4^ + 3. Очевидно, мы имеем (n!)2+JI (п!)2^4-0 + 1, ибо, как известно, для натуральных а и нечетных 加 число а771 + 1 делится на а + 1 (причем ат + 1 = (а + + 1)(。箱一1 — а1»—2 + …一a + 1). Так как 2(2月 + 1)= =4々 + 2 = р— 1, то, учитывая, что р|(п!)2 + 1, мы можем заключить, что рКп!)^1 + 1 и, следовательно, p[(n!)P + п!. Но, согласно теореме Ферма, р|(/И)Р —川・ Отсюда р|2п!, что невозможно, так как р есть простое нечетное число >п. Следовательно, р должно быть числом вида 4k + 1. Таким образом, мы доказали, что для каждого натурального числа n > 1 существует простое число >п, имеющее форму 4々 土 1 (и что таким числом является каждый простой делитель числа (п!)2 + 1). Тем самым доказана
Теорема /0. Простых чисел вида 4也十 I имеется бесконечно много.
В связи с нашим доказательством напрашивается вопрос, для каждого ли простого числа р вида 44 + 1 существует натуральное число п такое, что р|(я!)2 + 1， (Например, имеем: 5|(2!)2 十 1, 13|(6!)2 + 1). Можно показать (см. § 19), что если р есть простое число вида 4』,佇1)吁+ 1. Следовательно, 17|(8!)2 土 + 1, 29|(141)2.+ 1, 37|(18!)2 +：L
Возникает также вопрос, сколько имеется простых чисел вида 4々 + 3. Доказательство того, что их бесконечно много, опирается на следующую лемму.
Лемма. Каждое натуральное число вида 4^ + 3 имеет по меньшей мере один простой делитель того же вида.
Доказательство. Пусть п = 4k +■ 3. Это число имеет, очевидно, натуральные делители вида 4t+3 (где
t есть целое число) t так как само является одним из них. Обозначим через р наименьший из таких делителей. Ясно, что р > 1. Если бы р было числом составным, мы имели бы р = ab, где а и & были бы натуральными числами >1 и меньшими р, причем нечетными, так как р, будучи числом вида 4月 + 3, есть число нечетное. Оба числа а и & не могут быть вида 4f 十 1, так как тогда их произведение р = а& = (4力 + 1) (4^ + 1)= =4 (4幻2 + ti + t2) + I было бы вида 4f + 1, что исключено. Следовательно, по крайней мере одно из чисел а и 6 есть число вида 4f + 3. Так как делители р являются одновременно делителями п, то п будет иметь натуральный делитель вида 4f + 3, меньший р, что противоречит определению числа р. Итак, р — простое число. Таким образом, лемма доказана.
Пусть теперь п обозначает любое натуральное число. Число 4п! — 1 есть, очевидно, натуральное число вида 4А + 3. Согласно лемме, оно имеет по крайней мере один простой делитель р вида 4t 十 3. Здесь должно быть 卩 > п, так как число 4п! — 1, делясь на р, очевидно, не делится ни на одно натуральное число >1 и 《儿 Итак, мы доказали, что для каждого натурального числа п существует простое число >п, имеющее вид 4^ + 3.
Таким образом, доказана
Теорема //. Простых чисел вида 4^ + 3 имеется бесконечно много.
Обозначим для вещественного числа х через 冗i(x) число простых чисел вида 4fe + 1, не больших чем х, а через из (х) — число простых чисел вида 4々十 3, не больших чем х. Например, ui(10) = 1; 值(10)=2; hi(17)=仅3(17) =3;仅 1(100) = 11,仅з(100) = 13. Проверено, что 仅 1(х)《Вз(х) для X < 26 861. Однако было бы ошибочно думать, что всегда ui(x) <тсз(^), ибо, как установил Джт Лич в 1957 г., для х = 26 861 е(х)= =1473, а 仅з(#) = 1472.
Уже в 1914 г. Литтлвуд доказал, что существует бесконечное множество натуральных чисел х, для которых 仅i(x) >тсз(^), а также бесконечное множество натуральных X, для которых К1(х) <из(х). Мы видим, таким образом, какими ненадежными могут быть гипотезы относительно простых чисел, если они выдвигаются даже иа основании большого числа наблюдений.
Теоремы 10 и 11 можно сформулировать следующим образом.
Каждая из арифметических прогрессий
5, 9, 13, 17, 21, и
3, 7, 11, 15, 19, 23,
содержит бесконечно много простых чисел.
В связи с этим напрашивается вопрос: какие бесконечные арифметические прогрессии, составленные из натуральных чисел, содержат бесконечно много простых чисел?
Пусть дана бесконечная арифметическая прогрессия
а, а + г, а + 2г,
у которой первый член а и разность г—натуральные числа.
Если а и г имеют общий делитель d > 1, то, очевидно, каждое из чисел нашей последовательности будет делиться на d и поэтому, как легко видеть, ни один член прогрессии, кроме, быть может, первого члена, не будет простым числом. Отсюда следует: для того чтобы арифметическая прогрессия с первым членом а и разностью г содержала бесконечное число простых чисел, необходимо, чтобы а и г не имели общего делителя, большего 1. Как доказал еще в 1837 г. П. Г. Лежен Дирихле, это условие является также и достаточным.
Доказательство теоремы Дирихле, хотя позднее и было упрощено различными авторами, является сложным и длинным. Не менее сложно доказательство теоремы о том, что в каждой арифметической прогрессии, первый член и разность которой суть натуральные числа, не имеющие общего делителя, большего единицы, найдется по крайней мере одно простое число. Можно было бы подумать, что последняя теорема слабее теоремы Дирихле, однако нетрудно доказать, что она равносильна ей.、
Некоторые частные случаи теоремы Дирихле (так называемой теоремы об арифметической прогрессии) могут быть доказаны просто. Дадим, например, дока-
зательетво для случая а = 5, г — 6, для чего рассмотрим следующую лемму.
Лемма. Каждое натуральное число вида 6也十5 имеет по крайней мере один простой делитель того же вида.
Доказательство этой леммы совершенно аналогично доказательству леммы о числах вида 4ft + 3, с той лишь разницей, что вместо формы 4々 + 3 берем форму 6々 + 5, а затем используем замечание, что число вида 6f + 5, как не делящееся на 2 и 3, может иметь делители только вида 6f + 1 или 6f + 5, а также что произведение двух чисел вида 6f + 1 есть число того же вида.
Для доказательства самой теоремы возьмем какое- нибудь натуральное число п. Тогда число 6п! — 1 будет, очевидно, вида 6々 + 5 и, согласно лемме, будет иметь простой делитель р того же вида, причем, как легко показать, р > п. Итак, для каждого натурального числа п существует простое число р > п, имеющее форму 6也 + 5. Отсюда следует '
Теорема 12. Простых чисел вида 6ft + 5 имеется бесконечно много.
Итак, арифметическая прогрессия 5, 11, 17, 23, 29, 35,…содержит бесконечно много простых чисел. Следовательно, арифметическая прогрессия
5, 8, 11, 14, 17, 20, •…
включающая в себя все члены первой прогрессии, и подавно содержит бесконечно много простых чисел, т. е. существует бесконечное множество простых чисел вида 3々 + 2.
Существуют еще некоторые другие арифметические прогрессии, относительно которых можно легко доказать, что они содержат бесконечно много простых чисел. Таковой является, например, прогрессия 8ft + 1 (где 々=1, 2, 3,.・.)•
Некоторые гипотезы относительно простых чисел
Пусть теперь m — данное натуральное число >1. Расположим натуральные числа 1, 2, 3, .... п2 в п строк
43
по п чисел в каждой строке, т* е. составим таблицу
】，2, • • •, 比・♦.,
汽+ 1,掘+2,…，л + *2%2冷-[-1, 2л + 2,2д~I-kt ..., Зд,
(n1)九+ 1,…，(几-1)九+比"
Столбцы этой таблицы образуют арифметические про грессии (с п членами). А. Шинцель высказал предположение, что если 左 есть натуральное число <л, не имеющее общего с п делителя > 1, то А-й столбец нашей таблицы содержит по меньшей мере одно простое число. А. Горжелевскии проверил это предположение для всех натуральных чисел «< 100.
В. Серпинский высказал предположение, что каждая строка рассматриваемой таблицы (где л > 1) содержит по меньшей мере одно простое число. Это предположение было проверено А. Шницелем при помощи таблиц А. Вестерна и Д. X. Лемера для всех п<4500. Первая строка таблицы (для л > 1) содержит всегда простое число 2. Утверждение о том, что вторая строка таблицы содержит по крайней мере одно простое число, как легко видеть, равносильно теореме Чебышева и, следовательно, справедливо. Доказано также, что для л》3 третья строка таблицы содержит по крайней мере одно простое число, иными словами, что (для 九》3) между 2п и Зп лежит хотя бы одно простое число (что справедливо также для п = 2). Вообще доказано, что ДЛЯ п >9 каждая из девяти первых строк таблицы содержит по крайней мере одно простое число.
Так как двумя последними строчками таблицы являются
(n—1产，(n-1f+1, ••・，Д2 -冷，
м2 —内+1,д2 — Л--h 2, • • •,紋，
то из предположения В. Серпинского вытекает, что между каждыми двумя последовательными квадратами натуральных чисел лежит по меньшей мере два простых числа. Далее, так как легко доказать, что если
m — натуральное число, то существует натуральное число л такое, что
"3《0—1)2 И犷《(加+ ［尸，
то из предположения В. Серпинского следует, что между каждыми двумя поел ед овательными кубами натуральных чисел содержится по крайней мере два простых чнсла< Мы не знаем, справедливо ли это, однако доказано, что для достаточно больших натуральных чисел m между /л3 и (т + I)3 содержится произвольно мкого простых чисел.
Упомянем здесь еще о том, что, как заметил Ладислав Скуля, нз предположения относительно рассматриваемой таблицы (для я ^ 2, 3, ...) следует, что как (л + 1)-я, так н (л 4- 2)-я строки содержат хотя бы по одному простому числу (или что для натуральных л > > 1 каждая из последовательностей п? +「п* + 2, . •., 炉 + /I и М + п + 1, п2 + п + 2, ..п 2 + 2п содержит по крайней мере одно простое число). Для (л -Ь 3)-й строки это, вообще говоря, неверно. Например, при п = = 2 вли при % = 4 получаются последовательности 9, 10 н 25, 26, 27, 28, не сод^жащие ии одиого простого числа.
Из предположения отяоентельно рассматриваемой таблицы можно также легко вывести, что если все натуральные числа выписывать последовательно в строчки по п чисел в п-й строке, т. е. если составить бесконечную треугольную таблицу
23
456
78910
Н121314 15
то в каждой строке этой таблицы, начиная со второй, найдется по крайней мере одно простое число. Мы не знаем, справедливо ли это утверждение.
Теорема Лагравжа
Теорема 13. Если р — простое число 辽
М = ^^aхx^+ …十%./十阳 ⑴
45
есть многочлен степени 権》1 с целыми коэффициента^ ми, где коэффициент а。при высшей степени х не 5е- лится на р, то среди чисел
* = 0, 1, 2, 3,・・•，р — 1(2)
существует не более чем п таких, для которых число f(x) делится на р.
Док азател ь ст в о. Теорема справедлива для многочленов степени 1. В самом деле, если бы среди чисел (2) было по меньшей мере два различных числа xj и %2 > 〉％1 таких, что plf(xj) и p|f(x2)> то мы. имели бы plf(也)一f(%M а так как f(x) = a^x + @i, то мы имели бы p|ao(X2 —^i)» где %2 —修，будучи разностью двух различных чисел последовательности (2) и, значит, меньших р, не делится на р. Следовательно, р было бы делителем произведения двух натуральных чисел, не делящихся на р, что противоречит теореме 7.
Пусть теперь п — некоторое натуральное число >1. Предположим, что теорема справедлива для многочленов степени п— 1, и допустим при этом, что для некоторого многочлена (1) степени п теорема Лагранжа неверна, т. е. что существует набор целых чисел хь х2, xn+b где 0《尤1 < %2 < ... < Xn+i < р, таких, что plf(Xi) для t == I, 2, ..rt + 1.
Имеем /(%)—/(*1) = %(*"_*，)+%(*1_*；т)+ …
+@пт(х —%i)・ Отсюда, так как xft — xf = (^—-^i) X X(xft"1 + xrJ^-2 + ... +*f-2* + %L) для k—2, 3, ...» % то мы легко найдем, что
/(*)—/(%1) = (х —占)/1(%)，(3)
где fi(x) —многочлен степени п— 1 с целыми коэффициентами (зависящими от а% а】，...,ап и 打)，причем коэффициентом при хп-1 будет а。, т. е. число, не делящееся на р. .
На основании тождества (3), мы получим
/闯一/(匕)=(/一"力(修)(4)
для » = 2, 3, . • ” м + 1.
Но из того, что p\f(Xi) для I = 1, 2, ,.., n + 1, следует, что
尸!/(*»—/(*1) для » = 2, 3,・・・，冷十 1；
значит, согласно (4), имеем:
Р\(Х1 — х^/г(х^ для 1 = 2, 3,...,儿 + 1,
а так как числа xf — & для i = 2, 3, ..., n + 1 не делятся на р, то, в силу теоремы 7, должно быть
尸LA(修)Для » = 2, 3, ..., п+ 1,
вопреки предположению, что теорема справедлива для многочленов степени л— 1.
Следствие. Если р есть простое число, а (1)— многочлен степени п с целыми коэффициентами, и если существует более чем п натуральных чисел х <р, для которых f(x) делится на ", то все коэффициенты многочлена (1) делятся на р.
Доказательство. Предположим, что многочлен (1) удовлетворяет условию следствия, но не все коэффициенты его делятся на р. Пусть 。巽_丸 есть первый по порядку коэффициент, не делящийся на р. Предположим, что 氐 > 0. Для каждого натурального х, для которого f(x) делится на р, очевидно,
ё(х) = ап^+ап^х^+ ... +%
также делится на р. Таким образом, для многочлена g(#) степени k существует более чем п и, так Как h《n, более чем k натуральных чисел х < р, для которых "|g(#), что противоречит теореме Лагранжа (применимой, так как @пг не делится на р). Итак, предположим, .что ^=0, т. е. что все коэффициенты многочлена (1), кроме On, делятся на р. Но тогда, поскольку существует число х, для которого f(x) делится на р, мы, исходя из формулы (1), должны будем заключить, что р\ап^ Таким образом, предположение, что наше следствие несправедливо, в каждом случае приводит к противоречию.
Теорема Вильсона
Дадим теперь одно важное применение доказанного в § 17 следствия. Пусть р — простое число и пусть
/(х) = (х — 1)(х —2) ... (%—卩十 1) —%p-i 十 1
есть многочлен степени р — 2 с целыми коэффициентами. Для х= 1, 2, ..., р—1, согласно теореме Ферма, мы имеем 川*卩一* = *(*"】一1), откуда 川*1・
Но для % = 1, 2, ..., р— 1 мы, очевидно, также имеем
川(％—1)(* — 2) •・.(х—尸+ D，
так как для таких х один из сомножителей рассматриваемого произведения равен нулю. Учитывая, что разность двух чисел, делящихся на ", делится на р, мы заключаем, что p|f(x) для х = 1, 2, ..., р — 1.
Таким образом, согласно следствию теоремы Лагранжа (для п ~ р ——2), мы можем заключить, что все коэффициенты нашего многочлена, а значит, и его свободный член делятся на р.
Но для нечетных р (так как (—l)^-1 = 1) свободным членом многочлена f(х) является число 1-2-3 ... … (р— 1) + 1 или (р — 1)! + 1. Следовательно, если р есть простое нечетное число, то р\(р— 1)! + 1, что, впрочем, справедливо и для р = 2, так как 1! + 1 = 2. Таким образом, доказана
Теорема 14 (Вильсона). Для каждого простого числа р число (р— 1)! + 1 делится на р.
Следует заметить, что если для натурального числа л > 1 число (п — 1)! + 1 делится на п, то п должно быть простым числом. Действительно» если бы п было составным, то в силу того, что п = об, где а и b ——натуральные числа > 1 и <п, число а было бы одним из сомножителей произведения 1*2 ... (п—1) и, следовательно, число (п—1)! + 1 при делении иа а давало бы в остатке 1, между тем как, делясь иа п, оно и подавно должно делиться на а. Полученное противоречие доказывает, что число п должно быть простым.
Итак, для того чтобы натуральное число п > 1 было простим, необходимо и достаточно, чтобы число (п — —1)! + 1 делилось на п.
Таким образом, теоретически мы можем при помощи только одного деления выяснить, является данное число простым нли нет. Однако практически пользоваться этим способом неудобно, так как уже для трехзначных п число (п — !)! + 1 имеет более чем сто цифр. <8 ,
В связи с теоремой Вильсона возникает вопрос, возможны ли такие простые числа р, для которых (р — — 1)1 + 1 делится на р2. Оказывается, для р <；30000 имеется три таких числа: 5, 13 и 563. Мы не знаем, существует ли бесконечно много таких чисел р.
Теоремы Ферма и Вильсона можно соединить в одну следующую теорему:
Если р — простое число, то для любого целого числа а число а「+ (р — 1)!а делится на р.
В самом деле, если р—простое и а — произвольное целое число, то, согласно теореме Ферма, число а& — а делится на р, а так как, согласно теореме Вильсона, число а + (р — 1)!а = [1 + (р — 1)!]а делится на р, то и сумма этих чисел, т. е. число 必 + (р — 1) !а также делится на р. С другой стороны, если а@ + (р— 1)!а делится на р при любом целом а, то при а = 1 мы получаем отсюда теорему Вильсона, из которой следует, что при любом целом а р|(р—1)!а + а, а так как р\а^ + +(Р— 1)& то р|" + (р— 1)!а — [(р— 1)!а + а], т. е. "|аР — а, что дает теорему Ферма.
Легко также доказать, что теоремы Ферма и Вильсона можно соединить и в следующую теорему:
Если р — простое число, а — целое число, то число (р— 1)!ар + а делится на р (Лео Мозер).
Из теоремы Вильсона вытекает
Теорема 15 (Лейбница). Для того чтобы натуральное число р > 2 было простым, необходимо и достатт- но, чтобы число (р — 2)1 — 1 делилось на р.
Доказательство. Если число р > 2 является простым, то, согласно теореме Вильсона, число (р — 一1)!+ 1 делится на р. Учитывая, что (р—1)! = (р-^• ■—2)! (р — 1), мы имеем (р — 1)! + 1 = (р — 2)!р — —[(р — 2)! — 1], откуда видно, что число (р — 2)!—1 делится на р.
С другой стороны, если р[(р — 2)! — 1, то р|(" — —1)!—(р—1) и поэтому р|(р—1)1+ 1, откуда (напомним, что р > 2), как было уже доказано выше, следует, что р должно быть простым числом. Таким образом, теорема Лейбница доказана.
Если р есть простое число >3, то (р — 1)! > р, ибо тогда (р— 1)!》2(р — 1) = " + (р —2j> р. Поэтому число (р—1)! + 1, как число, большее р 禺 согласно
теореме Вильсона, делящееся на р, является числом составным.
Итак, если р > 3 есть простое число, то (р — 1)! + Г есть число составное. Отсюда следует, что существует бесконечное множество натуральных чисел п, для которых число и! + 1 является составным. Существует ли бесконечное множест во натуральных п, для которых число п! + 1 является простым, мы не зиаем.
Простыми являются числа 1! + 1 = 2, 2! + 1 = 3, 3! + 1 = 7; следующим простым числом того же вида является 11! + 1 39916801. Мы не знаем, являетсй ли простым число 27! + 1.
На основании теоремы Лейбница можно легко заключить, что существует бесконечное множество натуральных чисел п, для которых число п!——1 является составным. Но мы не знаем, существует ли бесконечное множество натуральных п, для которых число п! — 1 является простым (простыми являются числа 3!——1 = =5, 4! — 1 = 23, 6! — 1 = 719). Мы не знаем также, существует ли среди чисел каждого из видов р! + 1 и р! — 1, где р — простое число, бесконечное множество составных чисел.
Мы не знаем ответа на вопрос, существует ли бесконечное множество натуральных п, для которых число Р1Р2 ,рп + 1 является простым (рп есть n-е простое число), а также на вопрос, существует ли бесконечное множество таких натуральных чисел п, для которых число "i"2... рп + 1 является составным.
Числа "i + l=3, "i"2 +1=7, "1"2"з + 1 = 31, Р1"2"з"4 + 1 =211, "1"2"з"4"5 十 1 7= 2311 являются простыми, но числа "/2... рп + 1 для п = 6, 7 и 8 являются составными, делящимися соответственно на 59, 19 и 347.
Докажем еще (следуя идее А. Шинцеля), что для натуральных п > 3 произведение Qn всех простых чисел, меньших п, будет больше чем п.
Допустим, что при некотором натуральном п > 3 Qn《几.Тогда мы имели бы Qn — 1 < п. Число Qn — 1 не делится ни на одно простое число <п (так как такие числа являются делителями Qn), поэтому, учитывая, что м》4, мы заключаем, что число Qn— 1》 》Q《——1 = 5 > 1 имеет простой делитель р, который должен быть > п. Но тогда Qn — 1〉几,что приводит 50
к противоречию. Таким образом, Qn> п для п > 3, что и требовалось доказать.
Относительно произведения Рп всех простых чисел <^п можно доказать, что для натуральных п имеет место неравенство Рп < 4П, а для натуральных п > 29 неравенство Рп > 2П,
Доказано также, что для натуральных п > 2 сумма всех простых чисел ^п будет >п.
Разложение простого числа на сумму двух квадратов
Пусть теперь р обозначает простое число вида 4々 + + 1. Принимая во внимание четность числа ^—=2斩 найдем, что число
1 • 2 • 3 …E-q丄=(—1) • (—2)…(—P 2 丄) при делении на р дает, очевидно, такой же остаток, как число
(Р — 1) (Р — 2)…(р — Р 2 丄)'
Но последнее число, если его сомножители записать в обратном порядке, можно представить в виде
"人(p^丄 + 1)…(0一2)(0-1)>поэтому, если мы его умножим на (卩丁)! и заметим,что — =1-1, то найдем, что получившееся
число (р + 1)! дает при делении на р такой же остаток, как (£『)! . А так как (р— 1)! + 1, согласно теореме Вильсона, делится на р, то и число (%，广十 + 1 также делится на р. Таким образом, доказана
Теорема 76・ Если р есть простое число вида 4々 + + 1, го число (Р丁)!?+1 делится на р.
Для вывода следствия из этой теоремы нам понадо* бится следующая
Лемма. Если р ——простое число и а — целое число, не делящееся &а р, то существуют натуральные числа х<УЭ а У <^Р такае, что при соответствующем знаке 4- или — число ах ± у делится на р.
Доказательство. Пусть р — данное простое число и пусть m обозначает наибольшее натуральное число 《У^, так что m+1 >Vp и, следовательно, (т + I)2 > р. Рассмотрим целые числа ах — у, где х и у принимают значения 0, 1, 2, ..., т. Таких чисел имеется (m + I)2 > р, а так как при делении их на р различных остатков может быть не более чем р, то при двух разных системах чисел хь yi и х2, {/2, где, например, **》*2, числа @*1 ——^i и ах2 ——у» должны при делении на р давать одинаковые остатки и, значит, число @*1 - y1 — (fl^2 -У2)=0(%1 - *2)-(J/1 - y2) ДОЛЖНО делиться на р. Равенство 修 =打 здесь исключено, так как в этом случае число yi ——у? делилось бы на р, что, ввиду 0《У1 «加 кУрСр и аналогично 0<г/2 < Р» невозможно, поскольку системы хь у^ и х2, уз предполагаются разными. Исключено также и равенство у\ = =у?, так как в этом случае число a(*i——х2) делилось бы на р, откуда, согласно определению числа а, следовало бы, что число *1 ——х2 делится на р, а это невозможно (в последнем убеждаемся так же, как и в случае разности Ji —圾).Далее» так как %i >%2 и Х\±к* то число *1 ——х2 является натуральным, число же у\ — ——у? целое, отличное от нуля, следовательно, при соответствующем знаке, число у = ±(yi — у?) также является натуральным. Теперь замечаем, что х = хг —当《 W %i《加《VF， следовательно, x < ]/^, ибо равенство "=户 невозможно» поскольку р — простое число. Акалогячно у < Кр- При этом число ах 士 у, которое при соответствующем знаке равно числу @(修一х2)— —(jh — У2), делится на р. Таким образом, лемма доказана.
Пусть теперь р — простое число вида 4^ + 1 и пусть а =(互J" есть число, не делящееся на р (согласно следствию теоремы 7, как произведение нескольких натуральных чисел, меньших р). Тогда, в силу нашей леммы, существуют натуральные числа х<^Ур> у V
<Vp такие, что при соответствующем знаке + или — число ах ± у делится на р. Таким образом, в любом случае число а2х2 ——у2 = (ах,+ у) (ах — у) будет делиться на р. Но, на основании теоремы 16, число а2 十 1 делится на р, следовательно, и число а2х2 + х2 делится на р. Поскольку же числа о?^ + х2 и а?^ ——у2 делятся на р, то и их разность х2 + у2 делится на р н, следовательно, %2 + у?=月",где k ——натуральное число. Так как x<Vp и у < VA то 炉 + / V 2р, или 加 < 2р. откуда й < 2, а так как k ——натуральное число, то 々= =1, т. е. х2 + у2 = р. Таким образом, доказана
Теорема 17 (Ферма). Каждое простое число вида 4月 + 1 есть сумма двух, квадратов натуральных чисел.
Так, например, 5 = I2 + 22, 13 = 2? + З2, 17 = I2 + + 4\ 29 = 22 + б2, 37 =卩 + в2, 41 = 42 + 52, 53 =炉 + :+ 72, 61 = 52 б2, 73 = З2 + 82.
Докажем теперь, что разложение простого числа на сумму двух квадратов натуральных чисел единственно, если не обращать внимания на порядок слагаемых. Впрочем, мы докажем даже более общее предложение.
Теорема /5. Пусть а и b — данные натуральные числа, тогда ни оОяо простое число р нельзя представить двумя различными способами s форме р = ах2 +' + by”, где х и у — натуральные числа, если s случае а = Ь = 1 не обращать внимания на порядок слагаемых.
Доказательство. Предположим, что простое число р допускает два разложения:
р = ах2 十 by2 = ал；十 ”％
где х, у, xi, у】—натуральные числа. Отсюда получаем Р2 = (^1 + 方"1)2.+。"汇物一"i)2 = (0*1一包他 1)2 +. 汁 ab(xyi + уху.
Но (ахх1 + byyi) (xyt + ух】)=(ox? + 方英)修协卞 Ч (ox；+ 如;)乃="(%助 + x力. Таким образом, по крайней мере один из сомножителей левой части должен делиться на простое число р.
Если р\ахх\ + Ьууи то из первого выражения для р2 следует, что должно быть ху】一y*i = 0 и, следовательно, xyi = ухи р и axxi + Ьууп рх = (ах2 + Ьу2)хх = рхь откуда х = *i, а значит, н у = уь
Если же р|*У1 + y*i, то из второго выражения для р2 следует, что axxi — byy\ = 0 н р2 = 〃力(北矶 + yxi)2.
причем последнее, если учесть, что числа х, у,修 и 力 являются натуральными, возможно только, тогда, когда а = b = 1. Поэтому имеем р = ху\ + ухх и xxi — уу\ — =0, что дает нам равенство рх = (х2 + 炉)勿=РУъ откуда х = у、и, следовательно (принимая во внимание, что р =■炉 + у2 n 后十У；), У =修.Таким образом, наши разложения отличаются одно от другого только поряд* ком слагаемых. Теорема 18 доказана.
Из теоремы 18 тотчас же следует, что если натуральное число п можно представить хотя бы двумя способами в виде суммы двух квадратов натуральных чисел (при условии, что два разложения, отличающиеся только порядком слагаемых, не считаются различными), то п не является простым числом. Поэтому, например, из того что 2501 = I2 + 502 = 102 + 492, мы заключаем, что число 2501 не является простым.
Пусть тип — натуральные числа. Имеем т4 +； .+ 4孔4 =(招产 + (2n2)2 n (m2 — 2吟2 + (2mn)2.
Если m = n или m = 2n, то наши разложения на суммы квадратов одинаковы, но тогда мы имеем либо т4 + 4п4 = 5п4, что является простым числом только для /п = n = 1, либо т4 + 4" = 20п4, что является числом составным. Если же /п * п н m * 2п, то, как легко доказать, наши разложения отличаются друг от друга не только порядком слагаемых, и, значит, число 卅十 + 4" — составное. Следовательно,
Если тип — натуральные числа, из которых по крайней мере одно отлично от единицы, то число ап’ 十 j 4孔4 является составным.
В частности (для m = 1), отсюда следует, что все числа вида 4n4 + 1, где п — натуральное число >1, являются составными.
Если мы имеем два разложения данного натурального числа на суммы двух квадратов (отличающиеся друг от друга не только порядком слагаемых), то нетрудно показать, что можно найти представление этого числа в виде произведения двух натуральных чисел, больших единицы.
В частности^ совершенно элементарно можно получить следующее разложение на множители
т4 + 4載 » (ап2 + 2шп + 2л2) (т2 —2тп + 2п2),
Заметим, однако, что если натуральное число допускает только одно разложение на сумму двух квадратов натуральных чисел, то отсюда еще не следует, что оно должно быть простым числом. Например, как легко убедиться, числа 10, 18, 45 дают каждое только одно разложение: 10 == I2 + З2, 18 = З2 + З2, 45 = З2 + б2.
Но можно доказать, что если натуральное нечетное число п дает только одно разложение на сумму двух квадратов целых чисел > 0 (если не считать различными разложения, отличающиеся только порядком слагаемых), причем в этом разложении слагаемые не имеют общего делителя >1, то п является простым числом. Основываясь на этом, при помощи электронной вычислительной машины ЕМС, находящейся в Варшавском политехническом институте, удалось показать, что число 239 — 7 есть простое; произведенное исследование показало, что существует только одно разложение этого числа на сумму двух квадратов, именно
239 一 7 = 64 045« + 738 6842,
причем в этом разложении слагаемые не имеют общего делителя >1.
О числах 2П — 7 для п = 4, 5,・..,38 известно, что они являются составными. В 1956 г. П. Эрдеш поставил вопрос, все ли числа 2П — 7 для натуральных п > 3 составные. Ответ на этот вопрос, как мы видим, отрицателен.
Числа 2П — 7 являются составными для п = 4。,41,... ...,50, ибо они, как это было подтверждено, делятся соответственно на 3, 5, 3, 107, 3, 5, 3, 11, 3, 61, 3. Таким образом, среди чисел 2n — 7 для натуральных п, где 3 < п<50, имеется только одно простое (для п = 39).
Легко доказать, что среди чисел 2P — 7, где р — простое число, имеется бесконечно много составных. Действительно, согласно теореме 10, существует бесконечно много простых чисел вида 4А + 1, а для каждого такого простого числа р, в силу того, что 5|24— 1, имеем 5|2‘在一1, откуда 5|2晶+〔 一2, а значит, также 512P — 7.
Мы не знаем, существует ли бесконечное множество натуральных чисел п, для которых число 2П — 7 является простым.
В связи с теоремой 17 напрашивается вопрос, что можно сообщить о разложениях других простых чисел на суммы двух квадратов.
Число 2 имеет, очевидно, только одно представление в виде суммы двух квадратов натуральных чисел: 2 = I2 + I2. Таким образом, остается еще исследовать простые числа вида 4力 + 3 (где 月=0, 1, 2, ,..). Легко доказать, что ни одно натуральное число этого вида не может быть представлено в виде суммы двух квадратов целых чисел. Действительно, поскольку это число нечетное, то в случае 4^ + 3 = х2 + i/2 целые числа х и у не могли бы быть оба четными или же нечетными. Таким образом, одно из них должно быть четным, а другое нечетным. Но квадрат четного числа при делении на 4 дает в остатке нуль, квадрат же нечетного — единицу. Следовательно, сумма л2 + у2 при делении на 4 дала бы в остатке 1, в то время как число 4左 + 3 дает в остатке 3. Формула 4月 + 3 = х? + у2, таким образом, оказывается невозможной при целых k, х и у.
Итак, среди простых чисел только число 2 “ простые числа вида 4月 + 1 разлагаются на суммы двух квадратов натуральных чисел, причем каждое из них дает только одно такое разложение (если не считать различными разложения, отличающиеся только порядком слагаемых). 、
Труднее ответить на вопрос, какие натуральные числа являются суммами двух квадратов натуральных чисел. Можно доказать, что для того чтобы натуральное число п было суммой двух квадратов натуральных чисел, необходимо и достаточно, чтобы в его разложении на простые сомножители сомножители вида 4月 + 3, если они встречаются, входили в степенях с четными показателями и, кроме того, чтобы либо число 2 входило с нечетным показателем, либо число п имело по крайней мере один простой делитель вида 4^+1.
Исследован также вопрос, сколько данное натуральное число п дает разложений на суммы двух квадратов натуральных чисел. Оказывается, это зависит от разложения числа п на простые сомножители. Можно доказать, что существуют натуральные числа, дающие произвольно много разложений на суммы двух квадратов натуральных чисел. Число 65 дает два разложения на суммы двух квадратов: 65 = 12+82=42+72; чис- 56
ло 1105 дает четыре таких разложения: 1105 = 42 + + 33® = 92 + 322 = 12® + 31& = 232 + 24».
Разложение простого числа
на разность двух квадратов и другие разложения
Напрашивается вопрос, какие простые числа и сколькими способами могут быть представлены в виде разности двух квадратов натуральных чисел.
Предположим, что простое число р разлагается на разность двух квадратов натуральных чисел:卩=炉一 ——у2, где х и у ——натуральные числа, причем, очевидно, х> у. Отсюда р = （х —，）（％ +，）и, значит, х — у и х + у являются натуральными делителями числа р, причем первый меньше второго. Но так как р — простое число, то х — , = L х + у = р и, следовательно, % =巴寺А , у = Pf-・ Таким образом, число р должно быть нечетным, и в этом случае мы имеем единственное разложение
尸（中У—5
Итак, доказана
Теорема /9・ Каждое нечетное . простое число представимо & виде разности двух квадратов натуральных чисел и притом только одним способом.
Легко доказать, что для того чтобы натуральное число п > 1 было разностью двух квадратов натуральных чисел, необходимо и достаточно, чтобы при делении на 4 оно не давало в остатке 2.
Можно доказать, что существуют числа, допускающие достаточно большое число разложений на разность двух квадратов. Из теоремы 19 следует, что натуральное число, допускающее более чем одно разложение на разность двух квадратов натуральных чисел, не является простым.
Впрочем, легко также доказать, что если нечетное число имеет только одно разложение иа разность двух квадратов целых чисел, то оно является простым. В самом деле, предположим, что нечетное число
57
n — составное и, значит,九=ab, где а и 6 ——натуральные числа > I. Очевидно, имеем
〃=(宇)~ 宁)2 =(宇)~^「
причем если, например, а》6, то п——1 = ab — 1 > > a — b (так как 6 > 1), и, следовательно, наши разложения являются различными.
Такйм образом, нечетное составное число дает по крайней мере два различных разложения на разность двух квадратов целых чисел. Заметим, однако, что имеются нечетные составные числа, представимые единственным способом в виде разности двух квадратов натуральных чисел, например число 9. (Можно доказать, что такими числами являются квадраты простых нечетных чисел.)
Перейдем теперь к вопросу о разложении простых чисел на суммы трех квадратов натуральных чисел.
Можно доказать» что существует бесконечно много простых чисел, являющихся суммами трех квадратов натуральных чисел, а также бесконечно много простых чисел, не являющихся такими суммами. Среди простых чисел <100 суммами трех квадратов натуральных чисел являются только следующие:
3 = [2 + 卩 + [2, П = р+ р + 32, 17 = 22 + 22 + З2, 19 = N + 32 + З2, 29 = 22 + З2 + 42, 41 = 12 + 22 + 62 = =З2 + 42 + 42, 43 = З2 + З2 + 52, 53 = I2 + 42 + 62, 59 = I? + 32 + 72, 61 = 32 + 42 + б% 67 = 32 + 32 + 72, 73 = 12 + 62 + 62, 83 = I2 + I2 + 92 = З2 + 52 + 72, 89 = ==22 + 22 + 92 = 22 + 62 + 72 == З2 + 42 + 82, 97 = 52 + ,+ 62 + 62.
Мы видим также, что существуют простые числа, имеющие более чем одно разложение на сумму трех квадратов натуральных чисел, например числа 41, 83 и 89.
Легко доказать, что каждое целое число можно представить бесконечным числом способов в виде х2 + + у2 ——22, где х, у, 2 ——натуральные числа. Для этого достаточно заметить, что для целых 也 н £ имеют место тождества:
2也一1 士 (2/)2 + 伊一г/2)2 — (k — 2f2 — 1)2,2左=⑵ + I)2 + 伊一2於一2/产一他一2f2-2f - I)%
Что же касается разложений простых чисел на суммы четырех квадратов натуральных чисел, то можно доказать, что такие разложения имеют все простые числа, за исключением чисел: 2, 3, 5, 11, 17, 29 и 41.
Можно также доказать, что единственными простыми числами, которые не представимы в виде суммы пяти квадратов натуральных чисел, являются числа 2, 3 и 7 и что для каждого натурального числа m > 3 существует только конечное число простых чисел, не являющихся суммами m квадратов натуральных чисел.
И. Човла высказал предположение, что если число 1 считать простым (как это прежде иногда делали), то каждое натуральное число является суммой восьми или меньшего числа квадратов простых чисел. Это проверено для натуральных чисел <288 000.
В связи с теоремой 17 напрашивается вопрос, какие простые числа могут быть представлены в форме х2 + + 2y2, или в форме х2 + 3炉，где х и у — натуральные числа. Здесь имеет место следующая теорема.
Для того чтобы простое число р можно было представить в виде х2 + 2у2, где # 〃 у 一 натуральные числа, необходимо и достаточно, чтобы р было вида 8左 + 1 или 8也 + 3. Каждое простое число этих видов дает только одно разложение вида х2 + 2у2 (что вытекает из теоремы 18).
Так, например,
3-12+2- I2, 11 = 324-2- I2, 17=32+2 • 2% 19=产+2・ 32.
Высказано предположение, что существует бесконечно много простых чисел р вида 8^ + 1 и также вида 8也 + 3 таких, что р = I2 + 2у2, где у — натуральное число, а также бесконечно много таких, что р = х2 + + 2 • I?, где х — натуральное число. Например, 73 = =Р + 2 • 62, 83 = 92 + 2- I2.
Для того чтобы простое число р можно было представить в виде х2 + Зу2, где х и у — натуральные числа, необходимо и достаточно, чтобы р было вида 6^ + 1- Каждое простое число этого вида дает только одно раз- ложение вида х2 + Зу2.
Так, например, 7 — 22 + 3 - I2, 13 = I2 + 3 • 22, 19 = =42 + 3 • 12, 31 = 22 + З-З2, 37 = 52 + 3 • 22. Высказано предположение, что существует бесконечно много простых чисел р вида 6也 + 1 таких, что р = I2 + Зу2, где 59
у — натуральное число, а также бесконечно много таких, что р = х2 + 3 - I2, где х — натуральное число. Имеем, например, 67 = 82 + 3 • I2, 103 = 102 + 3 • I2,, 109 =产 + з・62.
Из теоремы 17 непосредственно следует, что для того чтобы простое число р можно было представить е виде %2 + 4y2, где х и у — натуральные числа, необ^ ходило “ достаточно, чтобы р было вида 4^ + 1.
Доказана также следующая теорема:
Для того чтобы простое нечетное число р можно было представить в виде х2 ——2炉，где х и у ——натуральные числа, необходимо и достаточно, чтобы р было чис^ лом одного из видов: 8k + 1 или 8k + 7 】)•
Займемся теперь вопросом, какие простые числа являются суммами двух кубов натуральных чисел. На этот вопрос можно легко дать ответ. Действительно, если простое число р является суммой двух кубов натуральных чисел, р — х3 + у3, то х + у|р, и если хотя бы одно из чисел х, у оказалось бы больше единицы, то было бы х + у <С х3 + у3 — р, т. е. число р имело бы натуральный делитель % + у, больший единицы и менв* ший р, что невозможно. Таким образом, должно быть % = у = I и, следовательно, р = 2.
Итак, ни одно простое число, кроме числа 2 = I3 +] + I3, не является суммой двух кубов натуральных чисел.
Какие же простые числа являются разностями двух кубов натуральных чисел? Если р — простое число и р = %з —丸 где х и у — натуральные числа, то х > у, и имеем р н %3一w=(*一力(%2 + 刑 + 产).так как здесь второй сомножитель больше первого, то должно быть х — у == 1 и х2 + ху + у2 = р, откуда 卩=炉一 —(%—1)з = з炉—з%+ 1.
Таким образом, простое число р является разностью двух кубов натуральных (и притом последовательных) чисел тогда и только тогда, когда оно имеет вид Зх(х—* —1) + 1, где 尤一натуральное число, большее единицы*
Высказано предположение, что таких простых чисел существует бесконечно много. Для г = 2, 3, 4, 5 мы получаем здесь простые числа 7 — 23——I3, 19 = З3 — 23,
])См. W« Sierpinski, Teoria liczb, II, Warszawa, 195Я str, 338, 446,
37 = 4s — З3, 61 = 53 — 43; для # = 6 получаем составное число 91 == 7* 13; для * = 7 — простое число 127 = =7® — 63; для * = 8 и * = 9 — составные числа 169 = ==132 и 217 = 7-31; для х = 10, 11, 12 — простые числа 271 = 103 —93, 331 = 113 —103, 397= 123 — II3; для *=13 — составное число 469 = 7,67; для х = 14 и 15 — простые числа 547 = 143— 133 и 631 = 153— 143; для х = 16 и * = 17 — составные числа 721 = 7-103 и 817 = 19* 43; для 尤=18 — простое число 919 = 183 — —173.
Итак, все простые числа <1000, являющиеся разностями двух кубов натуральных чисел, суть следующие: 7, 19, 37, 61, 127, 271, 331, 397, 547, 631 и 919.
Легко можно доказать, что существует бесконечное множество простых чисел, не являющихся разностями двух кубов натуральных чисел. В самом деле, мы до жазали, что каждое простое число, являющееся разностью двух кубов натуральных чисел, есть число вида Зх (х——1) + 1, где х ——натуральное число > 1. Но нз двух последовательных натуральных чисел х — 1 и х одно всегда четное. Следовательно, наше простое число должно быть вида 6А 4- 1. Но, согласно теореме 12, существует бесконечно много простых чисел вида 6А + 5, ни одно из которых, очевидно, не является числом вида 6论 + 1 и, следовательно, не является разностью двух кубов натуральных чисел. Заметим, однако, что имеются составные числа вида 6^ + 5, являющиеся разностями двух кубов натуральных чисел, например число 215 n =6 ・35 + 5 = & ——I3. Можно также доказать, хотя это было бы труднее, что существует бесконечно много простых чисел вида 6论 + 1, не являющихся разностями двух кубов натуральных чисел. Таковыми будут, например, простые числа 31, 67, 103, 139, 157.
чисел.чисел.Высказано предположение, что простых чисел, являющихся суммами трех кубов натуральных чисел, существует бесконечно много. Высказано даже бадее сильное предположение, что уже простых чисел вида х3 +* + 2 = х3 + Р + I3, где % — натуральное число, имеется бесконечно много. Таковы, например, простые числа 3=广 + 2,29 = 33 + 2, 127 = 53 + 2, 24 391 = 293 4- 2. Можно доказать, что существует бесконечно много простых чисел, не являющихся суммами трех кубов целых
чисел.
чисел.
Легко доказать, что ни одно простое число >2 не является суммой двух n-х степеней натуральных чисел, где п есть нечетное число, большее единицы (доказательство аналогично изложенному выше для случая п = 3). Заметим еше, что К.①.Рот в 1951 г. доказал, что каждое достаточно большое натуральное число является суммой восьми кубов натуральных чисел, из которых по крайней мере семь ——кубы простых чисел.
Квадратичные вычеты
Если р — простое число, то квадратичным в ы- четом для числа р называется каждое целое число г, для которого существует целое число х такое, что число х2 — г делится на р. Другими словами, целое число г называется квадратичным вычетом для р, если существует квадрат целого числа, дающий при делении на р такой же остаток, как и г. Целые числа, не являющиеся квадратичными вычетами для р, называются квадратичными невычетами для р.
Для числа 2, очевидно, каждое целое число является квадратичным вычетом, так как если г — нечетное число, то 2|12 — г, если же г — четное число, то 2|02 — г.
Пусть теперь р — простое нечетное число. Выясним, сколько в последовательности 1> 2, 3, ..., р—1 имеется квадратичных вычетов для р.
Обозначим через гх остаток от деления числа 炉 На р. Для целых х числа гх будут, очевидно, всеми квадратичными вычетами для р (так как р|х2 — &). Значит, в частности, квадратичным вычетом для р будет каждое из чисел
尸 1'尸2，尸р — 1(1)
n — 1
(число ^--gнатуральное, так как мы предположили, что р является простым нечетным числом). Числа последовательности (1), очевидно, отличны от нуля (так как ни одно из чисел Р, 22, ..., (^у^)“ не делится на р) и, следовательно, являются числами последовательности 1, 2, 3, р — 1. Покажем,、то они все различные. Предположим, что для некоторых натуральных i и j, где Y 丿《 尸 £ L, мн имеем 门=4 Это означает,
что числа i2 и 尸 дают при делении на р одинаковые остатки и, следовательно, число 产一卩=(了 一》)(了 十力) делится на р. Но, в силу неравенства для i и j, числа / — i и / + г являются натуральными, причем оба они меньше р (так как / + i < 2j < р — 1 < р). Таким образом, число р должно быть делителем произведения двух натуральных чисел, меньших р, что невозможно.
Итак, мы доказали, что г£ ¥= ^ для Y j《&彳】• Следовательно, среди чисел последовательности 1, 2, ,.р——1 мы имеем по крайней мере ^^— квадратичных вычетов для р. Докажем теперь, что в этой последовательности никаких других квадратичных вычетов для р, кроме чисел (1), не содержится. Предположим для доказательства, что г есть число из последовательности 1, 2,・..,р——1, являющееся квадратичным вычетом для р. Тогда существует целое число а такое, что
р\а2 ——г. Отсюда следует, что р|(а2) 2 —г 2 , т. е. р\ар'х — г^.
Далее, так как число г не делится на р, то и число а не делится на р. Поэтому, согласно теореме Ферма, имеем 川а"】一1. Следовательно, р I (арв| — 1)— —(a*：—г 2 丿，т. е. р\г £ —1. Таким образом, имеем p\ri 2 — 1 для / = 1, 2, ..., Р^1 ・ Но, согласно тео-
реме Лагранжа, многочлен х 2 —1 не может делиться на р для более чем ^~ различных значений х из последовательности 0, 1, 2, ...» р——1. Отсюда следует, что, кроме 々一 чисел (1), в последовательности 1, 2,
р — 1 нет других чисел г, для которых р\г~^ —1, т. е. в этой последовательности нет других квадратичных вычетов для р. Такйм образом, доказана
Теорема 20. Если р есть простое нечетное число, то е последовательности 1, 2, 3, ...» р— 1 мы имеем точно —2— квадратичных вычетов для р (и, очевидно, столько
жб квадратичных невычетов для р* так как р — 1 —
2 - 2 丿，
Из доказательства теоремы непосредственно следует, что для 1юлучения всех чисел последовательности 1, 2,...
д — 1, являющихся квадратичными вычетами для простого нечетного числа р, достаточно определить остатки от деления на р чисел
D,22, 32(唳)'•
Таким путем мы найдем, например, что всеми квадратичными положительными вычетами для 13，меньшими 13, являются числа 1, 4, 9, 3, 12, 10 и, следовательно, невычетами для 13 (среди чисел >0 и < 13) будут числа 2, 5, 6, 7, 8 и 11.
Как мы уже доказали выше, число г из последовательности 1, 2, ..., р — 1 является квадратичным вычетом для простого нечетного р тогда и только тогда, ко- гда число г 2 — 1 делится на р. Таким образом, если число а из указанной последовательности является 0一1 квадратичным невычетом для р, то число а 2 — 1 не делится на р. Но, согласно теореме Ферма, число 必-1 — 1 делится на р, а так как@"1—1=(а 2 —1)Х
X ^а 2 +1 丿， причем первый сомножитель правой части ие делится на р, то должен делиться второй сомно-
житель, т. в/>|0 2 +1., Следовательно, число а из последовательности 1, 2, ..., р — 1 является квадратичным вычетом для простого нечетного числа р, если р\а 2 ——1, н невычетом, если р\а 2 +1.
Заметим, что для составных чисел дело обстоит иначе. Например, для 孔=15 среди натуральных чисел <15 только пять (следовательно, меньше чем ——= /) являются квадратичными вычетами для числа 15, именно числа 1, 4, 6, 9 и 10, а остальные 9 иисел являются квадратичными невычетами для числа 15. Среди натуральных чисел <8 только два, именно числа 1 и 4 яв* ляются квадратичными вычетами для числа 8.
Заметим еще, что А. Вале Винс нашел теорему, согласно которой нечетное числап является простым тогда 〃 только тогда, когда ни одно из чисел 22, З2, 43,・・. • • о при делении на п не дает в остатке ни(X ни \.
Для простых чисел изучены также вычеты кубические, биквадратичные и высших степеней. Можно дока「 зать, что для каждого нечетного числа п существует бесконечно много простых чисел р, для которых каждое целое число является вычетом п-й степени. Так, например, для чисел 5 и 11 каждое целое число является кубическим вычетом, для чисел же 5 и 7 каждое целое число является вычетом 5-й степени.
Доказательство того, что каждое целое число является вычетом 5-й степени для простого числа 7, вытекает непосредственно из следующих формул, которые легко можно проверить:
7I05 —0, 7|15—h 7|45—2,. 7叮「3, 712s— 4,7I35 —5, 7|6S —6.
Можно доказать, цто для простых чисел 5 и 17 ка- ждое целое число является вычетом любой нечетной степени. Можно также доказать, что для того чтобы для простого числа р каждое целое число было вычетом любой нечетной степени, необходимо и достаточно, чтобы простое число р было вида 23* + 1, т. е. чтобы оно было простым числом Ферма.
Числа Ферма
Числами Ферма называются числа вида Г^ = =22*+ 1, где 月=。,1, 2,.・.Знаменитый математик XVII века П. Ферма предполагал, что все такие числа являются простыми. Это справедливо для ^ — 0, 1, 2, 3, 4, но Л. Эйлер в 1732 г. обнаружил, что число
吊=2亦 + 1 = 4294967297, имеющее 10 цифр, является составным: оно делится иа 641. В настоящее время мы знаем уже 37 составных чисел 尸а, именно для 亙=5, 6, 7, 8, 9, 10, 11, 12, J3, 14, 15, 16, 18. 23, 36, 38, 39, 55, 58, 63, 73, 77, 81, 117, 125, 144, 150, 207, 226, 228, 260, 267, 268, 284, 316, 452, 1945.
Среди этих 37 составных чисел F^ имеются такие, для которых нам известны их разложения на простые сомножители (Например, F$ и 户6), имеются такие, для которых мы не знаем этих разложений, но знаем разложения в произведения двух целых чисел >1 (например, 尸 1945), наконец, имеются и такие, для которых мы не знаем ни одного разложения в произведение двух целых чисел >1, хотя и знаем, что такое разложение существует (尸九 F^ 尸 13 и Fu).
Начнем с наибольшего из известных составных чисел Ферма, т. е. с числа 尸 194* Оно имеет более чем 10582 цифр, и поэтому все их невозможно выписать. Однако, как уже было сказано ранее (§ 8), мы знаем наименьший простой делитель этого числа: т = 5 • 21947 + 1. Напрашиваются здесь два вопроса: 1) как найден этот делитель и 2) как можно убедиться, что число 也 имеющее 587 цифр, является делителем числа F1945, все цифры которого невозможно выписать.
Мы здесь, очевидно» не будем ни производить деления числа 尸 1945 на число /и, ни находить частное от этого деления. Совершенно иным путем мы убедимся, или, скорее всего, выясним, как можно убедиться в том, что число 尸 1945 при делении на т дает в остатке нуль.
Обозначим для целого числа t через t остаток от деления t на т. Из определения числа Г^ледует, что для каждого целого числа t будет m\t ——t Определим теперь последовательность г^ (月=1, 2, ...) посредством условий —
尸i = 22, 〃+1 =理 для k—1,2,... (1) Докажем при помощи индукции, что
т\^ — rk для 々=1, 2,… (2)
Формула (2), очевидно, справедлива для 月=I, так как 2”一「1 = 0. Предположим, что она справедлива для некоторого натурального числа k. В таком случае, согласно (2), и подавно m\^+1 — rl. ^Учитывая же, что m\t—7 для £ =尸备 имеем 闵案一*• Затем находим /nj22*+i —г^. Следовательно, согласно (1). т\2^к+} — гк+ъ Итак, формула (2) доказана посредством индукции. Для k = 1945 имеем
词居945 —「1945— 1，
откуда следует, что число 尸心45 при делении на т дает такой же остаток, как и число 门945 + 1. Поэтому, чтобы исследовать, делится ли число 尸 1945 на т, достаточцо исследовать, делится ли на /п число /*1945 + 1. Осмыслим теперь, какие действия нужно будет выполнить, чтобы подсчитать число к©. Из формул ⑴ следует, что числа 「2,尸3, •…как остатки от деления на т все будут меньше 也 так что каждое нз них имеет не более ч^м 587 цифр. Таким образом, из формул (1) вытекает, что для вычисления числа 「1945 необходимо осуществить 1944 возвышений в квадрат чисел, имеющих не более чем 587 цифр, и столько же делений этих квадратов (следовательно, чисел, имеющих не более чем 1175 цифр) на число ш, имеющее 587 цифр. Это ——действия, которые современные электронные машины в состоянии выполнить. Таким путем было подтверждено, что число 尸1945 делится на т == 5k 21947 + 1, а так как 尸МьАт, что легко можно проверить, то заключаем, что число 尸 1945 является составным.
Перейдем теперь к вопросу, как молено найти простой делитель m числа Л945. Известна теорема, согласно которой каждый натуральный делитель числа Fn должен иметь вид 2爲+2月 + 1, где k — целое неотрицательное число. Для п = 1945 отсюда следует, что делителями числа F1945 могут быть только числа, принадлежащие арифметической прогрессии 21947^ + 1, где 也=0, 1， 2, ... Для 月=0 мы получаем тривиальный делитель 1. Для k = 1 число 2n+2+ I = 21947 + 1 не является простым, так как, очевидно, делится на 3. Для 月=2 число 2n+2.2 + 1 = 21948 + 1 = (24)487 + j делится на 24 + 1 и, следовательно, не является простым. Для 月=3 число 2П+2 • 3 + 1 = 21947-3 + 1 является составным, делящимся на 5. В самом деле, 5|24— 1, откуда 5121944 — 1. Умножив правую часть последней формулы на 23*3, найдем, что 5121947-3 — 24, откуда также 5|21947- 3 + 1. Для 月=4 число 2П+2 • 4 + 1 = 21949 + 1 делится на 3, следовательно, является составным.
Таким образом, разыскивая простой делитель числа 尸 1945, м.ы должны делить его на 21947- 5 + 1 = т. Как уже отмечалось, деление выполняется без остатка, и так как т — наименьшее целое число >1, являющееся Делителем числа 尸245, то иг ——число простое.
Подобным образом можно исследовать другие числа Ферма. Исследование десятизначного числа 尸5, относительно которого Ферма был убежден, что оно является простым, выполняется весьма просто. Делители числа 尸5, как мы знаем, должны быть вида 2?・& + 1* или 128月 + L Для ^ = 1 мы получаем число 129, делящееся иа 3, и следовательно, составное; для А = 2 получаем простое число 257, которое не является делителем числа 尸5, в чем легко можно убедиться непосредственным делением. Для 月=3 мн получаем число 385, делящееся на 5 и, стало быть, составное. Для 々=4 получаем число 513 = 29 + 1, делящееся на 3 и, следовательно, также составное. (Иначе, число 232 = 416 — и (3 丄 I)】，=(5— 1)16 при делении и на 3, и на 5 дает в остатке 1, а значит, число 尸5 дает в остатке 2, т. е. число 尸5 ие делится ни на 3, ни на 5 и поэтому не делится также ни на одно из чисел 129, 385 и 513.) Для 月=5 получаем простое число 641, относительно которого непосредственным делением легко Можно убедиться, что оно является делителем числа 户5・ Таким образом, только при помощи двух делений мы убеждаемся, что 641 является наименьшим простым делителем числа 尸5.
Разделив число & 二 4 294 967 Й7 на 641, мы получим в частном 6700417. Делители этого числа, будучи делителями числа 尸5, должны быть вида 2?4 + I. Если это число составное, то .оно имеет простой делитель, не больший, чем корень квадратный из него, и, значит, <2600. Таким образом, для k мы имеем здесь неравенство 128月 + 1 < 2600, откуда k < 21, а с другой стороны, мы знаем, что должно быть й > 4, ибо наименьшим простым делителем числа 尸5 является 641. Таким путем при помощи немногих делений подтверждено, что число 6 700417 является простым, и, следовательно, получена разложение числа 尸$ в произведение двух различных простых сомножителей.
Для числа 尸6 найден делитель 28 • 1071 + 1 и, таким образом, подтверждено, что оно является составным.
Разыскать простой делитель числа Fn среди чисел арифметической прогрессии 2n+?月 + 1 практически возможно только в том случае, если число 尸九 обладает не слишком большим простым делителем. В противном случае, подставляя вместо 内 даже очень много последовательных натуральных чисел, мы не натолкнемся на 68
такой делитель. Это имеет место, например, для чисел h и 户& из которых первое содержит 39, а второе 78 цифр. Мы не знаем ни одного простого делителя этих чисел, а также ни одного разложения их в произведения двух натуральных чисел, ббЛьших единицы. Однако Дж. К. Морхед в 1905 г. доказал, что число Fi является составным, а в 1909 г. он же и А. Е. Вестерн доказали, что число Fe также является составным. Доказательство основывалось иа следующей теореме.
Теорема 2/. Если число Fn является простым, то число 322"т + J делится на Fn・
Докажем вначале следующее предложение.
力£附附@・ Если А есть целое неотрицательное число и если число р = 12^ + 5 является простым, то число 3做+2 + 1 делится на р.
Доказательство. Лемма, очевидно, справедлива для 月=" поэтому далее мы можем считать, что k является числом натуральным. Пусть р = 12色 + 5. Возьмем произведение первых 6^ + 2 натуральных чисел, делящихся на 3, и разобьем сомножители этого произведения на три группы, отнеся к первой группе первые 2月 сомножителей, ко второй — следующие 2月 + 1 сомножителей и к третьей — остальные 2& + 1 сомножителей.
Сомножители первой группы дают произведение 3 • 6 • 9 …6А.
Сомножители второй группы, еслц записать их в по* рядке убывания, дают произведение
（12*+3）， 12й，（12Л —3）…（燄+6）（6论 + 3）,которое, учитывая, что р =» 12盍 + 5, можно написать в виде（0一2）5 一 5）（p一8）..."一伊+ 2）］.
Так как число сомножителей здесь нечетное （2月 + 1）, то последнее произведение после развертывания и объединения слагаемых, делящихся на р, даст нам число р〃—2-5-8 ・・• （6fe 4- 2）, где и есть некоторое целое число.
Сомножители третьей группы дают произведение （12*+6）（1泌+9）（12论+12）（18* + 6） =
= 3+1）（Р+4）0 + 7）・.・。+6々+1）=
=川 + 1 • 4 • 7 •・・（6尼 + 1）,
где о — натуральное число.
Таким образом, имеем 3-6-9 …（18^ + 6） = 3* •6*9 …6论• [ри — 2• 5 • 8 …（6月 + 2）][ри + 1-4-7 •… .. . （6月十1）] = p閲一1 • 2，3，4。5•6…（6月+ 1），（6论+ + 2） — pw — （6月 + 2） !, где w ——целое число.
Hq 3 ・ 6 ・ 9 •・• （18月 + 6） = （6月 + 2）!36ft+2. Отсюда мы заключаем, что число pw делится на （6月 + 2）!, следовательно, /?5= （6也 + 2）匕 где f есть целое число. Но 66 + 2 V 12月 + 5 = р, н поэтому число （6月 + 2）! не делится на р. Поскольку же произведение （6月 + 2）!£ делится на р, то t должно делиться на р, / = ps, откуда 5 = （6月 + 2）!s, где s есть целое число. Таким образом, имеем 36ft+2 = ps — 1, откуда следует, что число 36*+?十 + 1 делится на р, что и требовалось доказать.
Перейдем теперь к доказательству теоремы 21.
Доказательство. Пусть п есть некоторое натуральное число. Тогда имеем 2П = 2/п, где т — натуральное число,尸階——1 = 4^, откуда следует, что число гп — 5 делится на 4. С другой стороны, имеем Fn ——1 = =4m = （3 + l）m = 3^ 4- 1, гле t — натуральное число. Отсюда Fn——5 = 3（f——1）, так что число Fn ——5, делясь на 4, оказывается делящимся и на 3, следовательно, это число делится на 12, и поэтому Fn = 12月 + 5, где й —— целое число. Таким образрм, согласно нашей лемме, если число 尸п простое, то число Зб*+?+1=3㈡ 7）/2 + + 1 = 322"т+1 делится на 匕.
Итак, теорема 21 доказана. Заметим попутно （хотя далее это нам и не понадобятся）, что можно доказать и теорему, обратную теореме 21.
Воспользуемся теперь теоремой 21 для доказательства того, что число 尸7 является составным. Для этой цели достаточно показать, что число 3” + 1 не делится на число 尸7 = 340 282 366 920 938 463 463 374 607 431768 211 457.
Значит, достаточно вычислить остаток от деления числа 32必’ на 尸九 Число 32哪 столь велико, Нто мы не можем выписать все его цифры, однако, чтобы подсчитать остаток, который оно дает при делении на F?、можно поступить следующим образом. Число 3屮 имеет 61 цифру, следовательно, его мы можем написать и подсчитать остаток г, который получается при делении этого числа на F^ （теперь это уже нетрудно сделать, если прибегнуть к помощи электронной вычислительной машины, но для Морхеда в 1905 г. это было очень трудно, хотя
и возможно). Остаток 尸丄 от деления 4иСла г2 ^ число 尸7 есть, очевидно, остаток от деления числа З28 иа число 尸7. Подобным же образом остаток г? от деления числа ri на число Fj есть остаток от деления числа З29 на 户7, Продолжая этот процесс далее, дойдем до остатка 尸侬 от деления числа 3* на F?. Таким путем найдем, что г 120 # 尸7 — 1, откуда следует, что число 3炉"+ 1 не делится на 尸7 и, значит, согласно теореме 21, Нисло 尸7 не является простым.
Аналогичным образом убеждаемся, 4to и число 尸8 не является простым. Для каждого же из чисел 不制(孔= =9, 10, 11 и 12), которые являются составными, мы знаем их простые делители, именно: '
2®37+"爲，2% 11131 + 1 呼°, 213・39+“Е»2M・7+Н%・
На основании теоремы 21, при помощи электронных вычислительных машин доказано, что 戶⑶ имеющёе 2467 цифр, и 尸и, имеющее 4933 цифры, являются числами составными. Никаких простых делителей зТих ^и- сел мы не знаем. '
Доказано, что числа 尸 15 и 尸 16 также составные, причем найдены их простые делителе: 2“「573 十 1|户 15, 218 ・ 315。+ 1|F16.
Число 尸 17 имеет более 30 тысяч цифр. Существующие же в настоящее время вычислительные машины не в состоянии выполнять десятки тысяч делений чисел, имеющих несколько десятков тысяч цифр, на числа, имеющие более 30 тысяч цифр. Таким образом, мыг пока все еще лишены возможности применить теорему 21 к исследованию чисел Гп и Fi9.
В 1953 г. для числа FI6 был цайден наименьший простой делитель 218 • 3150 + 1 и тем самым была опровергнута гипотеза, согласно которой все числа бесконечной последовательности
2+i, 22Н-1, 2#+L 222"+1, ^Ч-!,
являются простыми (составное число 尸 16 ——пятый член этой последовательности). Мы не знаем, однако, имеется ли в этой последовательности бесконечно много простых чисел, а также имеется ли в ней бесконечно много составных чисел.
Заметим, что ни одно из чисел 22 +1 + 1, где п — натуральное, не является простым, так как оно больше 3 и делится на 3.
Простые числа видов ля + 1,孤統十 1 и некоторых других видов
В связи с числами Ферма напрашивается вопрос, сколько существует простых чисел вида ип + 1, где л — натур'алыюе яисло. Предположим, что п ——натуральное и что число яп + 1 является простым. Каждое нат^)аль- ное и есть, как известно, число вида и = 2ftт, где Л —— целое число》0, a m — нечетное. Если бы m оказалось числом, большим единицы, то число пп + 1 = =(n2*)m + 1 было бы >n2* + 1 и делящимся на 犷 + 1 и, следовательно, было бы составным. Таким образом, должно быть ffi = 1, а значит, /г = 2*.
Если 左 二 0, то и = 1, и число ип + 1 ~ 2 является простым. Если же й > 0, то й = 2$ где г есть целое число 》D, a s — нечетное. Если бы было s > 1, то чис- ЛО ив+1= 22& + 1 =(2“『+ 1 как число, большее чем 2? *+ 1 и делящееся на это число, было бы составным. Таким образом, должно быть s= U следовательно, 论干2，п = 2^ и, значит, дл4- 1 = ^'^ +1=2"” +
Итак, число пп + 1, где п — натуральное число >1, тогда и только тогда является простым, когда % = 2”， где г — целое число》0, н 尸「+2r есть простое число.'
Для г = 0, так как число 尸i = 5 есть простое, мы получаем простое число 22 + 1 = 5. Для г = 1, так как число 尸з = 257 есть простое, получаем простое число 4* + 1 = 257. Для г = 2, так как Г6, как известно, есть число составное, делящееся на 28 • 1071 + 1, мы не получим простого числа. Для г = 3 мы также не получим простого числа, ибо 尸口 является числом составным, делящимся на 213 • 39 + 1. Таким образом, если кроме чисел 2, 5 и 257 существует еще простое число вида nn + L то оно должно быть》尸20 > 2220 > 2成 > 1031о5> т.匕 должно быть числом, имеющим более чем триста тысяч цифр.
• Следовательно, среди чисел вида ип + 1 (где и — натуральное число), имеющих не более чем трйста тысяч цифр, содержится только трн простых числа: I1 + 廿 1 = 2, 22 + 1 = 5 н 4《+ I = 257.
Принимая это во внимание, можно рискнуть высказать гипотезу о том, что не существует простых чисел айда ип + 1, где п — натуральное число, кроме трех: 2, 5 н 257. Следует, однако, заметить, что из этой гипотезы вытекало бы, что существует бесконечна много чисел Ферма, являющихся составными: таковыми были бы числа 户汁2「для г = 4, 5, 6,，… т. е. числа 尸2% 尸з% 尸70,尸 135,艮264,尸521,尸期4, •… Ни Об ОДНОМ ИЗ ЭТИХ ЧИ- сел, однако, до сих пор не доказано, что оно является
составным.
Рассмотрим теперь, что известно о простых числах вида плЛ4~ I• Имеем 1"+ 1 =2, 222-}- 1 =^ 17.Легко доказать, что если число 九也孤 十 1, где и — натуральное число > 1, является простым, то при некотором целом 尸》0 должно быть п — ^9 следовательно, /1几”+1 =
-2门寸
Для г = 0 мы получаем простое число 尸2 = 17, для г = 1 — число 尸9, о котором известно, что оно является составным, делящимся на 21® • 37 + 1. Для г = 2 получаем число 尸66, которое, как легко можно доказать, имеет более чем 1018 цифр. Отсюда следует, что
Среди чисел, имеющих не более чем миллиард миллиардов цифр, существует только два простых числа вида 孔也厶 + 1, где п — натуральное число, именно 2 и 17.
Рассмотрим также, какие из чисел вида п*2п + 1, где п = 1, 2, 3являются простыми (это так называемые числа Каллена). Кроме числа 3 (для /г = 1), мы знаем еще только одно такое простое число для п = 141. Вопрос, сколько имеется таких про
стых чисел, остается открытым.
Легко доказать, что не существует других простых чисел вида 2也 + 1, кроме простых чисел Ферма. Действительно, если 几=2『гп, где m — нечетное число >1» то число 2厶+ 1 nQ27n + 1 делится на меиьшее число 2^+ 1 > 1 и, следовательно, является составным. Из простых чисел вида 2n + 1, где л = 1,2,..., мы знаем, таким образом, только пять, именно для n = 1, 2, 4, 8, 16*
наименьшее же число этого вида, о котором мы не знаем, простое оно или нет, есть число 28192 + 1. Следовательно, мы знаем также только четыре простых числа вида 2,2rt + 1, где 及—натуральное число, йменнд для п = 1, 3, 7 и 15. Зато мы знаем 19 простых чисел вида 3・2九+ 1, именно для л « 1, 2, 5, 6, 8, 12, 18, 30, 36, 41„ 66, 189, 201, 209, 276, 353, 408, 438, 534. Простых чисел вида 4-2п + 1, где 打=1, 2，•…мы знаем только три: для 4 = 2, 6 н 14. Простых же чисел вида 5- 2W + 1, где м = i, 2 ..мы знаем 12: для м = 1. 3, 7, 13, 15, 25, 39/ 55, 75, 85, 127, 1947. ，
Длй каждого натурального числа А <： 100, за исключением 笈=47 н 月=94, мы знаем по крайней мере одно натуральное число п такое, что число 左• 2n + 1 является прЬстнм. Однако можно доказать, что существует бесконечно много таких натуральных чисел 加 для которых каждое из чисел А • 2П 4- 1 (л « 1, 2, ...) является составным. ,
♦ Займемся теперь простыми числами вида 2巾 + 2n + + J, где m и n — натуральные числа, т> п. Такими числами являются, например, 22 + 2 Ч- 1 = 7, 23 + 2 + + 1 - llt 2а + 22 + 1 - 13, 24 + 2 ч- 1 = 19.
Неизвестно, существует ли бесконечное множество таких простыл чисел. Зато легко доказать一уто существует бесконечно много составных чисел указанного вада. Это вытекает, например, тотчас же из равенства 22^ 十 2n+1 + 1 = (2n + 1)2 для п = 2, 3……，либо из замечания, что для 左=1, 2,…число 2^+1 + 2+1 всегда делится на 5, число же 2?卜 + 22г + 1 при натуральных & и Z всегда делится на 3. Имеем также разложение 24* + 22fe + 1 ~ (22А + 2ft + 1) (2* — 2* + 1).
А. Рнхнер установил, что для п < 24 числа 2n + 3 являются простыми только для м = 1, 2, 3, 4, 6, 7, 12, 15, 16, 18. Легко доказать, что среди чисел 2"* 十 3 имеется бесконечно много составных, а именно числа 22“м+"+з дЛя 左=0, 1, 2, • •. все делятся на 19. Числа же 2*"i + 3 для 也=0, 1, 2, .. - все делятся на 7«
Заметим также, что 1312** — 3 для 4=1, 2, 3, следовательно, и каждое из чисел
2222 —3, 22必一3,… ,'
делится на 13 и, значит, является составным.
74
Мы не знаем, имеется ли среди чисел
2 + 3, 22 + 3, 222+3, 222"+3, ...
только конечное число простых. Зато легко можно доказать, что среди чисел
222+5, 22"+5,…
нет ни одного простого, так как каждое из этих чисел делится на 7. Действительно, для натуральных k число 2?h = (3 + 1)卜 при делении на 3 дает в остатке 1, следовательно, 2淤=3f + 1, где f — натуральное число. Отсюда 22* + 5 = 23/+I + 5 = (7 + 1)' * 2 + 5> что, очевидно, делится на 7.
Неизвестно, существует ли такое натуральное число Л, для которого имеется бесконечно много простых чисел вида 2" + 2"+ ・・・ +2，+1, где 力,п& суть натуральные числа.
Мы не знаем также, существует ли бесконечно много простых чисел вида 2П + п2, где п — натуральное число. Четырьмя наименьшими такими простыми числами являются 3 = 21 + I2,17 = 23 + З2,593 = 2§ + 92 н 32 993 = =2】5 + 152. .
Как заметил А. Монковский, существует только одно простое число, именно число 5, вида 4П + п4, где 九一 натуральное. В самом деле» если п > 1, то п не может быть числом четным. Пусть 九=2左+ 1, где k — натуральное. Но тогда 4П + п4 = 4(2ft)4 + 公=(2 • 2 歎一 —2k+ln + 紋)(2 • 2站 + 2八+切 + 献)есть число составное.
А. Шинцель доказал, что для всякого натурального числа а, где 2《а《227, существует по крайней мере одно натуральное число п< 15 такое, что число а?" + 1 является составным. Если бы, опираясь на этот факт» мы рискнули высказать гипотезу, что для всякого на・ турального а > 1 существует по крайней мере одно на~ туральное п такое, что число а?" + 1 оказывается со^ ставным, то из этой гипотезы вытекало бы существование бесконечного множества составных чисел Ферма, ибо для0= 2m(где 月=1, 2, ...)имеем 必"+1 =忆+电. (Заметим, что для а = 221945 эту гипотезу еще не удалось подтвердить). —
Легко доказать, что существует бесконечное множество натуральных чисел а, для которых все числа *+ + 1, где n ™ 1, 2, ...» являются составными. Таковы, например, все числа а =匕^, где 6 — натуральное число > 1, a m — нечетное число >1.
С другой стороны, мы не знаем ни одного натурального числа а > 1, для которого мы могли бы доказать, что среди чисел а2" + 1(п = 1, 2, ...) существует бес- конечно много простых.，
Из гипотезы Шин целя (о которой речь будет вдти в § 30) вытекает, что для всякого натурального числа /л существует такое натуральное число а > 1, что все т чисел а?" + 1, где 打=1, 2т, являются простыми. Для m = 4 можно взять а = 2. Но трудно было бы найти такое число а > 1 для m = 5.
Три ошибочных теоремы Ферма
П. Ферма в своем письме к Мерсенну от 1641 г. высказал следующие три теоремы:
Ни одно из простых чисел вида 12А + 1 не является делителем ни одного аз чисел айда 3n + 1.
Ни одно из простых чисел вида 1% + 1 не яв~ ляется делителем ни одного из чисел вида 5" + L
Ни одно из простых чисел вида 10左一1 не является делителем ни одного из чисел вида 5^+1，
Доказано, что ни одна из этих трех теорем не является справедливой. Первая потому, что, например» 61 |35Ч-L 241 [З^ + Ъ вторая потому, что 521|55+1, третья потому, что 29|57 + 1. Для каждой из этих трех теорем, как доказал А. Шинцель, существует бесконечно много простых чисел, для которых они неверны.
Таким образом, здесь положение несколько иное по сравнению с теоремой Ферма о том, что каждое из чисел 2?"十 1 (п = 1, 2, ..J является простым, где мы зиаем только конечное число примеров, опровергающих эту теорему.
Кроме приведенных выше теорем, Ферма в указанном письме к Мерсенну сформулировал также теорему о том, что ни одно простое число вида 12月一1 не является делителей ни одного из чисел вида 3n + 1. Эта теорема позднее была доказана.
Числа Мерсенна
Числами Мерсен н а называются числа вида Мп = 2П — 1, где п — 1, 2, 3, ... Они представляют интерес с двух точек зрения. Во-первых, наибольшие известные нам простые числа являются числами Мерсенна и, во-вторых, при помощи чисел Мерсенна мы находим все так называемые совершённые четные числа. (Совершенным числом называется натуральное число, равное сумме всех своих натуральных делителей, меньших самого числа.) n-е число Мерсенна можно определить также как сумму п первых членов геометрической прогрессии 1, 2, 2г, 2* 2% •一
Таким образом, имеем
Mi = 1, Л12 = 3, М3 п 7,从4 = 15, Ms = 31, М6 = 63,№ = 127,…
Как легко доказать, если индекс п числа Мп есть число составное, то и число Мп является составным. В самом деле, если л = ab. где а и Ъ — натуральные числа >1, то 2a—1 > 1 и 2П — 1 ™ 2аЬ—1 > 2а—1, следовательно, число 2ab一 it делящееся на 2a—1, является составным.
Итак, если число МПч где п > 1, простое, то и число л должно быть простым, но ие обязательно наоборот, так как, например. Мп = 2" — 1 = 2047 = 23 • 8 9.
Доказано, что если р — простое число, то каждый натуральный делитель числа Мр должен быть вида 2初 + 1, где А — целое число > 0. Поэтому, например, делителями числа М” являются числа 22Л + 1, где 左=0, 1, 4 н 93.
Точно так же делители числа Mot = 2101 — 1 должны быть вида 202А + 1. К сожалению, до сих пор не найдено ни одного простого делителя числа AJ10i (очевидно, число 也 здесь очень велико), хотя другим путем (о чем речь будет идти позднее) доказано, что число М^ составное и является произведением двух различных простых-чисел.
Доказано, что если q есть простое число вида 8^ + 7, то дрИ”1 ・ Это позволило показать, что средн
чисел 附卩，где р — простое число, многие являются составными. Например,
471M2з，1671Mаз，263 |М[з“ 3591Ml79’ 3831Al回，479|Л1239. Высказано предположение (до сих пор не доказанное),, что таких составных чисел существует бесконечно много；
Мы знаем пока только 20 простых чисел Мерсенна. Это числа Aln для п = 2, 3# 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253 и 4423, Восемь наибольших простых чисел Мерсенна были найдены в последнее десятилетие при помощи электронных вычислительных машин.
Покажем теперь, каким путем было доказано, что эти весьма большие числа Мерсенна являются^ простыми. Это стало возможным благодаря следующей теореме, доказанной ранее.
Теорема Люка—Д. X. Лемера. Число MPf где р 一 простое нечетное wcao, тогда 〃 только тогда есть простое, когда Мр является делителем (р— 1)-го члена последовательности 口九(n= 1, 2,...), определенной условиями: ■
% = 4, %+1 =吟—2 для /1=1,2,...
(стало быть, последовательности, первыми членами которой являются числа 4, 14, 194, 37634,...).
Легко доказать^ что М^ир-\ тогда и только тогда, когда Мр является делителем (р — 1)-го члена последовательности гп(^ = L 2, .. .)* зависящей от Мр и определенной условиями: Г[ = 4, Гп+\ является, остатком оГ деления числа 吟一2 на Мр.
Таким образом, при доказательстве того, чта число Мр есть простое или составное, нам приходится иметь дело только с возвышением в квадрат и последующим^ делением на Мр чисел, меньших чем Мр. В частности, для доказательства того, что число М101, имеющее 31 цифру, явлйется простым, нужно было бы убедиться в том, что Mioikioo- После выполнения необходимых здесь вычислений было установлено, что число гюо не делится на 而 1(н・ Следовательно, число MiOi составное.
Чтобы доказать, что число М3217, имеющее 969 цифр,у является простым, йужно. было установить, что 府3217Kз21б・ Для этого потребовалось произвести несколь^ ко тысяч возвышений в квадрат и затем делений на
Мз217 чисел, имеющих не более чем 969 цифр, что современные машины в состоянии выполнить *)■
Высказано предположение, что если число Мерсенна Мп является простым, то и число ММп является простым. Это справедливо для четырех наименьших простых чисел Мерсенна, но уже для пятого простого числа М1з = 8191, как показал в 1953 г. Д. Ю. Уилер, это неверно: число ^мп = 28191 — 1 (имеющее 2466 цифр) является составным). Заметим, что ни одного простого делителя числа Мм^ мы не знаем.
В 1957 г. доказано, что хотя числа Мп и М19 простые, числа ^мХ1 и М^^ являются составными, делящимися соответственно на 1768(2"—1) + 1 и 120 ⑵ 9— 1) + 1.
Высказано также предположение (до сих пор не- опровергнутое), что числа 伙，⑺，饮，…，где go = 2, a qn^\ = 2% — 1 для n = 0, 1, 2, ..., являются все простыми. Это справедливо для чисел ^n, где п <4, но уже для 05, имеющего, как легко подсчитать, более чем 1037 цифр, мы не в состоянии решить вопрос, простое оно или составное.
Мы уже упоминали о связи чисел Мерсенна с совершенными четными числами. Еще Евклид указал следующий способ получения всех совершенных четных чисел. Вычисляем последовательно суммы членов геометрической прогрессии 1, 2, 22, 2, ... Если такая сумма окажется простым числом, то, умножив ее на последнее слагаемое, получим совершенное число.
С другой стороны, известно, что все совершенные четные числа являются числами вида 2卩一|川卩,где Мр есть простое число Мерсенна. (Справедливость этой теоремы была доказана лишь в XVIII в. Л. Эйлером.) Отсюда следует, что мы знаем столько совершенных четных чисел, сколько мы знаем простых чисел Мерсенна, т. е. в настоящее время 20 чисел.
Наименьшим совершенным числом является число 2М2 ~ 6, наибольшим известным совершенным числом —число 24422(24423 — ]) Чисел совершенных нечетных мы не знаем. Известно только, что если они существуют, то являются весьма большими.
Упомянем еще об одной гипотезе, относящейся к числам Мерсенна. Ф. Якобчик высказал предположение» что если р — простое число, то число Мерсенна % не делится ни на один квадрат простого числа. А. Шинцель поставил вопрос, существует ли бесконечное множество чисел Мерсенна, являющихся произведениями различных простых чисел.
Простые числа
в различных бесконечных последовательностях
Вопрос, содержит ли данная бесконечная последовательность, определенная даже несложным способом, бесконечно много простых чисел, вообще говоря, весьма труден. Как мн уже говорили, мы не знаем, содержат ли последовательности п2 4- 1, м! + 1, л!——1, 2П + 1, 2П — 1 (для м = 1, 2, ...) бесконечно много простых чисел. Мы не знаем также, содержит ли бесконечное множество простых чисел последовательность 1, II, 111, 1111, ... Также обстоит дело и в случае так называемой последовательности Фибоначчи и» (п = L 2,...), определенной условиями
〃1 = 〃2 = 1, 〃升2 = Wn + 〃冗+1 (几=1, 2, 3,...).
Первыми членами этой последовательности являются числ з 〃] = 1, 〃2 = 1, 〃з = 2, 〃4 = 3, 〃5 = 5. 〃б = 8, 〃7 = 13, 〃8 = 21,... '
10 цифр. Можно доказать, что является простым, то и число п должно быть простым,10 цифр. Можно доказать, что является простым, то и число п должно быть простым,Доказано, что числа «п являются простыми для п = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47. Других простых чисел ип мы пока не знаем. Наибольшее известное простое число ип есть число щ? = 2 971215 073, имеющее если и =#4 и число un
10 цифр. Можно доказать, что является простым, то и число п должно быть простым,
10 цифр. Можно доказать, что является простым, то и число п должно быть простым,
37 • 113, 〃3i37 • 113, 〃3i1, 〃19 = 4181 =1, 〃19 = 4181 =обязательно наоборот, так как, например, …=1 346 269 ^= 557-2417.
37 • 113, 〃3i
37 • 113, 〃3i
1, 〃19 = 4181 =
1, 〃19 = 4181 =
Мы не знаем, имеется ли среди чисел 〃簞,где р — простое число, бесконечно много составных.
80
Рассмотрим также последовательность 七门(п =
2, ...), определенную условиями
U1 = 1,。2 = 3, и“+2 = и” + "а+1 (п = 1, 2,...),
первыми членами которой являются числа 1, 3, 4, 7, 11, 18,・ * • Числа Он являются простыми для п ~ 2, 4, 5, 7, 8, П, 13, 17, 19, 31, 37, 41, 47, 53, 6J, 71. Наиболь-
шее известное простое число у« есть число v7i = =688 846 502 588 399. Мы не знаем, существует ли бесконечно много простых ^исел и乳.
Укажем здесь еще одну последовательность, которой в последние годы занималось несколько математиков. При ее построении исходим из последовательности всех нечетных чисел: 1, 3, 5, 7, 9, П, 13, 15,….Положим 〃i = 1; наименьшее число последовательности, большее иь есть 3, его мы и примем за «2- Вычеркнем из нашей последовательности каждое третье число (т. е. числа, находящиеся на местах третьем, шестом, девятом и т. д.). Таким путем мы получим новую последовательность: 1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ... Наименьшее число этой последовательности, большее «2, есть 7, его мы и примем за 〃з・ Вычеркнув теперь из последней по
следовательности каждое седьмое число, получим по следсжательность 1, 3, 7, 9, 13, 15, 21, 25, 27, ... Наименьшее число этой последовательности, большее 以з* есть 9, его мы примем за 以《.Из полученной последовательности будем вычеркивать теперь каждое девятое число. Поступая так далее, получим бесконечную последовательность 〃ь 私2, ..., У которой членами, меньшими ста, будут числа: 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 9生
Числа нашей последежательноети названы счаст
ливыми. Мы не знаем, имеетет ли среди них бесконечно много простых. Подсчитано, что среди счастливых чисел, меиьших 98 600, имеется 715 простых чисел.
Решекие уравненкб в простых чнслах.
Мы знаем много простых уравнений (даже первой степей»), относительдо которых неизвестно, имеют ли они бесконечное мнажесгво решетий в простых числах.
81
Таково, например, уравнение х 4- у = z. Легко дока* зать, что вопрос, имеет ли это уравнение бесконечно' много решений в простых числах х, у, z, равносилен вопросу, существует ли бесконечно много пар простых чисел близнецов. В самом деле, если р, g н г — простое числа такие, что р + q =「* tg числа " н g, очевидно, не могут быть оба нечетными (так как тогда сумма их была бы числом четным >2 и, следовательно, составным). Следовательно, одно из чисел ряд, например число д, должно быть четным и потому равно 2. Но тогда числа р н 尸="+ 2 составили бы пару простых чисел близнецов. С другой стороны, если числа р и г = р + 2 составляют пару простых чисел близнецов, то числа х = =р, g = 2, z = p + 2 являются простыми и дают решение уравнения х 4- у = z.
Мы не знаем, имеет ли уравнение 2尤 + 1 = у или уравнение 2% — у= 1 бесконечно много решений в про* стых числах х, у (такое предположение высказано), хотя и известно много таких решений» Например, для уравнения 2х + 1 = у (х, у) = (2,5), (3,7), (5,11), (11, 23), для уравнения же 2х — 1 — у (х,у) = (2,3),(3,5), (7,13), (19,37).
Дж* Г. ван дер Корпут доказал, что уравнение 尤 + у + 1 = z имеет бесконечное множество решений в простых числах х, g, z (ср. стр. 19).
Доказано, что уравнение х -^ у = z + t имеет бесконечное множество решений в различных простых числах х,弘 z,厶 так же как и уравнение 炉 + 炉=/ 屮织 Например, 72 + 192 ^ 11? + 172. Легко доказать, что уравнение х2 + у2 + г2 = Р не имеет ни одного решения в простых числах х, у, z, f.
Мы не знаем, существует ли бесконечное множество прямоугольных треугольников таких, чтобы длины их сторон были натуральными числами, из которых два — простые. Можно доказать, что этот вопрос р-авносилен вопросу, имеет ли уравнение р? = 2g — 1 бесконечно много решений в простых числах р и д. Примерами таких треугольников являются треугольники со сторонами (3,4,5), (5,12,13), (11,60,61), (19,180,181), (29, 240,241), (61,1860,1861).
Легко находятся все решения уравнения х2-—2у2 = и 1 в простых числах х, у. В самом деле, если натуральные числа х, у удовлетворяют уравнению %’ = 2у3 +」
斗 1, то х, очевидно, число нечетное,充=2々+ 1, где k — целое число, откуда х2 = 4fea + 4区 + 1, а следовательно, у2 ж 2k(k + 1) и, стало быть, у есть число чет* ное. Поэтому, если у является простым числом, то у = =2, откуда следует, что наше уравнение имеет одно только решение в простых числах: х = 3, у = 2.
Мы не знаем, сколько решений в простых числах х, у имеет уравнение х2 — 2y2 = —L Такие решения известны, например, % = 7, у = 5 или х — 41, у = 29.
Легко доказать, что если я — натуральное число >1, то уравнение рп + qn = гп не имеет решений в простых числах р, % г.
До сих пор не доказано предположение Ферма, согласно которому если р — простое нечетное число, то уравнение 尤р + ур = z「 не имеет решений в натуральных числах х, у, 2. (Это доказано для простых нечетных чисел р < 4002.)
Магические квадраты, составленные из простых чисел
Магическим квадратом (в широком смыёле) с 九 строками мы называем таблицу, составленную из п2 различных натуральных чисел； выписанных в п строк (и столько жб столбцов), такую* что суммы чисел каждой строки, каждого столбца и чисел, находящихся на каждой из глав=ных диагоналей, одинаковы. Известны ма- гические квадраты с тремя и четырьмя строками^ составленные из одних простых чисел. Например, квадраты
1731739767307157107227127277257137347473736717317397673071571072271272772571373474737367
17
317
397
67
307
157
107
227
127
277
257
137
347
47
37
367
17
317
397
67
307
157
107
227
127
277
257
137
347
47
37
367
В первом из этих квадратов суммы, о которых идет ре曠ь, все равны 1077; во втором 一 798.
Высказано предположение, что для каждого натурального числа м〉3 существует бесконечно много магических квадратов (в широком смысле), составленных из 打2 различных простых чисел.
Несколько нерешенных задач, касающихся простых чисел
Мы не знаем, существует ли бесконечно много нар последовательных натуральных чисел, каждое из которых имеет только один простой делитель (как, например, пары 2 и 3, 3 и 4, 4 и 5, 7 и 8, 8 и 9, 16 и 17, 31 и 32). Нам известно только 26 таких пар, из которых наивысшей является пара 24423 — 1 и 24423 (ср. далее 6).
Зато можно доказать, что уравнение рт一g" = 1, где ри?——простые числа, а т н п ——натуральные числа >1, имеет только одно решение: р — 3, g = 2, т = =2/ = 3.
Мы не знаем, существует ли бесконечное множество троек последовательных натуральных чисел, каждое нз которых является произведением двух различных простых чисел. (Примером таком тройки может служить тройка чисел: 33 == 3 • 11, 34 = 2 • 17, 35 — 5-7, а также тройка: 93 = 3 * 31, 94 = 2 • 47, 95 = 5• 19.) Высказано предположение, что таких троек существует бесконечно много.
Мы не знаем, существует ли бесконечно много простых чисел р таких, что для каждого натурального п < р ——1 число 2п при делении на р дает остаток, отличный от 1. (Такими являются, например, простые числа 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83.) Высказано предположение, что таких простых чисел р существует бесконечно много.
Мы не знаем, из каждого ли натурального числа п^ 10 при изменении двух его цифр можно получить простое число. (Для двузначных чисел это очевидно. Для трехзначных чисел это вытекает, например, из того, что простыми являются числа 101, 211, 307, 401, 503, 601, 701, 809, 907.)
Мы не знаем, справедлива ли гипотеза А. Шин- деля, согласно которой для каждого вещественного числа 尤》117 существует по крайней мере одно простое число р, содержащееся между х и х +]Л^. Эту гипотезу А. Шинцель проверил для всех чисел х таких, что 117<х<2- 107.
Легко доказать, что среди любых шести последовательных натуральных чисел по крайней мере одно имеет хотя бы два различных простых делителя (так как всегда одно из них делится на 6 и, значит, имеет простыми делителями 2 и 3).
Можно также доказать, что среди каждых трех последовательных натуральных чисел >7 хотя бы одно имеет по крайней мере два различных простых делителя. Но мы не знаем, среди каждых ли двух достаточно больших последовательных натуральных чисел хотя бы одно имеет по крайней мере два различных простых делителя. Иными словами, мы не знаем, существует ли натуральное число /и такое, что для п》т хотя бы одно из натуральных чисел й и п + 1 имеет по крайней мере два различных простых делителя. Мы знаем только, что если такое т существует, то должно быть т》2《组3, йбо из чисел 24423 — 1 и 24423 каждое имеет только один простой делитель. Доказано, что если такое число m существует, то существует только конечное число простых чисел Ферма и только конечное число простых чисел Мерсенна.
Гипотеза А. Шинцеля
Многочлен от переменной х с целыми коэффициент та ми мы называем неприводимым, если он не является произведением двух многочленов с целыми коэффициентами, степени которых меньше степени рассматриваемого многочлена.
Относительно многочлена f(x) е целыми коэффициентами напрашивается вопрос, когда такой многочлен при натуральных значениях х дает бесконечно много простых чисел. Легко доказать, что необходимым условием этого является требование, чтобы многочлен был неприводимым. Однако такое условие не является достаточном, ибо, как легко доказать, многочлен х2 + х + 2
является неприводимым, но ни при одном натуральном значении х не дает простого числа： для каждого натурального х его значение есть число четное >2.
Легко также доказать, что кроме неприводимости многочлен f (х) должен удовлетворять еще следующему условию： не существует ни одного натурального числа > 1, которое являлось бы делителем числа f(x) при каждом целом значении х.
Являются ли эти условия достаточными для того, чтобы многочлен с целыми коэффициентами, где коэффициент при наивысшей степени х положителен, давал бесконечно много простых чисел для натуральных х? В прошлом веке В. Я. Буняковский высказал предположение, что это так. Из данной гипотезы сейчас же следует, что существует бесконечно много простых чисел вида х2 4- 1, где х — натуральное число. Из нее же следует также, что существует бесконечно много натуральных чисел х, для которых х2 4- х + 41 является числом простым.
Из гипотезы А. Шницеля, о которой речь идет ниже, следует, что для каждого натурального числа п существует бесконечно много натуральных чисел х, для которых все четыре числа *" + 1,炉"+ 3, х» + 7,尤严 + + 9 простые.
А. Шинцёль высказал следующую общую гипотезу Р. 、
Если s — натуральное число, f\(x), %(尤),•… &(尤)一 многочлены с целыми коэффициентами, имеющие при наивысших степенях х положительный коэффициент, неприводимые и удовлетворяющие следующему условию S; не существует натурального числа > 1, которое являлось бы делителем произведения f\(x)f2(x) ... f8(x) для каждого целого значения х, — то существует бесконечно много натуральных чисел х, для которых каждое из чисел fi(x), %仪)，…，AW является простым.
Пусть, в частности, 5^2, fi (х) =« х, %(尤)« х + 2fe, где 2А — данное натуральное четное число. Имеем здесь
力⑴力(1)=1 + 2比 Л(-1)Л(-1)«1-2Л.
Если бы существовало натуральное число d> 1 такое, что d历(幻/式尤)для каждого целого числа х, то должно было бы быть d|2& — 1 и d\2k + lft что невоз-
можно, ибо, как известно, два последовательных нечетных числа 2fe — 1 и 2fe + 1 не имеют ни одного общего делителя, большего единицы. Таким образом, условие S здесь выполнено, и из гипотезы Р следует, что существует бесконечно много натуральных чисел х таких, что числа Л (х) и ，2(尤)являются простыми, стало быть, 尤=р, х + 2h = q, где р и q — простые числа, откуда 2々=夕一р. Поэтому из гипотезы Р следует, что каждое натуральное четное число может быть представлено бесконечным числом способов в виде разности двух простых чисел. В частности, для А = 1 отсюда следует существование бесконечного множества пар простых чисел близнецов.
Из гипотезы Р А. Шинцеля можно вывести еще много других теорем о простых числах, которые до сих пор не доказаны.
ИМЕННОЙ УКАЗАТЕЛЬ
Адамар (Hadamard J.) 29
Бейкер (Baker С. L) 16
Бертран (Bertrand J.) 14
Бнджер (Beeger N. G. W. Н) 38
Бреднхин Б. М. 34
Буняковский В. Я. 86
Вале Винс А. 65
Валле-Пуссен (Vallee Poussin de 1а Ch.) 29
Ван дер Корпут (Van der Cor- put J. G) 19, 82
Вестерн (Western A. E.) 44, 69
Вильсон (Wilson J.) 47—51
Виноградов И. M. 18
Вороной Г. Ф. 7
Гарди (Hardy G. Н.) 20
Гильбрайт (Gilbreath N. L.) 21, 22
Голашевский (Golaszewski S) 18
Голj бев В. А. 32, 35
Гольдбах Хр. 18, 19
ГоржелевскиЙ (Gorzelewski А.) 44
Грунбергер (Gruenberger F. J.) 16
Джуга (Giuga G.) 39
Дирихле (Dirichlet Р. G. Lele- une) 42
Каллен (Cullen J.) 73
Кантор (Cantor М.) 35
Крайчик (Kraitchik M) 27
Кулик (Kulik J. F.) 16
Лагранж (Lagrange J. L.) 45— 48, 63
Ландау (Landau E.) 30
Лейбниц (Leibniz G. W) 49, 50
Лемер Д. H. (Lehmer D N) 16
Лемер Д X. (Lehmer D H)
38, 44, 78, 79
Линник Ю. В 20
Литтлвуд (Littlewood J. E) 20, 41
Лич (Leech J ) 41
Лолер-Эрнст (Locher-Ernst L.)
29
Лузин H H. 8
Люка (Lucas) 78, 79
Мазуркевич (Mazurkiewicz S ) 8
Мерсенн (Mersenne M ) 76—80, 85
Мозер (Moser L ) 28, 49
МонковскиЙ (M@kowski A.) 19.
75.
Морхед (Morehead J. C.) 69, 70
Ньютон (Newton I.) 36
Полетти (Poletti L.) 16
Портер (Porter R. J.) 16
Робинзон (Robinson R. M^ 14
Pot (Roth К. E) 62
Серпинский (Sierpinski W.) 7—
9, 10, 14, 2 7, 29, 44, 45, 60
Скуля (Skula L.) 45
Туран (TurAn P.) 31
Уилер (Wheeler D. J.) 79
Ферма (Fermat P.) 35, 39, 40, 48, 49, 53, 63—66, 68, 72, 73, 75, 76, 83, 85
Ферье {Ferrier A) 32
Фибоначчи (Fibonacci L.) 80
Чебышев П Л. 14, 44
Човла (Chowla I.) 59
Шерк (Scherk H. J.) 30
Шницель (Schinzel A)' 9, 18, 31, 38, 44, 50, 75, 76, 80, 85—87 .
Эйлер Л. 33, 65, 79
Эратосфен 15
Эрдеш (Erdos P.) 31, 55
Якобчик (Jak6bczyk F.) 80
Янишевский (Janiszewski Z.) 8
Евклид 13, 79
88
Рихерт (Richert H E.) 28
Рихнер (Richner A.) 74
7 91011121315161821222728303234354043454751^^7 91011121315161821222728303234354043454751^^
7 91011121315161821222728303234354043454751^^
7 91011121315161821222728303234354043454751^^
ОГЛАВЛЕНИЕ
И. Г. Мельников. Вацлав Серпинский {к восьмидесятилетию со дня рождения)
От переводчика
Предисловие
Что такое простые числа?
Простые делители натуральных чисел
Сколько существует простых чисел?
Как можно найти все простые числа, меньшие данного чнсла?
Простые числа близнецы
Гипотеза Гольдбаха
Гипотеза Гильбрайта
Разложение натурального числа на простые сомножители ..
Какими цифрами могут начинаться и заканчиваться простые числа?
Число простых чисел, не превосходящих данное число .・
Некоторые свойства n-го по порядку простого числа .・.
Многочлены и простые числа
Арифметические прогрессии, образованные из простых чисел
Малая теорема Ферма
Доказательство теорем, согласно которым имеется беско- иечио много простых чисел каждого из видов 4在 + 1, 4АЦ-3 n 6在 + 5
Некоторые гипотезы относительно простых чисел
Теорема Лаграижа
Теорема Вильсона
Разложение простого числа на сумму двух квадратов ...
Разложение простого числа на разность двух квадратов и другие разложения
Квадратичные вычеты
Числа Ферма
Простые числа видов пя4-1,九"" + 1 и некоторых других видов
Три ошибочных теоремы Ферма
Числа Мерсенна
Простые числа в различных бесконечных последовательностях -
Решение уравнений в простых числах
Магические квадраты, составленные из простых чисел .・.
Несколько нерешенных задач, касающихся простых чисел
Гипотеза А. Шинцеля
5 267 Q В 34586 7 7 7 8 8 & & 8 85 267 Q В 34586 7 7 7 8 8 & & 8 8Именной указатель
5 267 Q В 3458
6 7 7 7 8 8 & & 8 8
5 267 Q В 3458
6 7 7 7 8 8 & & 8 8
Вацлав СерпинскийЧто мы знаем и чего не знаемо простых числах
几，Фиэматгиз, 1963 г., 92 стр. с илл.
Редактор Н. М・ Розенгауз
Техн, редактор А А. ЛукьяновКорректор Л. А Любович
Сдано в набор 9/V 1963 г.Подписано к пе-
чати 3/IX 1963 г. Бумага 84х10В>/32. Физ. печ. л. 2,875.Усл. печ. л. 4,72. Уч.>изд. ▲・ 4,71. Тираж 100 000 экз.Цена книги 14 коп. Заказ № 1390.
Государственное издательствофизико-математической литературыМосква, В-71, Ленинский проспект, 15
Типография № 2 ям. Ввг. Соколовой' УЦБ и ПП Леисовиархоза.
Леиингрвд. Измайловский пр., 29.
str. 4004
I) D. № Lehmer, Factor table for the first ten millions, Washington, Carnegie Institution, 190&.
2B
I) Для доказательства того, что число M3Q17 является простым, шведская электронная вычислительная машина БЕСК в 1957 г. затратила 5% часов.
■
НИН что мы
ЗНАЕМ ^Ш
♦ ■ R* 7，▲ ^^^^11HB■1aB ПРОСТЫХ ^^М ЧИСЛАХ
2 3 5 7 11 13 17 19 2：
兽35 71113 17 19 2：
23 5 711 13 1719 2：
В. СЕРПИНСКИЙВ. СЕРПИНСКИЙЧТО МЫ ЗНАЕМИ ЧЕГО НЕ ЗНАЕМО ПРОСТЫХ ЧИСЛАХЧТО МЫ ЗНАЕМИ ЧЕГО НЕ ЗНАЕМО ПРОСТЫХ ЧИСЛАХ
В. СЕРПИНСКИЙ
В. СЕРПИНСКИЙ