 |
Отступление про Диофанта и его исторический след.
|
|
|
|
Третий и последний период античного общества - период господства Рима. Рим завоевал Сиракузы в 212 году, Карфаген - в 146 году, Грецию - в 146, Месопотамию - в 46, Египет - в 30 году до нашей эры. Огромные территории оказались на положении колоний, но римляне не трогали их культуры и экономического устройства пока те исправно платили налоги и поборы. Установленный римлянами на столетия мир, в отличие от всех последующих великих миров и рейхов, принес всей завоеванной территории самый длинный период безвоенного существования, торговли и культурного обмена.
Александрия оказалась центром античной математики. Велись оригинальные исследования, хотя компилирование, пересказ и комментирование становились и стали основным видом научной деятельности. Александрийские ученые, если угодно, приводили науку в порядок, собирая разрозненные результаты в единое целое, и многие труды античных математиков и астрономов дошли до нас только благодаря их деятельности. Греческая наука с ее неуклюжим геометрическим способом выражения при систематическом отказе от алгебраических обозначений угасала, алгебру и вычисления (прикладную математику) александрийцы почерпнули с востока, из Вавилона, из Египта.
Основной труд Диофанта (ок. 250 г.) - "Арифметика". Уцелели только шесть книг оригинала, общее их число - предмет догадок. Мы не знаем, кем был Диофант, - возможно, что он был эллинизированный вавилонянин. Его книга - один из наиболее увлекательных трактатов, сохранившихся от греко-римской древности. В ней впервые встречается систематическое использование алгебраических символов, есть особые знаки для обозначения неизвестного, минуса, обратной величины, возведения в степень. Папирус N 620 Мичиганского университета, купленный в 1921 году, принадлежит эпохе Диофанта и наглядно это подтверждает. Среди уравнений, решаемых Диофантом, мы обнаруживаем такие, как x 2 - 26 y 2 = 1 и x 2 - 30 y 2 = 1, теперь известные нам как частные случаи "уравнения Пелля", причем Диофант интересуется их решениями именно в целых числах.
|
|
|
Книга Диофанта неожиданно оказала еще и огромное косвенное влияние на развитие математической науки последних трех столетий. Дело в том, что юрист из Тулузы Пьер Ферма (1601 - 1665), изучая "Арифметику" Диофанта, сделал на полях этой книги знаменитую пометку: "Я нашел воистину удивительное доказательство того, что уравнение x n + y n = z n при n > 2, не имеет решений в целых числах, однако поля этой книги слишком малы, чтобы здесь его уместить". Это одно из самых бесполезных математических утверждений получило название "Великой теоремы Ферма" и, почему-то, вызвало настоящий ажиотаж среди математиков и любителей (особенно после назначения в 1908 году за его доказательство премии в 100 000 немецких марок). Попытки добить эту бесполезную теорему породили целые разделы современной алгебры, алгебраической теории чисел, теории функций комплексного переменного и алгебраической геометрии, практическая польза от которых уже не подлежит никакому сомнению. Сама теорема, кажется, благополучно доказана в 1995 году; Пьер Ферма, конечно, погорячился на полях "Арифметики", ибо он физически не мог придумать подобного доказательства, требующего колоссальной совокупности математических знаний. Элементарного доказательства великой теоремы Ферма пока никто из жителей нашей планеты найти не смог, хотя над его поиском бились лучшие умы последних трех столетий. Однако, до сих пор тысячи психически нездоровых любителей-"ферматистов" в жажде славы и денег бомбят своими письмами академические институты и университеты и почти ежегодно один из сотрудников кафедры алгебры и дискретной математики Уральского госуниверситета, где я работаю, вынужден вести с таким психом дипломатическую переписку на заранее заготовленном бланке:
|
|
|
"Уважаемый.............................! В Вашем доказательстве на странице №......, в строке №........, содержится ошибка..............................................................".
Пусть требуется решить линейное диофантово уравнение:
ax + by = c,
где a, b, c Î Z; a и b - не нули.
Попробуем порассуждать, глядя на это уравнение.
Пусть (a, b) = d. Тогда a = a 1 d; b = b 1 d и уравнение выглядит так:
a 1 d· x + b 1 d· y = c, т.е. d· (a 1 x + b 1 y) = c.
Теперь и ежику ясно, что у такого уравнения имеется решение (пара целых чисел x и y) только тогда, когда d | c. Поскольку очень хочется решать это уравнение дальше, то пусть d | c. Поделим обе части уравнения на d, успокоимся, и всюду далее будем считать, что (a, b) = 1. Так можно.
Рассмотрим несколько случаев.
Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение". Немножко потрудившись, находим, что
| x = - | b a | y. |
Так как x должен быть целым числом, то y = at, где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt, at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.
Дорогие читатели, не правда ли, что все названия уже до боли знакомы? "Однородное уравнение", "общее решение" - все это мы уже слышали и в курсе линейной алгебры и в лекциях по дифференциальным уравнениям. При разборе следующего случая эта аналогия буквально выпирает на первый план, что, конечно, не случайно, но исследование единства великого государства линейности на материке математики выходит за рамки этой скромной книжки.
Случай 2. Пусть теперь c ¹ 0. Этот случай закрывается следующей теоремой.
Теорема. Пусть (a, b) = 1, { x 0 , y 0 } - частное решение диофантова уравнения ax + by = c. Тогда его общее решение задается формулами:
| ì í î | x = x 0 - bt y = y 0 + at. |
Таким образом, и в теории линейных диофантовых уравнений общее решение неоднородного уравнения есть сумма общего решения соответствующего однородного уравнения и некоторого (любого) частного решения неоднородного уравнения. Вот оно - проявление единства линейного мира! (Однажды, перед экзаменом по дифференциальным уравнениям, мне снился кошмар, будто все линейные пространства решений сговорились между собой и требовали от меня прибавить к ним частное решение, так как они не хотели содержать нулевой вектор, а хотели быть линейными многообразиями. Я отказался, а наутро, на экзамене, мне досталась однородная система!)
|
|
|
Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x *, y *} - какое-нибудь решение уравнения ax + by = c. Тогда ax * + by * = c, но ведь и ax 0 + by 0 = c. Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:
a (x *- x 0 ) + b (y *- y 0 ) = 0
- однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x 0 = - bt, y *- y 0 = at, откуда моментально, используя навыки третьего класса средней школы, получаем:
| ì í î | x * = x 0- bt, y * = y 0 + at. |
¨
"Все это, конечно, интересно", - скажет читатель, - "Но как же искать то самое частное решение { x 0 , y 0 }, ради которого и затеяна вся возня этого пункта и которое, как теперь выясняется, нам так нужно?". Ответ до глупости прост. Мы договорились, что (a, b) = 1. Это означает, что найдутся такие u и v из Z, что au + bv = 1 (если вы это забыли, вернитесь в пункт 4), причем эти u и v мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv = 1 на c и получим: a (uc) + b (vc) = c, т.е. x 0 = uc, y 0 = vc. Вот и все!
Пример. Вы - хроноп, придуманный Хулио Кортасаром в книжке "Из жизни хронопов и фамов". Вам нужно расплатиться в магазине за синюю пожарную кишку, ибо красная в хозяйстве уже давно есть. У вас в кармане монеты достоинством только в 7 и 12 копеек, а вам надо уплатить 43 копейки. Как это сделать? Решаем уравнение:
|
|
|
7 x + 12 y = 43
Включаем алгоритм Евклида:
12 = 7· 1 + 5
7 = 5· 1 + 2
5 = 2· 2 + 1
2 = 1· 2
Значит, наибольший общий делитель чисел 7 и 12 равен 1, а его линейное выражение таково:
1 = 5 - 2· 2 = 5 - (7 - 5) · 2 = (12 - 7) - (7 - (12 - 7) · 2) = 12· 3 + 7· (- 5),
т.е. u = - 5, v = 3. Частное решение:
x 0 = uc = (- 5) · 43 = - 215
y 0 = vc = 3 · 43 = 129.
Итак, вы должны отобрать у кассира 215 семикопеечных монет и дать ему 129 двенадцатикопеечных. Однако процедуру можно упростить, если записать общее решение неоднородного диофантова уравнения:
x = -215 - 12 t
y = 129 + 7 t
и, легко видеть, что при t = - 18, получаются вполне разумные x = 1, y = 3, поэтому дубасить кассира необязательно.
Задачки 
| 1. Решите диофантовы уравнения: а) 2 x + 7 y = 20; б) 6 x - 27 y = 21; в) 11 x + 99 y = 41. 2. Для каждого целого z решите в целых числах уравнение 2 x + 3 y = 5 z. 3. Решите уравнение 3 sin 7 x + cos 20 x = 4, а потом предложите решить его знакомому школьнику. Кто быстрее? 4. Сколькими различными способами можно расплатиться за вкуснейшую девяностосемикопеечную жевательную резинку лишь пятаками да копейками? |
Пункт 6. Простые числа и "основная" теорема арифметики.
Определение. Число р Î N, р ¹ 1, называется простым, если р имеет в точности два положительных делителя: 1 и р. Остальные натуральные числа (кроме 1) принято называть составными. Число 1 - на особом положении, по договору, оно ни простое, ни составное.
Как это часто бывает в математике, да и в других науках, прилагательным "простой" называется объект только первоначально казавшийся простым. Простые числа, как выяснилось в процессе накопления научных знаний, появляются в различных областях математики и являются одним из самых загадочных и тяжелых для изучения монстров. Любопытного читателя, любителя ужастиков и лихо закрученных сюжетов, я отсылаю здесь к изумительному рассказу математика из Боннского университета Дон Цагира "Первые пятьдесят миллионов простых чисел", опубликованному в книжке "Живые числа", М.: Мир, 1985 г.
Отметим некоторые несложные наблюдения, связанные с простыми числами.
Наблюдение 1. Наименьший делитель любого числа а Î N, отличный от 1, есть число простое.
Доказательство. Пусть с | а, с ¹ 1 и с - наименьшее с этим свойством. Если существует с 1 такое, что с 1 | с, то с 1 £ с и с 1 | а, следовательно, с 1 = с или с 1 = 1.
¨
Наблюдение 2. Наименьший отличный от 1 делитель составного числа а Î N не превосходит Ö a.
Доказательство. с | а, с ¹ 1, с - наименьший, следовательно
а = са 1 , а 1 | а, а 1 ³ с, значит аа 1 ³ с 2 а 1 , а ³ с 2 и с £ Ö a.
|
|
|
¨
Следующее наблюдение, отдавая дань уважения его автору - Евклиду, назовем теоремой.
Теорема (Евклид). Простых чисел бесконечно много.
Доказательство. От противного. Ну пусть р 1 , р 2 ,..., р n - все простые, какие только есть. Рассмотрим число а = р 1 р 2 ... р n + 1. Его наименьший отличный от 1 делитель с, будучи простым, не может совпадать ни с одним из р 1 , р 2 ,..., р n , так как иначе с | 1. Не перестаю удивляться изобретательности ума людей тысячелетней древности!
¨
Для составления таблицы простых чисел древний грек Эратосфен придумал процедуру, которая получила название "решето Эратосфена":
2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17,...
Идем по натуральному ряду слева направо. Подчеркиваем первое неподчеркнутое и невычеркнутое число, а из дальнейшего ряда вычеркиваем кратные только что подчеркнутому. И так много раз. Легко понять, что подчеркнутые числа - простые. Если вспомнить наблюдение 2, то становится понятно, что когда вычеркнуты все кратные простых, меньших р, то оставшиеся невычеркнутые, меньшие р 2 - простые. Это значит, что составление таблицы всех простых чисел меньших N закончено сразу, как только вычеркнуты все кратные простых, меньших Ö a.
Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Чудаки люди! Например, в 1876 году француз Люка доказал, что число 2 127 - простое, и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если на него взглянуть:
2 127 -1 = 170141183460469231731687303715884105727.
В настоящее время составлены таблицы всех простых чисел, не превосходящих 50 миллионов, далее известны только отдельные их представители. Читателей всегда привлекает гигантизм, поэтому укажу здесь два самых больших известных на сегодняшний момент простых числа: 2 44497 - 1 и 2 86243 - 1. Последнее число записано пока в книгу рекордов Гиннеса, в нем 25962 десятичных знака. Найдено оно было, конечно, в рекламных целях - демонстрация фирмой IBM возможностей очередного суперкомпьютера, которому для проверки этого числа на простоту с помощью специальных изощренных тестов (пригодных только для чисел вида 2 n- 1) потребовалась неделя работы и куча денег. И это трата денег происходит в то время, когда у нас в России более трети населения живет за чертой бедности, а половина детей в Уганде не умеют ни читать, ни писать, а только сидят и гундят!
Самой важной и общеизвестной в этом пункте является следующая теорема (искушенные алгебраисты скажут, что она утверждает факториальность кольца Z, а я воздержусь от каких-либо комментариев в адрес этой теоремы, ибо про столь важную персону математического мира надо либо долго говорить, либо почтенно молчать). Эта теорема носит название "Основной теоремы арифметики".
Теорема. Всякое целое число, отличное от - 1, 0 и 1, единственным образом (с точностью до порядка сомножителей) разложимо в произведение простых чисел.
Доказательство. Будем доказывать утверждение теоремы только для натуральных чисел, ибо знак минус перед числом умеют ставить все умеющие ставить знак минус.
Пусть а > 1, р 1 - его наименьший простой делитель. Значит,
а = р 1 а 1 . Если, далее, а 1 > 1, то пусть р 2 - его наименьший простой делитель и а 1 = р 2 а 2 , т.е. а = р 1 р 2 а 2 , и так далее, пока а n не станет равным единице. Это обязательно произойдет, так как а > а 1 > а 2 ..., а натуральные числа с естественным порядком удовлетворяют условию обрыва убывающих цепей (во как выразился!). Имеем, таким образом,
a = p 1 p 2 ... p n , и возможность разложения доказана.
Покажем единственность. Ну пусть a = q 1 q 2 ... q n - другое разложение, т.е. p 1 p 2 ...p n = q 1 q 2 ...q s . В последнем равенстве правая часть делится на q 1 , следовательно, левая часть делится на q 1 . Покажем, что если произведение p 1 p 2 ...p n делится на q 1 , то один из сомножителей р k обязан делиться на q 1 .
Действительно, если q 1 | p 1 , то все доказано. Пусть q 1 не делит p 1 . Так как q 1 - простое число, то (q 1 , p 1 ) = 1. Значит найдутся такие
u, v Î Z, что up 1 + vq 1 = 1. Умножим последнее равенство на p 2 ...p n , получим: p 2 ... p n = p 1 (p 2 ... p n ) u + q 1 (p 2 ... p n ) v. Оба слагаемых справа делятся на q 1 , следовательно, p 2 ...p n делится на q 1 . Далее рассуждайте по индукции сами.
Теперь пусть, например, q 1 | p 1 . Значит q 1 = p 1 , так как p 1 - простое. Из равенства p 1 p 2 ...p n = q 1 q 2 ...q s банальным сокращением моментально получим равенство p 2 ...p n = q 2 ...q s . Снова рассуждая по индукции, видим, что n = s, и каждый сомножитель левой части равенства p 1 p 2 ...p n = q 1 q 2 ...q n обязательно присутствует в правой и наоборот.
¨
Сразу отмечу без доказательства два достаточно очевидных следствия из этой теоремы.
Следствие 1. Всякое рациональное число однозначно представимо в виде
| p | a 1 1 | p | a 2 2 | ... p | a k k | , |
где a 1 , a 2 ,..., a k Î Z.
¨
Следствие 2. Если
| a = p | a 1 1 | p | a 2 2 | ... p | a n n | , | b = p | b 1 1 | p | b 2 2 | ... p | b n n |
- целые числа, то наибольший общий делитель a и b равен
| p | g 1 1 | p | g 2 2 | ... p | g n n | , |
а наименьшее общее кратное a и b равно
| p | d 1 1 | p | d 2 2 | ... p | d n n | , |
где g i = min { a i , b i }, a d i = max { a i , b i }.
¨
Можно очень долго анализировать, какие такие глубинные причины вызывают к жизни "основную теорему" арифметики, однако такой анализ, боюсь, уведет нас слишком далеко за пределы основных понятий арифметики. Отмечу только, что для справедливости обсуждаемой теоремы просто необходима аддитивная структура кольца целых чисел. Поясню необходимость наличия сложения плохим примером.
Плохой пример. Пусть S = {4 k + 1 | k Î Z } - множество вот таких вот целых чисел. Легко проверить, что S замкнуто относительно умножения:
(4 k 1 + 1)·(4 k 2 + 1) = 16 k 1 k 2 + 4 k 2 + 4 k 1 + 1 = 4·(4 k 1 k 2 + k 1 + k 2 ) + 1 Î S,
однако это множество не замкнуто относительно сложения. "Квазипростые" числа из S - суть далее неразложимые в произведение чисел из S: 5, 9, 13, 17, 21, 49,... Индуктивным рассуждением, подобным рассуждению в первой части доказательства основной теоремы арифметики, легко убедиться, что всякое число из S разложимо в произведение "квазипростых". Однако единственность такого разложения отсутствует: 441 = 21·21 = 9·49, при этом 9 не делит 21, и 49 не делит 21. Вот какой плохой пример.
Задачки 
| 1. Простое число - это число, имеющее в точности два различных положительных делителя (единицу и себя). Найдите все натуральные числа, имеющие в точности а) три различных положительных делителя; б) четыре различных положительных делителя; в) k штук различных положительных делителей (k > 4). 2. Опоссум Порфирий в зоопарке раскладывает на простые множители число 81 057 226 635 000. Помогите ему, не то он обидится. 3. Методом Эратосфена составьте таблицу простых чисел, меньших 100. 4. Докажите, что среди членов каждой из арифметических прогрессий: а) 3, 7, 11, 15, 19,... б) 5, 11, 17, 23, 29,... в) 11, 21, 31, 41, 51,... имеется бесконечно много простых чисел. (1) 5. Докажите, что в натуральном ряде имеются сколь угодно длинные промежутки вида { n, n +1, n +2, …, n + k }, не содержащие простых чисел. 6. Докажите, что не существует такого многочлена f (x) = a 0 x n + a 1 x n -1 +…+ a n -1 x + a n с целыми коэффициентами, что все числа f (0), f (1), f (2), f (3), … являются простыми.(2) |
(1) Оказывается, справедлив такой общий факт: Если первый член и разность арифметической прогрессии взаимно просты, то среди ее членов содержится бесконечно много простых чисел. Более того, ряд, составленный из обратных величин к этим простым числам, расходится. Это классическое утверждение называется теоремой Дирихле и доказывается весьма сложно. В 1950 году датский математик А. Сельберг придумал чрезвычайно сложное и хитроумное элементарное (не использующее аппарат высшей математики) доказательство теоремы Дирихле, однако жить лучше от этого не стало и даже сильно одаренному школьнику доказательство теоремы Дирихле вряд ли объяснишь.
(2) Абсолютно несложное доказательство этого факта впервые придумал Л. Эйлер. Он же напридумывал массу многочленов f (x), значения которых при многих последовательных натуральных x являются про-стыми числами. Два примера:
а) f (x) = x 2 + x +41, при x = 0, 1, 2,..., 39.
б) f (x) = x 2 -79 x +1601, при x = 0, 1, 2,..., 79.
Если же рассматривать многочлены от нескольких переменных, то, как следует из результатов Ю. В. Матиясевича о диофантовости рекурсивных множеств (опубликовано в 1970 году), существуют многочлены, множество положительных значений которых в точности является множеством всех про-стых чисел. Преследуя чисто спортивный интерес, укажу здесь один такой многочлен от 26 переменных:
F (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) =
= { k + 2}{1 - (wz + h + j - q) 2 - (2 n + p + q + z - e) 2 -
- (a 2 y 2 - y 2 + 1 - x 2 ) 2 -({ e 4 + 2 e 3 }{ a + 1} 2 - o 2 ) 2 -
- (16{ k + 1} 3 { k + 2}{ n + 1} 2 + 1 - f 2 ) 2 -
- ({(a + u 4 - u 2 a) 2 - 1}{ n + 4 dy } 2 + 1 - { x + cu } 2 ) 2 - (ai + k + 1 - l - i) 2 -
- ({ gk + 2 g + k + 1}{ h + j } + h - z) 2 - (16 r 2 y 4 { a 2 - 1} + 1 - u 2 ) 2 -
- (p - m + l { a - n - 1} + b {2 an + 2 a - n 2 - 2 n - 2}) 2 -
- (z - pm + pla - p 2 l + t {2 ap - p 2 - 1}) 2 -
- (q - x + y { a - p - 1} + s {2 ap + 2 a - p 2 - 2 p - 2}) 2 -
- (a 2 l 2 - l 2 + 1 - m 2 ) 2 - (n + l + v - y) 2 }
Цепные дроби
В этом параграфе мы отходим от изучения только целых чисел и действующими лицами станут произвольные действительные (как рациональные, так и иррациональные) числа. Сей параграф посвящен очень остроумному математическому аппарату - цепным (или непрерывным) дробям. Почему-то о них не рассказывают в школах, техникумах и университетах в обязательном порядке, а зря. Кроме того, что изучение цепных дробей занимательно само по себе, их применения выходят далеко за рамки теории чисел: они помогают исследовать числовые последовательности, анализировать алгоритмы, решать дифференциальные уравнения и т.д. Не претендуя на полноту изложения теории цепных дробей в этом параграфе и отдавая дань уважения славному ученому - математику А. Я. Хинчину, я сразу упомяну здесь его классическую книжку "Цепные дроби", в которой любопытный читатель найдет еще много интересных фактов, кроме тех, которые будут изложены ниже.
|
|
|
