Книги по разным темам Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 76 |

С чисто логической точки зрения небезынтересно отметить то обстоятельство, что с помощью принципа наименьшего целого числа принцип математической индукции доказывается как теорема. В самом деле, пусть имеется 44 НАТУРАЛЬНЫЕ ЧИСЛА гл. I последовательность таких утверждений A1, A2, A3,..., что а) при любом r справедливость Ar+1 вытекает из справедливости Ar, б) известно, что A1 справедливо.

Мы докажем, что предположение о том, что хоть одно из утверждений A несправедливо, придется отбросить. Действительно, если бы хоть одно из утверждений A было неверным, то множество всех натуральных чисел n, для которых An неверно, не было бы пустым. Тогда согласно принципу наименьшего целого числа оно содержало бы наименьшее число p, которое вследствие б) должно было бы быть больше чем 1. Но тогда Ap было бы неверно, а Ap-1 верно. Это противоречит условию а).

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

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

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

в противном случае вопрос о том, верна или неверна теорема, остается открытым, и она может быть доказана или опровергнута когда-нибудь в будущем уже иными методами.

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

Иначе можно иной раз прийти и к абсурду. Мы предлагаем читателю разобраться в следующем софизме. Мы докажем сейчас, что любые два целых положительных числа равны между собой; например, 5 = 10. Начнем с определения. Если a и b Ч два неравных между собой целых положительных числа, то через max(a, b) будем обозначать a или b, смотря по тому, какое из чисел больше: a или b; если же a = b, то положим max(a, b) = a = b. Так, max(3, 5) = max(5, 3) = 5, тогда как max(4, 4) = 4. Далее, через An обозначим следующее утверждение: Если a и b Ч два таких целых положительных числа, что max(a, b) = n, то a = b.

а) Предположим, что Ar верно. Пусть a и b Ч два таких целых положигл. I ТЕОРИЯ ЧИСЕЛ тельных числа, что max(a, b) = r + 1. Рассмотрим числа = a - 1, = b - 1;

тогда max(, ) = r. В таком случае =, так как Ar верно. Но отсюда следует, что a = b; значит, верно и Ar+1.

б) A1, очевидно, верно, так как если max(a, b) = 1, то a и b (по предположению Ч целые положительные числа) должны быть каждое в отдельности равны 1.

Итак, по принципу математической индукции An верно при любом n.

Пусть теперь a и b Ч два произвольных целых положительных числа;

положим max(a, b) = r. Было показано, что An верно при любом n; значит, в частности, верно Ar. Следовательно, a = b.

ДОПОЛНЕНИЕ К ГЛАВЕ I Теория чисел Введение Мистические и суеверные представления, связывавшиеся первоначально с целыми числами, мало-помалу изгладились, но среди математиков интерес к числам не ослабевал никогда. Евклид (около 300 г.

до нашей эры), громкая слава которого объясняется той частью его Начал, которая посвящена основам геометрии (изучаемым в школе), по-видимому, сделал оригинальные открытия в области теории чисел, тогда как его геометрия в значительной степени представляет собой компиляцию ранее полученных результатов. Диофант Александрийский (около 275 г. нашей эры), один из первых алгебраистов, оставил также след в теории чисел. Пьер Ферма (1601Ц1665), живший в Тулузе, по специальности юрист, вместе с тем замечательнейший математик своей эпохи, положил начало современным теоретико-числовым изысканиям.

Эйлер (1707Ц1783), наиболее изумительный из математиков в смысле богатства продукции, в своих исследованиях весьма часто углублялся в область теории чисел. Сюда же следует прибавить ряд иных имен, знаменитых в анналах математики: Лежандр, Дирихле, Риман. Гаусс (1777Ц1855), виднейший из математиков более близкой к нам эпохи, в равной степени отдававший себя различным отраслям математики, следующими словами определил свое отношение к теории чисел: Математика Ч царица наук, теория чисел Ч царица математики.

46 ТЕОРИЯ ЧИСЕЛ гл. I з 1. Простые числа 1. Основные факты. Многие утверждения в области теории чисел, как и математики вообще, относятся не к отдельным объектам, скажем, к числу 5 или числу 32, а к целому классу объектов, имеющих какое-то общее свойство; примерами могут служить класс всех четных чисел 2, 4, 6, 8,..., или класс чисел, делящихся на 3, 3, 6, 9, 12,..., или класс квадратов целых чисел 1, 4, 9, 16,...

