ВВЕДЕНИЕ

Натуральные числа — это числа, возникшие в процессе счета отдельных предметов, т. е. 1, 2, 3, . и т. д. Вся совокупность чисел, которые потенциально могут возникнуть в процессе счета, называется натуральным рядом. Как известно, натуральные числа можно складывать и умножать друг на друга. Результат этих операций также будет натуральным числом. С другой стороны, деление натуральных чисел друг на друга не всегда возможно. Эта операция часто приводит к другим числам — рациональным. В отличие от натуральных чисел, которые количе- чественно описывают совокупности отдельных предметов, рациональные числа возникают в процессе измерения непрерывно меняющихся величин, т. е. таких, как объем, температура, скорость и т. д. Аналогично делению не всегда возможно, оставаясь в пределах натурального ряда, извлечь квадратный, кубический и другие корни из натурального числа. Например, ₁/’2 — число иррациональное. Извлечение корней из натуральных чисел становится возможным после добавления к рациональным числам всех иррациональных, т. е. на множестве вещественных чисел. С другой стороны, решение некоторых задач в вещественных числах не всегда приемлемо. Так, например, количество зубцов шестеренок должно быть натуральным числом. Еще Гюйгенс, проектируя различные часовые механизмы, в частности модель Солнечной системы, занимался проблемой нахождения оптимального числа зубцов на колесах для того, чтобы точность механизмов была максимальной при возможно меньшем количестве деталей. Для решения этой задачи Гюйгенс привлек так называемые цепные (непрерывные) дроби, тесно связанные с рядом разделов теории натуральных чисел (некоторые гипотезы, касающиеся цепных дробей, эквивалентны гипотезе Римана о нулях дзета-функции Римана (см. гл. III)). Изучением вопросов, возникающих при решении уравнений в натуральных числах, занимается теория чисел (другое, более старое, название — арифметика).

Например, в арифметике изучаются вопросы типа: для каких натуральных чисел п уравнение п = х² + у² имеет решение в натуральных же числах? Или другой вопрос: насколько большим по сравнению с п может быть количество его делителей, т. е. количество таких d, кратным которых является число п?

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

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

Известно, что в современной математике, исходя из натурального ряда, строят рациональные, затем вещественные, комплексные числа, функции, геометрические объекты и т. д. В дальнейшем, хотя нам и придется использовать некоторые сведения из теории функций, все они носят чисто вспомогательный характер. Наш интерес будет сосредоточен на вопросах, связанных со структурными свойствами натуральных и простых чисел.

Остановимся вкратце на истории изучения свойств простых чисел.

Трудно ответить на вопрос о том, кто первый стал изучать простые числа. Во всяком случае как древних египтян, так и древних вавилонян не интересовала логическая сторона их исчислений. По сохранившимся древнеегипетским источникам геометрия для египтян была собранием опытных фактов. Их вполне устраивали такие формулы, как, например, формула для площади треугольника: S = = ab/2, где а — меньшая, а b — средняя по величине стороны треугольника. Вероятно, точность этой формулы была достаточна и для фараона, и для чиновников в течение тысячелетий. Свидетельства древних греков подтверждают это. Например, Фалес Милетский в VI в. до н. э. удивил египтян тем, что, используя соображения подобия, по длине тени от пирамиды и тени от палки вычислил высоту пирамиды. В таком же положении, как и египтяне, находились древние вавилоняне, которые были прекрасными вычислителями. Для нужд астрономии они составили весьма точные таблицы. Ими были составлены также таблицы для решения квадратных уравнений и даже некоторых кубических. Существует мнение *, что в некоторых случаях математическому мышлению вавилонян были присущи алгебраические черты. Подобно тому как современный алгебраист обозначает одной буквой сложный объект и оперирует с ним по определенным правилам до тех пор, пока не появится необходимость использовать его индивидуальные свойства, древние вавилоняне могли оперировать радикальным выражением, не конкретизируя его до тех пор, пока это было им выгодно. Тем не менее вряд ли они задумывались о природе чисел, вряд ли у них возникал вопрос о возможности вычислить точно значение корня квадратного из двух, или вопрос о том, можно ли в шестидесятеричной системе счисления (у вавилонян была именно эта система) точно поделить 19 на 29, получив при этом конечную шестидесятеричную дробь.

По-видимому, подобные вопросы впервые появились в Древней Греции в VI—V вв. до н. э. Несмотря на разнообразие взглядов на мир, разнообразие философских учений, несмотря на то, что дичайшие суеверия мирно соседствовали в сознании древних греков с вполне современным скептицизмом, в целом духовная жизнь Греции того времени характеризовалась желанием логически понять устройство мира. Само по себе это предполагает, что мир «устроен» разумно, т. е. познаваем нашим разумом. Такого рода взгляды оказались весьма плодотворными для развития математики.

