§ 1. Основные понятия и теоремы Пункт 1. Деление с остатком. Целые числа — суть {..., –3, –2, –1, 0, 1, 2 , 3,...}. В этой книжке будет употребляться довольно стандартное обозначение этого множества — жирная буква Z . (Очень часто употребляется и ажурная , но я не сторонник ажурных излишеств ушедшего в прошлое стиля рококо). Известно, что относительно обычных операций сложения и умножения, множество целых чисел является кольцом, а для более страстных почитателей алгебры можно сказать и точнее: Z является моногенным ассоциативно-коммутативным кольцом с единицей. Этот привычный со школьной скамьи объект на самом деле является очень сложным, но я не буду сейчас объяснять, в чем состоит сложность арифметики целых чисел, ибо такое объяснение может увести нас слишком далеко от названия этого пункта. Математику-профессионалу в этом месте могут прийти в голову и знаменитая теорема Геделя о неполноте формальной арифметики, и выдающийся результат Матиясевича об алгоритмической неразрешимости систем диофантовых уравнений, и великое множество элементарно формулируемых, но до сих пор нерешенных теоретико-числовых проблем и т.д., и т.п. Однако, давайте пока воспримем Z просто как объект, преподнесенный нам в подарок природой-матушкой и займемся его изучением. “Прекрасная половина” {1, 2, 3, 4,...} множества целых чисел зовется множеством натуральных чисел и стандартно обозначается жирной как поросеночек буквой N . Определение. Пусть a , b Z . Число а делится на число b если найдется такое число q Z , что а = qb . Синонимы: а кратно b ; b — делитель а . Запись: а b или b | a . Легко заметить, что отношение делимости b | a есть бинарное отношение на множестве Z , а если ограничиться рассмотрением только натуральных чисел, то несложно установить, что на множестве N это бинарное отношение является рефлексивным, антисимметричным и транзитивным, т. е. отношением частичного порядка. Легко проверяется также следующее свойство: Пусть а 1 + а 2 +...+ а n = c 1 + c 2 +...+ c k – равенство сумм целых чисел. Если все слагаемые в этом равенстве, кроме одного, кратны b , то и оставшееся слагаемое обязано быть кратным b . Перечисленные свойства отношения делимости позволят нам доказать основную теорему первого пункта: Теорема . Для данного целого отличного от нуля числа b , всякое целое число а единственным образом представимо в виде а = bq + r , где 0 r Доказательство. Ясно, что одно представление числа а равенством а = bq + r мы получим, если возьмем bq равным наибольшему кратному числа b , не превосходящему а (см. рис. 1) ( a = 3b+r ) Рис. 1 Тогда, очевидно, 0 r Сразу после доказательства теоремы, пока не забылись использовавшиеся в нем обозначения, дадим Определение. Число q называется неполным частным, а число r — остатком от деления а на b . Признаюсь, что идея рисунка 1, поясняющего доказательство теоремы, принадлежит не мне, а древним грекам, которые, впрочем, не знали, что они древние. Именно древние греки, почему-то, очень любили многократно укладывать один отрезок в другой, а оставшуюся часть большего отрезка, естественно, называли “остатком”. Заметим, дорогие читатели, что остаток — всегда есть число неотрицательное, а вот неполное частное может быть каким угодно целым числом. Поэтому на вопрос: “Сколько будет минус пять поделить на три с остатком?”, каждый должен бойко отвечать: “Минус два, в остатке — один!”. Но за добрый десяток лет опыта приема устных вступительных экзаменов в университет, судьба еще не послала мне абитуриента, правильно ответившего на этот вопрос. А ведь это дети, специально готовившие себя поступать именно на математико-механический факультет. “Печально я гляжу на наше поколение...” Задачки 1. Разделите с остатком: а) 161 на 17; б) –161 на 17; в) 161 на –17; г) –161 на –17. 2. Разделите с остатком: а) 17 на 161; б) –17 на 161; в) 17 на –161; г) –17 на –161. 3. Проверьте, что множество N \ {1}={2,3,4,...} с отношением делимости есть частично упорядоченное множество. Найдите его минимальные элементы. 4. Справедливый ковбой зашел в бар и попросил у бармена стакан виски за 3 доллара, пачку Marlboro за доллар и 11 центов, шесть пачек патронов для своего кольта и дюжину коробков спичек. Услышав итоговую сумму – 28 долларов и 25 центов, ковбой пристрелил бармена. За что? ^ Пункт 2. Наибольший общий делитель. Не затягивая развития событий, начнем сразу с определения. Определение. Число d Z , делящее одновременно числа а , b , c , ... , k Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) . Перечислим, кое-где доказывая, основные свойства наибольшего общего делителя. Первое свойство, ввиду его важности, окрестим теоремой. Она покажет нам, как устроен наибольший общий делитель двух целых чисел. Теорема (Свойство 1) . Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv . Доказательство . Рассмотрим множество P = { au + bv u,v Z }. Очевидно, что P Z , а знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , b , 0 P . Пусть x , y P и y 0 . Тогда остаток от деления x на y принадлежит P . Действительно: x = yq + r , 0 r r = x – yq = ( au 1 + bv 1 ) – ( au 2 + bv 2 ) q = a ( u 1 – u 2 q )+ b ( v 1 – v 2 q ) P . Пусть d P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r 1 , 0 r 1 Далее, раз d P , то d = au 0 + bv 0 . Если теперь d 1 - общий делитель a и b , то d 1 | ( au 0 + bv 0 ), т.е. d 1 | d . Значит d d 1 и d - наибольший общий делитель. Свойство 2 . Для любых целых чисел а и k , очевидно, справедливо: ( а , kа ) = а ; (1, а ) = 1. Свойство 3 . Если a = bq + c , то совокупность общих делителей a и b совпадает с совокупностью общих делителей b и с , в частности, ( a , b ) = ( b , c ). Доказательство. Пусть d | a , d | b , тогда d | c . Пусть d | c , d | b , тогда d | a . Конечно, я привел здесь это "крутое" доказательство не потому, что читатели не смогли бы его придумать самостоятельно, а потому, что мне хочется, опять-таки, проиллюстрировать это доказательство на древнегреческий лад. Посмотрите на рис. 2: Рис. 2 Если d целое число раз укладывается в а и в b , то, очевидно, что d обязано целое число раз уложиться и в с . Наглядная иллюстрация! Спасибо грекам. Свойство 4 . Пусть a , b и m - произвольные целые числа. Тогда ( am , bm ) = m ( a , b ). Доказательство. Если d - наибольший общий делитель чисел а и b , то dm | am и dm | bm , т.е. dm - делитель am и bm . Покажем, что dm - наибольший общий делитель этих чисел. Поскольку d - наибольший общий делитель чисел а и b , то, согласно свойству 1, для некоторых целых чисел u и v выполнено равенство d = au + bv . Умножив это равенство на m , получим равенство: dm = amu + bmv . Видно, что если некоторое число s делит одновременно am и bm , то s обязано делить и dm , т.е. s dm , следовательно, dm - наибольший общий делитель. Свойство 5 . Пусть s - делитель а и b . Тогда: ( а / s , b / s ) = ( a , b ) s . Доказательство . ( a , b ) = a s s , b s s = s a s , b s . Свойство 6 . Очевидно теперь, что a ( a , b ) , b ( a , b ) = 1. Свойство 7 . Если ( a , b ) = 1, то ( ac , b ) = ( c , b ). Доказательство . Пусть ( c, b ) = d . Имеем: d | b , d | c , следовательно d | ac , т.е. d - делитель ас и b . Пусть теперь ( ac , b ) = s . Имеем: s | b , s | ac , s - делитель b , т.е. либо s = 1, либо s не делит а . Это означает, что s | c , значит s | d . Итак, d и s делятся друг на друга, т.е. d = s . Что еще сказать в этом пункте? Да, пожалуй, больше и нечего. Задачки 1 . Докажите, пожалуйста, что если d = ( a 1 , a 2 , ... a n ) - наибольший общий делитель чисел a 1 , a 2 , ... a n , то найдутся такие целые числа v 1 , v 2 , ... v n , что d = v 1 a 1 + v 2 a 2 +...+ v n a n ). 2 . Вася любит Машу. Маша тоже любит Васю, но согласна выйти за него замуж только если наибольшие общие делители у пар чисел (2 3 ·5·13·45, 5 23 ·11 6 ·21) и (6·35·10, 17 4 ·15·55) совпадают. Есть ли у Васи шанс? Пункт 3. Взаимно простые числа. Определение. Целые числа a и b называются взаимно простыми, если ( a , b ) = 1. Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1. Казалось бы, что особенного можно сказать о взаимно простых числах? Ну нет у них общих делителей, отличных от 1 и - 1, и все тут. Однако, зададимся вопросом: "Как часто встречаются пары взаимно простых чисел?", и постараемся ответить на него с довольно неожиданной точки зрения - в терминах теории вероятностей. Пусть X = { x n | n = 1, 2,...} - произвольная строго возрастающая последовательность натуральных чисел (или, если угодно, X - произвольное подмножество натуральных чисел, упорядоченное естественным образом). Обозначим через ( N ; X ) число членов последовательности X , не превосходящих N . Определение. Число = ___ lim N ( N ; X ) N называется (верхней асимптотической) плотностью последовательности X = { x n | n = 1, 2,...} в множестве N . Пример 1. Пусть x n = 2 n , где n пробегает N , - последовательность всех четных чисел. Очевидно, что ___ lim N ( N ; { x n }) N = 1 2 . Между прочим, это хорошо согласуется с нашими интуитивными представлениями о том, что четных чисел - половина. Пример 2. Пусть x n =2 n , где n пробегает N , - геометрическая прогрессия. Интуитивно ясно, что таких чисел в натуральном ряду мало, ибо чем "дальше в лес" по натуральному ряду, тем реже встречается степень двойки. Понятие плотности подтверждает это ощущение: (2 k ; { x n }) = k , и, легко проверить, что ___ lim N ( N ; { x n }) N = lim k k 2 k = 0. Резонно считать, что плотность - это вероятность наугад вытащить из натурального ряда число, принадлежащее заданной последовательности. (Согласитесь, что вы всегда так и думали. Вероятность достать четное число есть 1/2, а вероятность напороться на степень двойки, особенно среди больших чисел, вообще говоря, ничтожно мала). Аналогично определению плотности последовательности, можно дать определение плотности множества пар натуральных чисел. Пусть имеется произвольное множество Х упорядоченных пар натуральных чисел. Обозначим через ( N ; X ) число пар из множества Х , каждая компонента которых не превосходит N . Полезно представить себе пары чисел из множества Х как координаты точек на координатной плоскости, тогда ( N ; X ) есть просто число точек множества Х , попавших в квадрат {( x , y ) | 0 Определение. Число = ___ lim N ( N ; X ) N 2 называется (верхней асимптотической) плотностью множества пар ^ Х в множестве N 2 . Пример 3. Пусть Х - множество всех пар натуральных чисел, у которых первая компонента строго больше второй. Множеству Х соответствуют точки первой четверти координатной плоскости, лежащие под биссектрисой y = x . Плотность такого множества легко подсчитать: = ___ lim N ( N ; X ) N 2 = ___ lim N N ( N -1)/2 N 2 = 1 2 , что, опять-таки, согласуется с нашим интуитивным представлением о том, что упорядоченных пар, у которых первая компонента превосходит вторую примерно половина от общего количества всех пар натуральных чисел. Пусть ^ X - множество всех упорядоченных пар ( u , v ) натуральных чисел таких, что ( u , v ) = 1, т.е. множество всех пар взаимно простых чисел. (В этом месте я подумал о неудачности стандартного обозначения ( u , v ) для наибольшего общего делителя, но, раз уж я влип в эту коллизию, то, всякий раз в дальнейшем прийдется уповать на контекст, призванный вносить ясность в смысл обозначения.) Ответ на вопрос о частоте появления пары взаимно простых чисел дает удивительная теорема, открытая в 1881 году итальянцем Э. Чезаро. ^ Теорема (Чезаро). Вероятность выбрать из N пару взаимно простых чисел равна 6/ 2 , точнее = ___ lim N ( N ; X ) N 2 = 6 2 . Таким образом, плотность взаимно простых чисел в множестве N 2 оказывается существует и равна 6/ 2 0, 607... Примерно в 60% случаев вы вытащите из натурального ряда пару взаимно простых. И еще удивительно - в теореме Чезаро возникло число , загадочное и вездесущее! Вот уж никак не ожидали мы встретить его посередь царства целых чисел! Доказательство. Строгое доказательство теоремы Чезаро довольно сложно и громоздко. Но, как говорится, человека (а, в особенности, женщину) убеждает не строгая логика, а эмоция и правильно подобранные наводящие соображения. Вот и сейчас я схитрю и вместо строгого доказательства приведу некоторые эвристические рассуждения, призванные убедить читателя, почему эта теорема вообще должна быть правдоподобна. Забудем, что существование вероятности (верхнего предела), строго говоря, нужно кропотливо доказывать. Предположим сразу, что существует вероятность p того, что случайно выбранные натуральные числа а и b взаимно просты. Пусть d N . Через P { S } обозначим, как обычно, вероятность события S . Рассуждаем: Р {( a , b ) = d } = = P { d | a } · P { d | b } · P a d , b d = 1 = = 1 d · 1 d · p = p d 2 . Просуммировав теперь эти вероятности по всем возможным значениям d , мы должны получить единицу: 1 = d N P {( a , d ) = d } = d = 1 p d 2 , а сумма ряда d = 1 1 d 2 известна и равна 2 /6 (см., напр., задачник Демидовича по матанализу, раздел "Ряды Фурье"). Итак, 1 = 2 6 · p , следовательно, p = 6/ 2 . Лихо, правда?! Задачки ^ 1 . Докажите своему другу, что из пяти последовательных целых чисел всегда можно выбрать одно, взаимно простое со всеми остальными. 2 . Докажите своей подруге, что из 16 последовательных целых чисел всегда можно выбрать одно, взаимно простое со всеми остальными. 3 . Докажите себе, что каждые два числа последовательности 2+1, 2 2 +1, 2 4 +1, 2 8 +1, ..., 2 2 n +1, ... являются взаимно простыми * . 2961. (Из задачника Демидовича). Разложить функцию f ( x ) = x 2 в ряд Фурье: а) по косинусам кратных дуг в интервале (- , ); б) по синусам кратных дуг в интервале (0, ); в) в интервале (0, 2 ). Пользуясь этими разложениями, найти суммы рядов: n = 1 1 n 2 ; n = 1 (-1) n +1 n 2 ; n = 1 1 (2 n -1) 2 . 5 . Найдите плотность последовательностей: a) x n = 5 n +2; б) x n = n 2 ; в) x n = n +1000. 6 . Найдите плотность множества всех простых чисел ** . 7. Проверьте, что функция ( X ), ставящая в соответствие каждому множеству X натуральных чисел его плотность, удовлетворяет стандартным аксиомам вероятности: 1) ( X ) 0 для всех X (неотрицательность); 2) ( N ) = 1 (нормированность); 3) n = 1 X n = n = 1 ( X n ) для попарно непересекающихся множеств X n (счетная аддитивность). 8 . Найдите плотность множества пар вида: а) (3 n +1, 4 k +3), б) (2 n , 4 k +3), в) (2 n , 3 k ); где n и k независимо пробегают N . 9 . Проверьте, что функция ( X ), ставящая в соответствие каждому множеству X упорядоченных пар натуральных чисел его плотность, удовлетворяет стандартным аксиомам вероятности. 10 . Уговорите своего товарища доказать или докажите сами, что если плотность последовательности строго больше нуля, то для любого натурального k , в этой последовательности найдутся k членов, образующих k -членную арифметическую прогрессию *** . * Между прочим, из утверждения этой задачи сразу следует бесконечность множества простых чисел. Действительно, если бы простых чисел было бы лишь конечное число, то не могло бы существовать бесконечно много чисел, попарно взаимно простых. ** Если эта задача вызывает затруднения, отложите ее в сторону, а после прочтения пункта 15 вернитесь к ее решению. Правильный ответ - ноль. *** Эта задачка - чистое издевательство, однако размышления над ней принесут вам немало пользы. Ут-верждение этой задачи в математическом мире известно как теорема Семериди, а наиболее короткое ее доказательство, использующее эргодическую теорию, содержит около 60 страниц. Теорема Семериди устанавливает, в некотором смысле, характеристическое свойство арифметических прогрессий: всякая бесконечная арифметическая прогрессия имеет ненулевую плотность и всякая последовательность нену-левой плотности содержит сколь угодно длинную арифметическую прогрессию. Прекрасный рассказ об этой теореме и ее элементарное доказательство для k =3 можно найти в книжке Р. Грэхема "Начала теории Рамсея". М., Мир, 1984. ^ Пункт 4. Алгоритм Евклида. Слово "алгоритм" является русской транскрипцией латинизированного имени выдающегося арабского математика ал-Хорезми Абу Абдуллы Мухаммеда ибн ал-Маджуси (787 - ок.850) и означает в современном смысле некоторые правила, список инструкций или команд, выполняя которые, некто (быть может, тупой, но усердный) достигнет требуемого результата. В этом пункте я расскажу алгоритм, позволяющий по заданным натуральным числам a и b находить их наибольший общий делитель. Считается, что этот алгоритм придумал самый влиятельный математик всех времен и народов - Евклид, он изложен в IX книге его знаменитых "Начал". ^ Отступление "Панегирик Евклиду" Не могу удержаться от небольшого исторического отступления про Евклида. О его жизни мы не имеем никаких достоверных сведений, может быть, даже, он не был реальной исторической личностью, а являлся коллективным псевдонимом некоей группы Александрийских математиков, типа Николя Бурбаки. Если он жил, то он жил во времена Птолемея Первого (306 - 283), которому, согласно преданию, он надерзил словами "К геометрии нет царской дороги". Но Птолемеи сознательно культивировали науку и культуру в Александрии, поэтому все эти закидоны своих ученых пропускали мимо ушей. Наиболее знаменитое и выдающееся произведение Евклида - тринадцать книг его "Начал", но есть еще и другие мелкие опусы. Мы не знаем, какая часть этих трудов принадлежит самому Евклиду и какую часть составляют компиляции, но в этих трудах проявляется поразительная проницательность и дальновидность. Это первые математические труды, которые дошли до нас от древних греков полностью. В истории Западного мира "Начала", после Библии, - наибольшее число раз изданная и более всего изучавшаяся книга. Большая часть нашей школьной геометрии заимствована буквально из первых шести книг "Начал", традиция Евклида до сих пор тяготеет над нашим элементарным обучением. Для профессионального математика эти книги все еще обладают неотразимым очарованием, а их логическое дедуктивное построение повлияло на сам способ научного мышления больше, чем какое бы то ни было другое произведение. Слава Птолемеям! Честь и хвала Евклиду! Идут пионеры - Салют "Началам"! Панегирик окончен. Пусть даны два числа a и b ; a 0, b 0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание. Алгоритм: 1. Ввести a и b . 2. Если b = 0 , то Ответ: а . Конец . 3. Заменить r := "остаток от деления а на b ", а := b , b := r . 4. Идти на 2. Как и почему исполнение этого коротенького набора инструкций приводит к нахождению наибольшего общего делителя мы выясним чуть позже, сейчас же хочется сказать несколько слов про сам алгоритм. Внимательное разглядывание и пошаговое выполнение алгоритма Евклида убеждают в его, выражаясь словами иконописца Феофана Грека, "простоте без пестроты". Я очень сожалею, что в тексте невозможно проиллюстрировать работу алгоритма на греческий лад - греки стирали отрезки, нарисованные на песке. У лектора в аудитории в руках мел и тряпка, он может показать этот живой процесс на доске, а вам, дорогие читатели, прийдется довольствоваться застывшим рис. 3: Рис. 3 В современной буквенной записи, кочующей из одного учебника в другой, алгоритм Евклида выглядит так: a > b; a, b Z . a = bq 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3 r 2 = r 3 q 4 + r 4 0 r 1 0 r 2 0 r 3 0 r 4 Экзаменатор, настойчиво внушающий студенту мысль об ошибочности решения студента явиться на экзамен с невыученным алгоритмом Евклида. · · · · · · · · · r n -3 = r n -2 q n -1 + r n -1 r n -2 = r n -1 q n + r n r n -1 = r n q n +1 0 r n -1 0 r n r n +1 = 0 Имеем: b > r 1 > r 2 >... > r n > 0, следовательно процесс оборвется максимум через b шагов. Очень интересный и практически важный народохозяйственный вопрос о том, когда алгоритм Евклида работает особенно долго, а когда справляется с работой молниеносно, мы рассмотрим в этой книжке чуть позже. Давайте сейчас покажем, что r n = ( a , b ). Просмотрим последовательно равенства сверху вниз: всякий делитель а и b делит r 1 , r 2 ,..., r n . Если же просматривать эту цепочку равенств от последнего к первому, то видно, что r n | r n -1 , r n | r n -2 , и т.д., т.е. r n делит а и b . Поэтому r n - наибольший общий делитель чисел а и b . Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей ( a , b ). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что r n = au + bv = ( a, b ). Действительно, из цепочки равенств имеем: r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ... (идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение) ... = au + bv = ( a , b ). Пример. Пусть а = 525, b = 231. Отдадим эти числа на растерзание алгоритму Евклида: (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок) _ _42| 42 | 0 _ 63| 42 | 21 2 _ 231| 189 | 42 1 525| 462 | 63 3 231 2 Запись того же самого в виде цепочки равенств: 525 = 231 · 2 + 63 231 = 63 · 3 + 42 63 = 42 · 1 + 21 42 = 21 · 2 Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя: 21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 = = 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) = = 525 · 4 - 231 · 9, и наши пресловутые u и v из Z равны, соответственно, 4 и - 9. Пункт 4 закончен. Задачки 1 . Предлагаю читателям самим придумать два разных трехзначных числа а и b и, непрерывно гундя и пикая металлическим голосом фразу: "Я исполнитель алгоритма Евклида", найти их наибольший общий делитель d и его представление в виде d = au + bv , u,v Z . Наиболее упорные могут усложнить себе задачу, заменив трехзначные числа четырехзначными, или даже пятизначными. Шестизначные числа брать не стоит, так как ваши родственники могут уже начать беспокоиться. 2 . К великому беспокойству родственников, все-таки найдите d = (317811, 196418) и его представление в виде d = 317811 u + 196418 v . * 3 . Найдите d = (81719, 52003, 33649, 30107). * Числа 196418 и 317811 являются, соответственно, 27-ым и 28-ым членами последовательности Фибоначчи, с которой мы еще встретимся в этой книжке при анализе алгоритма Евклида. Для обработки алгоритмом Евклида этих двух чисел придется выполнить 26 делений с остатком, что, конечно, многовато для ручной работы, но я все-таки рекомендую вам ее проделать, дабы посмотреть, какие получаются остатки, и почему они получаются именно такими. ^ Пункт 5. Линейные диофантовы уравнения с двумя неизвестными. Обычно, произвольное уравнение (но, как правило, все-таки с целыми коэффициентами) получает титул "диофантово", если хотят подчеркнуть, что его требуется решить в целых числах, т.е. найти все его решения, являющиеся целыми. Имя Диофанта - выдающегося Александрийского математика - появляется здесь не случайно. Диофант интересовался решением уравнений в целых числах еще в третьем веке нашей эры и, надо сказать, делал это весьма успешно. ^ Отступление про Диофанта и его исторический след. Третий и последний период античного общества - период господства Рима. Рим завоевал Сиракузы в 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 . Следующее наблюдение, отдава