и так далее.

В теории чисел особенно важную роль играет класс всех простых чисел. Очень многие числа могут быть разложены на меньшие множители: 10 = 2 5, 111 = 3 37, 144 = 3 3 2 2 2 2, и т. п. Числа, которые таким образом не разлагаются, носят название простых. Точнее, простым называется такое целое число p, большее единицы, которое не имеет иных множителей, кроме единицы и самого себя. (Число a есть множитель, или делитель, числа b или делит число b, если существует такое целое число c, что b = ac.) Числа 2, 3, 5, 7, 11, 13, 17, Ч простые, тогда как, например, число 12 не является простым, так как 12 = 3 4.

Значение класса простых чисел заключается в том, что каждое число может быть представлено как произведение простых : если данное число не простое, то его можно последовательно разлагать на множители до тех пор, пока все множители не окажутся простыми; так, например, 360 = 3 120 = 3 30 4 = 3 3 10 2 2 = 3 3 5 2 2 2 = 23 32 5.

Число, отличное от 0 и 1 и не являющееся простым, называется составным.

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

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

з 1 ПРОСТЫЕ ЧИСЛА Пользуясь знаками, мы можем обозначить все простые числа через p1, p2,..., pn. Всякое иное число тем самым составное и должно делиться по меньшей мере на одно из простых чисел p1, p2,..., pn. А теперь мы придем к противоречию, а именно, построим число A, которое будет отлично от каждого из чисел p1, p2,..., pn, так как будет больше их всех и тем не менее не будет делиться ни на одно из них. Вот это число:

A = p1p2... pn + 1.

Как видно, оно равно единице плюс произведение тех чисел, которые образуют совокупность всех простых чисел. Число A больше, чем любое из чисел p, и потому должно быть составным. Но при делении на p1, на p2 и т. д. A дает всякий раз остаток 1, таким образом, A не делится ни на одно из чисел p. Сделанное нами допущение, что существует лишь конечное число простых чисел, приводит, таким образом, к противоречию, так что приходится заключить, что это допущение ошибочно, а следовательно, истинным может быть только противоположное ему.

Итак, теорема доказана.

Хотя это доказательство и косвенного характера, все же небольшое его видоизменение приводит, по крайней мере теоретически, к методу построения бесконечной последовательности простых чисел. Предположим, что, исходя из некоторого простого числа, скажем p1 = 2, мы уже нашли n простых чисел p1, p2,..., pn; заметим, далее, что число p1p2... pn + 1 или простое, или содержит множителем простое число, отличное от тех, которые уже найдены. Так как такой множитель всегда может быть найден (хотя бы непосредственными пробами), то в обоих названных случаях мы в итоге получаем новое простое число pn+1; продолжая таким же образом дальше, убеждаемся, что последовательность простых чисел, которые мы действительно можем построить, не имеет конца.

Упражнение. Выполните намеченное построение, начиная с простых чисел p1 = 2, p2 = 3; найдите еще пять простых чисел.

Если какое-нибудь число представлено в виде произведения простых множителей, то эти множители можно, конечно, располагать в каком угодно порядке. Занимаясь разложением чисел на простые множители, мы очень скоро приходим к заключению, что с точностью до порядка сомножителей разложение любого числа N на простые множители обладает свойством единственности: каждое натуральное число N, большее единицы, может быть разложено на простые множители только одним способом. Это утверждение кажется на первый взгляд таким очевидным, что неспециалист склонен обыкновенно отвергать необходимость его доказательства. Все же рассматриваемое предложение отнюдь не тривиально; с другой стороны, его доказательство, хотя и совсем элементарного содержания, требует более или менее тонких рассуждений. Классическое доказательство этой лосновной теоремы арифмети48 ТЕОРИЯ ЧИСЕЛ гл. I ки, данное Евклидом, базируется на методе (лалгоритме) нахождения общего наибольшего делителя двух чисел. Этот метод будет нами рассмотрен на стр. 61. Здесь же мы приведем доказательство менее почтенной давности, которое несколько короче, чем доказательство Евклида, и вместе с тем выглядит несколько более софистическим. Оно также является типичным образцом косвенного рассуждения. Мы допустим, что существует такое число, которое может быть разложено на простые множители двумя существенно различными способами, и это допущение приведет нас к противоречию. Возникновение противоречия будет свидетельствовать о том, что гипотеза о существовании числа, допускающего два существенно различных разложения на простые множители, несостоятельна; и отсюда мы заключим, что разложение чисел на простые множители обладает свойством единственности.