О деятельности такого известного математика, как Пифагор, можно судить лишь по упоминаниям других античных авторов (деятельность же его была крайне разнообразна: математика, философия, пророчества, политическая деятельность, шарлатанство, путешествия и, наконец, по преданию, Пифагор был чемпионом Олимпийских игр по кулачному бою). Если отбросить фантастические истории, касающиеся Пифагора (вроде того, что однажды его видели одновременно в двух разных местах, или истории о том, что когда однажды он переходил речку, та вышла из берегов, восклицая: «Да здравствует Пифагор!»), то останется его тезис о том, что законы, управляющие миром, суть законы, управляющие натуральными числами, останутся его мистические взгляды на натуральные числа, останется открытие иррациональных чисел (несоизмеримость стороны квадрата с его диагональю), останется первая попытка понять мир музыки, останутся элементы гелиоцентрической системы. Впрочем, трудно понять, что из перечисленного действительно принадлежит Пифагору, а что принадлежит другим лицам, входившим в союз пифагорейцев. Для нас важно то, что именно в союзе пифагорейцев стали рассматриваться вопросы делимости чисел, выделялись простые числа, составные, совершенные (т. е. числа, сумма собственных делителей которых равна самому числу). В дальнейшем (III век до н. э.) простые числа и связанные с ними вопросы изучались Евклидом и Эратосфеном. Эратосфен предложил способ получения простых чисел («решето» Эратосфена), состоящий в том, что из натурального ряда последовательно вычеркиваются числа вида 2к, Зк, ., где к = 2, 3, 4, оставшиеся числа будут простыми. Сейчас трудно сказать, какие именно вопросы относительно простых чисел интересовали древних греков. Можно лишь предполагать, что Евклид мог интересоваться вопросом о бесконечности простых чисел вида 2^я — 1, так как «Начала» Евклида содержат как доказательство бесконечности числа простых чисел, так и доказательство теоремы о том, что число вида 2^я (2 ^Я+1 — 1) является совершенным в том случае, когда 2^Я+1 — 1 есть простое число. (Конечно или бесконечно число простых чисел вида 2^я — 1 неизвестно и по сей день.)

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

Ниже рассказывается о методах и достижениях математики нового времени в изучении простых чисел.

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

1. Если f (х) и g (х)— две вещественные функции и

g (х) > 0, то

f (*) = О (g (х))

означает, что при достаточно больших х ограничена некоторой постоянной.

Выражение f (х) = о (g (х)) означает,

—> 0 при х -> оо.

2. При х -> оо имеет место следующая величина

что f (x)/g (х) -> асимптотическая

еМ

формула:

где Ini I ±

