Книги по разным темам
Pages: | 1 | ... | 6 | 7 | 8 | 9 | 10 | ... | 76 | 1 1 2 2 r r Докажите это утверждение. В качестве следствия установите, что число всех делителей a (включая 1 и само a) равно произведению ( + 1)( + 1)... ( + 1).
1 2 r 50 ТЕОРИЯ ЧИСЕЛ гл. I Так, например, 144 = 24 имеет 5 3 делителей. Вот они: 1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144.
2. Распределение простых чисел. Можно составить список всех простых чисел, не превышающих какого-то данного числа N, следующим образом. Напишем подряд все натуральные числа от 2 до N, затем вычеркнем все числа, являющиеся кратными 2 (не считая самого числа 2), все числа, являющиеся кратными 3 (не считая 3), и т. д., пока не будут вычеркнуты все составные числа. Эта процедура, известная под названием решета Эратосфена, позволит выловить все простые числа в пределах от 2 до N. Усовершенствования этого метода мало-помалу привели к тому, что в настоящее время составлены вполне надежные таблицы простых чисел примерно до 10000000. Они предоставляют в наше распоряжение обширнейший эмпирический материал, позволяющий судить о распределении и свойствах простых чисел. Основываясь на этих таблицах, мы можем высказать ряд в высшей степени правдоподобных гипотез Ч совершенно так, как будто бы теория чисел была экспериментальной наукой. Часто доказательство этих гипотез оказывается необычайно затруднительным.
а. Формулы, дающие простые числа Были сделаны попытки найти элементарные арифметические формулы, которые давали бы только простые числа, хотя бы без требования, чтобы они давали все простые числа. Ферма высказал предположение (не выставляя его в качестве положительного утверждения), что все числа вида n F (n) = 22 + являются простыми. В самом деле, при n = 1, 2, 3, 4 мы получаем F (1) = 22 + 1 = 5, F (2) = 22 + 1 = 24 + 1 = 17, F (3) = 22 + 1 = 28 + 1 = 257, F (4) = 22 + 1 = 216 + 1 = Ч всё простые числа. Но в 1732 г. Эйлер разложил на множители число 22 + 1 = 641 6700417; таким образом, число F (5) Ч уже не простое.
Позднее среди этих чисел Ферма удалось обнаружить другие составные числа, причем ввиду непреодолимых трудностей, с которыми были связаны непосредственные пробы, в каждом случае были выработаны более глубокие теоретико-числовые методы. В настоящее время остается неизвестным даже то, дает ли формула Ферма бесконечное множество простых чисел.
з 1 ПРОСТЫЕ ЧИСЛА Вот другое простое и замечательное выражение, дающее много простых чисел:
f(n) = n2 - n + 41.
При n = 1, 2, 3,..., 40 f(n) есть простое число; но уже при n = простого числа не получается:
f(41) = 412.
Выражение n2 - 79n + дает простые числа до n = 79 включительно; при n = 80 получается составное число.
В итоге можно сказать, что поиски элементарных формул, дающих только простые числа, оказались тщетными. Еще менее обнадеживающей следует считать задачу нахождения такой формулы, которая давала бы только простые числа и притом все простые числа.
б. Простые числа в арифметических прогрессиях Если доказательство того, что в последовательности всех натуральных чисел n = 1, 2, 3, 4,... содержится бесконечное множество простых чисел, носит вполне элементарный характер, то следующий шаг в сторону таких последовательностей, как, например, 1, 4, 7, 10, 13,... или 3, 7, 11, 15, 19,..., или, вообще говоря, в сторону произвольной арифметической прогрессии a, a + d, a + 2d,..., a + nd,... (где a и d не имеют общих множителей), оказался связанным с гораздо б ольшими трудностями. Все наблюдения только подтверждали тот факт, что в каждой такой прогрессии содержится бесконечное число простых чисел, как и в простейшей из них 1, 2, 3,... Но понадобились величайшие усилия для того, чтобы доказать эту общую теорему. Успех был достигнут Лежёном Дирихле (1805Ц1859), одним из ведущих математиков прошлого столетия, который применил при доказательстве самые усовершенствованные средства математического анализа из известных в то время. Его замечательные работы в этой области даже для настоящего времени остаются непревзойденными; прошло около ста лет, но доказательства Дирихле все еще не упрощены настолько, чтобы они могли быть поняты теми, кто не овладел полностью техникой математического анализа и теорией функций.
Мы не будем здесь пытаться привести доказательство общей теоремы Дирихле, а ограничимся рассмотрением более легкой задачи: обобщим евклидово доказательство о существовании бесконечного множества простых чисел таким образом, чтобы оно охватило некоторые специальные прогрессии, например 4n + 3 или 6n + 5. Рассмотрим первую из этих прогрессий. Заметим прежде всего, что всякое простое число, большее 2, Ч непременно нечетное (иначе оно делилось бы на 2) 52 ТЕОРИЯ ЧИСЕЛ гл. I и, следовательно, имеет вид 4n + 1 или 4n + 3 (при целом n). Далее, произведение двух чисел вида 4n + 1 также есть число того же вида, так как (4a + 1)(4b + 1) = 16ab + 4a + 4b + 1 = 4(4ab + a + b) + 1.
Допустим теперь, что существует лишь конечное число простых чисел вида 4n + 3; обозначим их p1, p2,..., pn и рассмотрим число N = 4(p1p2... pn) - 1 = 4(p1... pn - 1) + 3.
Одно из двух: либо число N Ч простое, либо оно разлагается в произведение простых чисел, среди которых, однако, не может быть ни одного из чисел p1, p2,..., pn, так как эти числа делят N с остатком -1.
Заметим далее, что все множители, входящие в N, не могут быть вида 4n + 1, так как само N не этого вида, а мы видели, что произведение чисел вида 4n + 1 является числом того же вида. Итак, хоть один из множителей, входящих в N, должен быть вида 4n + 3, а это невозможно, так как ни одно из чисел p не входит множителем в N, а числами p все простые числа вида 4n + 3 по предположению исчерпываются. Таким образом, допуская, что существует лишь конечное число простых чисел вида 4n + 3, мы приходим к противоречию, и значит, таких чисел бесконечно много.
Упражнение. Докажите соответствующую теорему для прогрессии 6n + 5.
в. Теорема о распределении простых чисел В исследованиях, связанных с законом распределения простых чисел, решительный шаг был сделан тогда, когда математики отказались от тщетных попыток найти элементарную математическую формулу, которая давала бы все простые числа или же точное число простых чисел, содержащихся среди n первых натуральных чисел, и сосредоточили вместо того внимание на распределении в среднем простых чисел среди всех натуральных.
При всяком целом n обозначим через An число простых чисел среди чисел 1, 2, 3,..., n. Если мы выделим среди первых чисел натурального ряда 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19...
те, которые являются простыми, то не составит труда подсчитать ряд значений An:
A1 = 0, A2 = 1, A3 = A4 = 2, A5 = A6 = 3, A7 = A8 = A9 = A10 = 4, A11 = A12 = 5, A13 = A14 = A15 = A16 = 6, A17 = A18 = 7, A19 = 8 и т. д.
з 1 ПРОСТЫЕ ЧИСЛА Возьмем теперь какую-нибудь неограниченно возрастающую последовательность значений n, например n = 10, 102, 103, 104,... ;
тогда соответствующие значения An A10, A102, A103, A104,...
также будут возрастать безгранично (хотя и более медленно). Действительно, множество простых чисел, как мы уже знаем, бесконечно, и потому значения An рано или поздно станут больше любого назначенного числа. Плотность распределения простых чисел среди n первых чиAn сел натурального ряда дается отношением ; не представляет особого n An труда с помощью таблиц простых чисел подсчитать значения при n достаточно больших значениях n:
An n n 103 0,106 0,109 0,Последняя, скажем, из выписанных строчек в приведенной табличке дает вероятность того, что число, случайно выхваченное из 109 первых чисел натурального ряда, окажется простым: всего имеется 109 возможных выборов, из них A109 соответствуют простым числам.
Распределение отдельных простых чисел отличается чрезвычайно неправильным характером. Но эта неправильность в малом исчезает, если мы направим внимание к распределению в среднем, находящему An свое выражение в изменениях отношения при неограниченно растуn щем n. Простой закон, которому подчиняется поведение этого отношения, следует отнести к числу самых замечательных открытий, сделанных во всей математике. Для того чтобы сформулировать теорему о распределении простых чисел, к которой мы теперь подходим, необходимо предваритель- y но разъяснить, что такое натуральный логарифм числа n. Для этой цеxy ли возьмем в плоскости две взаимно перпендикулярные оси и рассмотрим геометрическое место таких точек на плоскости, для которых произведение расстояний x и y от двух осей x Рис. 5. Площадь заштрихованной области под гиперболой определя54 ТЕОРИЯ ЧИСЕЛ гл. I равно единице. В терминах координат x и y это геометрическое место есть равносторонняя гипербола, уравнение которой имеет вид xy = 1. Мы определим ln n как площадь (рис. 5) фигуры, ограниченной гиперболой и двумя вертикальными прямыми x = 1 и x = n. (Более детально логарифм и его свойства будут рассмотрены в главе VIII.) Чисто случайно, в связи с изучением таблицы An простых чисел, Гаусс заметил, что отношение приблизительно равn но и что точность этого приближения, по-видимому, улучшается при ln n возрастании n. Насколько удовлетворительно приближение, можно суAn дить по отношению :, значения которого при n = 1000, 1000000, n ln n 1000000000 показаны в следующей табличке:
An 1 An n :
n ln n n ln n 103 0,168 0,145 1,106 0,078498 0,072382 1,109 0,050847478 0,048254942 1,.....................................
Основываясь на такого рода эмпирической очевидности, Гаусс высказал An в качестве предположения, что отношение ласимптотически равn но. Смысл этого утверждения заключается в следующем: если ln n возьмем последовательность значений n, становящихся все больше и больше, например, 10, 102, 103, 104,...
(как мы делали и раньше), то отношение An :, n ln n вычисляемое для этих последовательно рассматриваемых значений n, будет становиться все более и более близким к числу 1, а именно, разность между указанным отношением и единицей будет делаться столь малой, сколь будет назначено, лишь бы только мы рассматривали достаточно большие значения n. Такого рода соотношение символически An 1 An выражается знаком : означает, что : при возрасn ln n n ln n тании n стремится к 1. Что знак не может быть заменен знаком обыкновенного равенства (=), ясно хотя бы из того факта, что An Ч n непременно целое число, тогда как не является таковым.
ln n з 1 ПРОСТЫЕ ЧИСЛА То обстоятельство, что распределение простых чисел хорошо описывается с помощью логарифмической функции, нельзя не признать поистине поразительным, так как здесь вступают в тесное соприкосновение два математических понятия, казалось бы не имеющие друг к другу никакого отношения.
Хотя схватить содержание высказанного Гауссом предположения не представляет особой трудности, однако его строгое математическое доказательство во времена Гаусса было за пределами возможностей математической науки. Для того чтобы доказать теорему о распределении простых чисел, говорящую лишь о самых элементарных математических понятиях, неизбежно нужно прибегнуть к самым мощным методам современной математики. Пришлось ждать почти сто лет, пока анализ получил достаточное развитие для того, чтобы Адамар (1896) в Париже и Валле-Пуссен (1896) в Лувэне смогли дать исчерпывающее доказательство теоремы о распределении простых чисел. Упрощения и важные дополнения были затем внесены Мангольдтом и Э. Ландау. Задолго до Адамара значительное продвижение в этой области было сделано Риманом (1826Ц1866) в его знаменитой работе, намечающей основные стратегические линии предстоящей атаки. Совсем недавно американский математик Норберт Винер сумел видоизменить доказательство таким образом, чтобы избежать применения комплексных чисел в узловых моментах проводимых рассуждений. Но все же доказательство теоремы о распределении простых чисел остается слишком сложным для того, чтобы его можно было предложить начинающему. Мы вернемся к этому вопросу на стр. 507 и следующих.
г. Две еще не решенные задачи о простых числах Если проблема распределения простых чисел (лв среднем) была разрешена удовлетворительно, то справедливость ряда других гипотез, эмпирически совершенно несомненная, все еще не доказана.
Сюда относится прежде всего знаменитая гипотеза Гольдбаха.
Гольдбах (1690Ц1764) сам по себе не оставил никакого следа в истории математики: он прославился только проблемой, которую предложил Эйлеру в письме, относящемся к 1742 г. Он обратил внимание на тот факт, что ему всегда удавалось представить любое четное число (кроме 2, которое само есть простое число) в виде суммы двух простых. Например, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5, 12 = 5 + 7, 14 = 7 + 7, 16 = 13 + 3, 18 = 11 + 7, 20 = 13 + 7,..., 48 = 29 + 19,..., 100 = 97 + и т. д.
Гольдбах спрашивал у Эйлера, может ли тот доказать, что такого рода представление возможно для всякого четного числа, или же, напротив, сможет указать пример, опровергающий такое предположение. Эйлер так и не дал ответа; не дал его никто и в дальнейшем.
56 ТЕОРИЯ ЧИСЕЛ гл. I Эмпирическая очевидность гипотезы Гольдбаха, как легко проверить, вполне убедительна. Источник же возникающих затруднений Ч в том, что понятие простого числа определяется в терминах умножения, тогда как сама проблема касается сложения. Вообще, находить связи между мультипликативными и аддитивными свойствами чисел очень трудно.
До недавнего времени доказательство гипотезы Гольдбаха казалось задачей совершенно неприступной. Сегодня дело обстоит уже не так.
Очень значительный успех, оказавшийся неожиданным и поразительным для всех специалистов по данному вопросу, был достигнут в 1931 г.
неизвестным в то время молодым русским математиком Шнирельманом (1905Ц1938), который доказал, что всякое целое положительное число может быть представлено в виде суммы не более чем 800 000 простых.
Хотя этот результат и производит несколько комическое впечатление (по сравнению с первоначально поставленной целью доказать гипотезу Гольдбаха), тем не менее он стал первым шагом в должном направлении. Доказательство Шнирельмана Ч прямое и носит конструктивный характер, хотя и не обеспечивает практического метода для представления произвольного целого числа в виде суммы простых. Еще позднее русский же математик Виноградов, пользуясь методами Харди, Литтлвуда и их поистине великого сотрудника по работе индуса Рамануджана, сумел понизить число слагаемых в формулировке Шнирельмана с 800000 до 4. Это уже гораздо ближе к решению проблемы Гольдбаха.
Но между результатами Шнирельмана и Виноградова имеется очень резкое различие более резкое, чем различие между числами 800000 и 4.
Pages: | 1 | ... | 6 | 7 | 8 | 9 | 10 | ... | 76 | Книги по разным темам