* Если существует хоть одно число, допускающее два существенно различных разложения на простые множители, то существует непременно и наименьшее число, обладающее таким свойством (см. стр. 37), m = p1p2... pr = q1q2... qs, (1) где через p и q обозначены простые числа. Меняя, если потребуется, порядок этих множителей, мы можем допустить, что p1 p2... pr, q1 q2... qs.

Заметим, что p1 отлично от q1: иначе, деля равенство (1) на общий простой множитель, мы получили бы два существенно различных разложения на простые множители числа, которое было бы меньше, чем m, и это противоречило бы предложению о том, что m Ч наименьшее число, обладающее таким свойством. Следовательно, одно из двух: или p1 < q1, или q1 < p1. Пусть p1 < q1. (Если бы оказалось q1 < p1, то в дальнейшем рассуждении достаточно было бы поменять местами буквы p и q.) Рассмотрим целое число m = m - (p1q2q3... qs). (2) Подставляя вместо m два его выражения, взятые из равенства (1), мы можем представить число m в любом из двух видов:

m = (p1p2... pr) - (p1q2q3... qs) = p1(p2... pr - q2q3... qs), (3) m = (q1q2... qs) - (p1q2q3... qs) = (q1 - p1)q2q3... qs. (4) Из равенства (4) следует, что m Ч положительное число, так как p1 < q1;

из равенства (2) следует, с другой стороны, что m меньше чем m. Но раз так, то разложение m на множители должно быть единственным (с точностью до порядка сомножителей). Из равенства (3) далее видно, что p1 входит множителем в m ; значит, из равенства (4) можно в таком случае заключить, что p1 входит множителем или в q1 - p1, или з 1 ПРОСТЫЕ ЧИСЛА в q2q3... qs. (Это вытекает из единственности разложения m на простые множители; см. рассуждение в следующем абзаце.) Но последнее невозможно, так как все q больше чем p1. Поэтому p1 должно входить множителем в q1 - p1, т. е. q1 - p1 должно делиться на p1. Другими словами, существует такое целое число h, что q1 - p1 = p1 h, или q1 = p1(h + 1).

Но это значит, что q1 делится на p1, чего, однако, быть не может, так как, по предположению, q1 Ч число простое. Противоречие, к которому мы пришли, показывает несостоятельность первоначально сделанного допущения, чем и заканчивается доказательство основной теоремы арифметики.

Вот одно важное следствие основной теоремы. Если простое число p входит множителем в произведение ab, то оно непременно входит множителем или в a, или в b. В самом деле, если бы p не входило множителем ни в a, ни в b, то, перемножая разложения на простые множители чисел a и b, мы получили бы разложение на простые множители числа ab, не содержащее множителя p. С другой стороны, так как предполагается, что p входит множителем в произведение ab, то это значит, что существует такое целое число t, что ab = pt.

Поэтому, перемножая p и разложение на простые множители числа t, мы получим разложение на простые множители числа ab, содержащее множитель p. Таким образом, приходится признать, что существует два различных разложения числа ab на простые множители, а это противоречит основной теореме.

Примеры. Если установлено, что 2652 делится на 13 и что 2652 = = 6 442, то отсюда можно сделать заключение, что 442 делится на 13.

С другой стороны, 240 делится на 6 и притом 240 = 15 16, но ни 15, ни не делятся на 6. Этот пример показывает, что условие основной теоремы относительно того, что число p Ч простое, является существенным.

Упражнение. Чтобы найти все делители числа a, достаточно разложить a в произведение a = p 11p 22... p rr, где все множители p Ч простые и различные, причем каждый из них возводится в некоторую степень. Все делители числа a имеют вид b = p 11p 22... prr, где показатели Ч произвольные целые числа, подчиненные условиям 0, 0,..., 0.

Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 76 |    Книги по разным темам