ln/1 ±-Ц ^{= ±}— + 0(-V l X I X \х^г

1 \

— I — натуральный логарифм.

3. При oo ln^ax = О (xP), где аир — произвольные положительные числа.

4. Хотя там, где это может вызвать различные толкования, делаются соответствующие напоминания, удобно сразу договориться, что р, p_ft, pW всегда обозначают простые числа, 5, П — суммы и произведения, распространенные на простые числа.

5. С, с* Cj, всегда обозначают положительные постоянные в различных главах, вообще говоря, различные.

Глава L ЭЛЕМЕНТАРНЫЕ СВОЙСТВА ПРОСТЫХ ЧИСЕЛ

Как известно, добавлением к натуральным числам нуля и чисел, им противоположных, т. е. натуральных чисел со знаком минус, получаются целые числа. Целые числа можно складывать, вычитать и умножать друг на друга. В том случае, если результат деления целого числа п на целое число d — целое число, то d называется делителем п и краткая запись этой ситуации есть d\n. Очевидно, что для всякого целого числа п справедливо: 1 1л» —1 |п, п|п и —п[п.

Если п — натуральное число, п и не имеет других делителей, кроме ±1 и ±п, то п называется простым числом.

Хотя единица не имеет делителей, кроме ±1, по многим причинам ее удобно не считать простым числом.

Все натуральные числа, отличные от 1 и простых чисел, называются составными числами.

Роль простых чисел среди натуральных проясняется следующей теоремой.

Теорема 1. Всякое натуральное число п, большее 1, допускает представление в виде произведения простых чисел, т. е. п = р_х р₂ . рк, где р_х, р₂» •••> Р*—простые числа.

Доказательство. Если п—простое число, то теорема 1,

очевидно, верна. Если п — составное число, то по определению найдется хотя бы один его натуральный делитель, отличный от 1 и п. Каждый такой делитель d, меньше, чем и, поэтому их конечное число. Следовательно, из них можно выбрать наименьший по величине. Обозначим его через d_t. Покажем, что d_t — простое число. Действительно, если dj — составное число, то найдется натуральное число х, которое не равно ни 1, ни d_t и которое делит d_v Но тогда х строго меньше d_t и х делит п, т. е. является делителем, меньшим d_n что противоречит выбору d_v

Таким образом, — простое число и п = причем п_х строго меньше п и не равно единице. Если п_г — простое число, то теорема доказана. Если п_г — составное число, то рассмотрим его делители и повторим предыдущее рассуждение. Получим п = did₂n₂- Такую процедуру можно продолжить и далее. Поскольку получающиеся числа образуют строго убывающую последовательность, то процесс рано или поздно оборвется, т. е. на каком-то шаге получим: п = di d₂ . d_Kn_K, где п_к — простое число. По построению все d_lt d₂, ., d_K — простые числа, поэтому теорема 1 доказана.

Следствие. Всякое целое число п, не равное нулю, либо равно ±1, либо допускает представление в виде п = ьрг .р_к, где е = ±1 и pi, ., р_к — простые числа.

Теорема 1 показывает, что простые числа играют роль своего рода кирпичей, из которых умножением могут быть составлены все натуральные числа. Но теорема 1 ничего не говорит об однозначности такого представления. Возможны ли ситуации, когда одно и то же число по-разному составлено из простых чисел?

Ответ на этот вопрос дает теорема 2. (Теорема 2 не является банальным утверждением, так как есть числовые системы, во многом схожие с целыми числами, в которых утверждение теоремы 2 неверно.)

Теорема 2 (Основная теорема арифметики).

Пусть n> 1 и п = pi р₂ . р_к = <71 q₂ . q_m, где Pi . <7i ••• qm — простые числа, причем р_г < р₂ < р₃ .

< Рк, <71 < <7г < ••• <7т- Тогда т = k и Pj = qj для / =

К 2, ., т.

Замечание. Здесь и в дальнейшем запись n=p_tp₂. p^k означает, что если, например, k — 1 или k = 2, то п — р_г и п = р^р₂ соответственно.

2 ^т(р— 1) = C₀* + °(*)- p<x

Доказательства соотношений (61) следуют из выведенной нами ранее теоремы 18. Из этой теоремы следует, что

2 мх_;и,1)^о/ 2

—< п < Vx I ~~“Б < и <Vx I

(In х}& \(1пх)В /

= О (^Х(^^1ПХ)Л (In Ух - 1П -Ж + О (In In X) =

\ 1ПХ М ^г (\пх)^{в v}

^{= 0}(^_K7^(lnln^³ ) +

Поскольку

2 >= 2л (иУх+ 1; и, 1), то с помощью анало-

Р — \=uv^>x u^fx и,

гичных рассуждений получается оценка:

2 ^(тнтОпМ.

р— 1 = VU ' '

и < Vx

V < Vx

Тем самым доказан теорема.

Теорема 23. (Линник). При х->оо имеет место а симптотическая формула 2 * (Р ~ ') = V + ⁰ «> ^{где С}°~ ^нек°- торая постоянная, большая нуля.

ЗАКЛЮЧЕНИЕ

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

Например, несмотря на безусловные успехи математиков XX в. в аддитивных задачах с простыми числами, проблема Гольдбаха о представлении четного числа суммой двух простых чисел до сих пор не решена. (Утверждение, наиболее близкое по звучанию к формулировке проблемы Гольдбаха о представлении четных чисел, доказанное на сегодняшний день, заключается в том, что всякое достаточно большое четное число N представимо в виде Л^г=Р1+р₂^,Рз« где

Рг, Рз— простые. Это утверждение было совсем недавно доказано китайским математиком Ченем.)

К другим известным нерешенным задачам о простых числах относится так называемая проблема близнецов. Проблема близнецов заключается в выяснении вопроса о том, конечно или бесконечно множество простых чисел р, таких, что р+2 является также простым числом.

К нерешенным проблемам относится проблема, касающаяся представления простых чисел значениями целочисленных многочленов. Например, единственными многочленами, про которые известно, что множество значений, которые они принимают при целых значениях аргумента, содержит бесконечное множество простых чисел, являются линейные многочлены вида qx-H_t где q и I •— взаимно простые числа, <7=7^0. Уже про многочлен х²+1 неизвестно, конечное или бесконечное число раз его значения являются простыми числами. Перечисленные и множество других задач о простых числах ждут своего решения. Учитывая неослабевающий в течение 2500 лет интерес к простым числам, можно думать, что со временем каждая из этих проблем будет решена.

ЛИТЕРАТУРА

1. Виноградов И. М. Метод тригонометрических сумм в теории чисел. М., «Наука», 1971.

2. Виноградов И. М. Основы теории чисел. М., «Наука», 1972.

3. К а р а ц у б а А. А. Основы аналитической теории чисел. М., «Наука», 1975.

4. Пр ах а р К. Распределение простых чисел. М., «Мир», 1967.

5. Т р о с т Э. Простые числа. М., Физматгиз, 1959.