ДИОФАНТОВ АНАЛИЗ И БОЛЬШАЯ ТЕОРЕМА ФЕРМА
Пока доказать теорему Ферма
Никто не сумел, хоть охотников ≈ тьма.
В другом Диофантовы методы, вроде,
Во всем хороши, а вот к ней не подходят .Дж. А. Линдон. Клерихыо ( Перевод А. Глебовской.)
Во многих сборниках математических головоломок конца прошлого века (когда цены на скот были гораздо ниже теперешних) приводится такая задача. Один фермер потратил 100 долларов на покупку 100 различных домашних животных. Каждая корова обошлась ему в 10 долларов, свинья≈в 3 доллара, а овца ≈ по 50 центов за голову. Предполагая, что фермер приобрел по крайней мере одну корову, одну свинью и одну овцу, подсчитать, сколько голов скота каждого вида он купил?
На первый взгляд кажется, что это обычная задача из элементарной алгебры, однако, начав ее решать, мы быстро обнаруживаем, что у нас получается система двух уравнений с тремя неизвестными, каждое из которых должно быть положительным целым числом. Нахождение целочисленных решений алгебраических уравнений в наши дни называется обычно диофантовым анализом. В прошлые столетия такой анализ допускал использование в качестве переменных и рациональные дроби, однако сейчас он, как правило, ограничивается только целыми числами, включая нуль и отрицательные целые числа.
Естественно, что в задачах, аналогичных вышеприведенной, все неизвестные величины должны быть положительными целыми числами. В литературе по занимательной математике встречается множество такого рода неопределенных (диофантовых) задач. Классическими примерами таких задач являются широко известная задача про обезьяну и кокосовые орехи, а также старинная задача о нахождении прямоугольных треугольников со сторонами, длина которых выражается в целых числах.
Термин ╚диофантов╩ берет свое начало от имени выдающегося греческого математика Диофанта из Александрии. К сожалению, мы до сих пор не знаем точно, в каком веке он жил, однако большинство историков математики относят его работы к III в. О его жизни нам практически ничего не известно, за исключением нескольких незначительных фактов, которые упоминаются в одной стихотворной задаче, вошедшей в более поздний греческий сборник математических головоломок. Эти стихи так часто цитируются, а алгебраическое решение самой задачи настолько тривиально, что я не буду их повторять. Если в этой задаче приведены действительные факты, то, значит, у Диофанта был сын, умерший в среднем возрасте, а сам Диофант дожил до 84 лет. До нашего времени дошла примерно половины его главного труда ≈ математического трактата ╚Арифметика╩. Поскольку большинство задач в этой книге предусматривает решения в целых числах, то для анализа подобного рода проблем стал применяться термин ╚диофантов╩. Сам Диофант не предпринимал никаких попыток создать систематическую теорию таких задач, точно так же как нет почти никаких свидетельств использования методов диофантова анализа математиками, жившими до него.
Сегодня диофантов анализ ≈ это обширная, сложная область теории чисел, которой посвящена многочисленная научная литература. При этом полная теория разработана лишь для линейных уравнений. Неизвестен (а, быть может, и не существует) общий метод решения уравнений второй и более высоких степеней. Анализ даже простейшего нелинейного диофантова уравнения может представить огромнейшие трудности. Такое уравнение может вообще не иметь решения, может иметь бесчисленное множество решений или, наконец, может обладать произвольным конечным числом решений. Множество такого рода уравнений ≈ причем настолько простых, что они понятны даже ребенку,≈ упорно сопротивляется всем попыткам найти их решение или же доказать, что такое решение невозможно.
Самое простое линейное диофантово уравнение имеет вид ax + by = с, где х и у ≈ неизвестные, а а, b и с ≈ заданные числа. Попытаемся использовать это уравнение для описания задачи, приведенной в начале главы. Пусть х ≈ число коров, у ≈ число свиней и z ≈ число овец, купленных фермером. Тогда мы легко можем записать следующие два соотношения:
10x+3y+z/2=100,
х+ у +z= 100.
Для того чтобы избавиться от знаменателя, умножим первое уравнение на 2. Из полученного результата 20х + 6y + z = 200 вычтем второе уравнение. Исключая таким образом переменную z, мы получим уравнение 19x + 5y = 100. Как найти целые значения неизвестных х и у? Существует много способов проделать это, но я приведу здесь лишь один старый алгоритм с использованием непрерывных дробей, который применим к любым уравнениям такого типа.
Оставим в левой части уравнения лишь член с наименьшим коэффициентом: 5y=100≈19x. Разделив теперь обе части на 5, получим y=(100≈ 19x)/5. Далее разделим правую часть почленно на 5 и представим остатки (если таковые имеются) в виде конечных дробей со знаменателем, равным 5. Таким образом, наше уравнение преобразуется к виду у=20 ≈ Зх ≈ 4х/5.
Очевидно, что если х и у ≈ целые положительные числа (каковыми они и должны быть), то х должно быть таким, чтобы дробь 4x/5 оказалась целым числом. Отсюда ясно, что число х должно быть кратным 5. Наименьшее такое кратное есть само число 5. В этом случае величина у оказывается равной 1, а неизвестная z (определяемая с помощью любого из двух исходных уравнений) ≈ равной 94. Итак, мы нашли решение: 5 коров, 1 свинья и 94 овцы,
Существуют ли другие решения нашей задачи? Если бы мы могли пользоваться отрицательными целыми числами, то решений оказалось бы бесчисленное множество, хотя, понятно, что отрицательных животных не бывает. В самом деле, при х, равном 10 или любому другому числу, кратному 5, число у становится отрицательным. Таким образом, данная задача имеет только одно решение.
В приведенном простом примере первая же полученная дробь 4х/5 не содержит члена с неизвестной у. Для уравнений такого же вида, но с большими коэффициентами описанную процедуру часто приходится повторять по многу раз. Конечную дробь приравнивают некоторой новой целочисленной неизвестной, например а, член с наименьшим коэффициентом вновь оставляют в левой части уравнения, после чего вся процедура повторяется для получения новой конечной дроби. В конце концов вы обязательно получите дробь, содержащую только одну неизвестную, причем эта дробь будет иметь достаточно простой вид, позволяющий оценить, какие же значения должна принимать неизвестная величина, чтобы данная дробь оказалась целым числом. Возвращаясь по этапам обратно, с помощью полученной последовательности уравнений нетрудно найти решение исходной задачи.
Для того чтобы построить пример уравнения, аналогичного тому, которое мы только что исследовали, но не имеющего решения, предположим, что корова стоит 5 долларов, свинья≈2 доллара, а овца≈ 50 центов. Оба исходных уравнения преобразуем точно так же, как и в предыдущем случае. Чтобы избавиться от знаменателя, умножим первое из них на два, а затем вычтем из него второе. В результате мы получим диофантово уравнение вида 9х+3y=100. Применяя процедуру построения непрерывных дробей, в конце концов мы придем к соотношению у = 33 ≈ Зх ≈1/3, из которого следует, что при целом х число у целым быть не может. В данном случае, впрочем, можно сразу сообразить, что уравнение 9х + 3y=100 не имеет решения в целых числах, если вспомнить следующую хорошо известную теорему. Если коэффициенты при х и у имеют общий множитель, не являющийся таковым для числа, стоящего в правой части, то данное уравнение не допускает рeшения в целых числах. В нашем случае числа 9 и 3 имеют общий множитель 3, а число 100 на 3 не делится. Легко понять, почему эта теорема справедлива. Если оба стоящих слева числа кратны числу п, то и их сумма будет кратной n; следовательно, число, стоящее справа, также должно быть кратным п. Еще более простым примером является уравнение 4х + 8у=101. Левая часть этого соотношения, понятно, должна быть четным числом, а значит, она не может равняться нечетному числу в правой его части. Полезно также вспомнить, что если все три данных числа имеют общий множитель, то исходное уравнение можно тут же упростить, разделив обе его части на этот общий множитель.
В качестве примера такого варианта основной задачи, для которого число целочисленных решений конечно и больше единицы, рассмотрим случай, когда корова стоит 4 доллара, свинья ≈ 2 доллара и овца ≈ 1/3 доллара. Как и раньше, фермер тратит 100 долларов и покупает себе 100 домашних животных, причем не меньше одной головы каждого вида. Сколько коров, свиней и овец он купит на этот раз?
Многие геометрические задачи также решаются путем нахождения целочисленных решений тех или иных диофантовых уравнений. В одной из глав моей книги ╚Математический цирк╩ (Gardner M. Mathematical Circus ), посвященной треугольникам, я привел два классических примера такого рода: найти целочисленные решения в задаче о двух пересекающихся лестницах, а также в задаче о расположении пятнышка внутри равностороннего треугольника. Среди множества геометрических диофантовых задач, решение которых не найдено до сих пор, одной из самых трудных и наиболее известных является задача о так называемом ╚целочисленном кирпиче╩ или ╚рациональном кубоиде╩. Под ╚кирпичом╩ в данном случае понимается прямоугольный параллелепипед. При этом мы имеем 7 неизвестных: 3 ребра кирпича, 3 его лицевые диагонали и 1 пространственную диагональ, проходящую через центр кирпича из одного его угла в другой (рис. 8).
Найдется ли такой кирпич, у которого все 7 указанных переменных являются целыми числами?
Данная задача эквивалентна нахождению целочисленного решения следующей системы уравнений с семью неизвестными-
а2 + b2 = с2,
a2+d2=e2,
b2+d2=f2,
b2+e2=g2.
Эта задача не решена до сих пор, как и не найдено пока доказательства, что решение ее не существует. Поисками решения данной задачи много занимался английский математик Джон Лич, которому я обязан следующей информацией. Наименьший кирпич с ребрами и лицевыми диагоналями, выраженными в целых числах (лишь его пространственная диагональ≈не целое число), имеет стороны длиной 44, 117 и 240. Леонард Эйлер считал это решение минимальным. Наименьший кирпич, у которого все указанные размеры, за исключением одной лицевой диагонали, выражаются в целых числах, имеет стороны длиной 104, 153 и 672≈этот результат также был известен Эйлеру. (При этом длина пространственной диагонали оказывается равной 697.) Третий случай ≈ когда длина одной из сторон не выражается целым числом,≈ как утверждает Лич, ранее не рассматривался. Этот случай также имеет решения, но числа, получаемые в результате, являются, по выражению Лича, ╚премерзкими╩. Так, он считает, что соответствующий кирпич наименьших размеров должен иметь ребра длиной 7800, 18720 и квадратный корень из числа 211 773 121 (что дает нам иррациональное число). При этом объем кирпича, очевидно, также выражается иррациональным числом.
Рис 9 Простая диофантова задача
Гораздо проще оказывается геометрическая задача, представленная на рис. 9 (я взял ее из сборника математических головоломок Л. Лонгли-Кука). На клетчатой бумаге нарисован прямоугольник (под этим термином может подразумеваться также квадрат), причем крайние его клетки заштрихованы. В нашем случае количество заштрихованных клеток не равно числу пустых клеток во внутреннем прямоугольнике, Можно ли построить такой прямоугольник, границы которого шириной в одну клетку содержали бы столько же клеток, сколько их насчитывается во внутреннем прямоугольнике? Если да, то задача состоит в том, чтобы найти все такие решения. Соответствующее диофантово уравнение, описывающее решение этой задачи, легко решается методом разложения на множители, о котором я расскажу в ╚Ответах╩.
В древности наиболее известной из диофантовых задач, сформулированной еще Архимедом, была так называемая ╚задача о скоте╩. Она содержит всего 8 неизвестных, однако целые числа, возникающие при ее решении, настолько велики (самое меньшее из них состоит более чем из 200000 цифр), что ее удалось решить только с помощью ЭВМ в 1965 г. Те, кто заинтересуется этой задачей, могут найти подробный ее разбор в книге Эрика Белла ╚Последняя задача╩, а ее окончательное решение ≈ в статье Г. Уильямса и др. (см. список литературы в конце книги).
Однако самой знаменитой из всех диофантовых задач, полное решение которой не найдено и поныне, является так называемая ╚большая теорема╩ Пьера Ферма, французского математика XVII в , много занимавшегося теорией чисел (по профессии он был юристом). Практически каждому математику известно, как Ферма, читая ╚Арифметику╩ Диофанта, сделал на нолях згамечание на латинском языке к восьмой задаче из второй книги, где требовалось решить в целых числах уравнение х2 + y2=а2. Ферма писал, что такое уравнение не имеет решений в целых числах для степеней, больших, чем 2. (В случае уравнения второй степени решения его называются ╚пифагоровьши числами╩, причем число этих решений бесконечно.) Короче говоря, Ферма утверждал, что уравнение хn + yn=an не имеет решений в целых числах, если показатель степени п есть целое положительное число, большее 2. Замечание Ферма заканчивается словами: ╚Я нашел этому поистине чудесное доказательство, однако поля слишком узки, чтобы поместить его здесь╩.
До сегодняшнего дня никто не знает, действительно ли у Ферма имелась такое доказательство. Поскольку самые знаменитые математики после Ферма так и нс сумели его найти, большинство считает, что Ферма ошибался. Однако полностью принять это мнение не позволяет тот факт, что всякий раз, когда Ферма утверждал, что у него имеется доказательство, оно у него действительно было. Рассмотрим, например, диофантово уравнение y3 = х2 + 2. Простым подбором можно легко убедиться, что это уравнение имеет решения 33 = 52 + 2 и 33 = ≈52 + 2. Однако, как пишет Белл в своей книге ╚Творцы математики╩(Bell Е. Т. Men of Mathematics), для того чтобы доказать, что других целочисленных решений у такого уравнения не существует, ╚требуется не меньше интеллектуальных усилий,... чем для постижения глубин теории относительности╩. Ферма утверждал, что у него имеется такое доказательство, хотя он и не опубликовал его. ╚В этом случае он основывался вовсе не на догадках,≈ продолжал Белл.≈ Задача эта очень трудна, он утверждал, что обнаружил доказательство ≈ позднее доказательство было найдено╩. Ферма действительно опубликовал сравнительно простое доказательство того, что уравнение х4 + y4=a4 не имеет решений, а позднее математики доказали невозможность решения более сложного уравнения: х3+ у3 = а3 Для случаев n=5 и n = 7 то же самое было доказано в самом начале XIX в.
Можно показать, что большая теорема Ферма справедлива для всех простых показателей степени, больших 2. К 1978 г. эта теорема была доказана для любых показателей степени, не превышающих 125000, так что если для нее и существует какой-либо контрпример, то в нем должны фигурировать числа, состоящие более чем из миллиона цифр. Полное доказательство большой теоремы Ферма продолжает оставаться одной из самых глубоких нерешенных проблем диофантова анализа. Теперь, когда Курт Гедель с помощью своего знаменитого доказательства теоремы неразрешимости установил, что в арифметике существуют теоремы, которые нельзя доказать в рамках дедуктивной системы самой арифметики, некоторые математики стали придерживаться мнения, что утверждение Ферма истинно, но недоказуема. (Если большая теорема Ферма неразрешима но Геделю, то она должна быть верной, потому что если бы она была ошибочной, то ее можно было бы легко опровергнуть с помощью одного-единственного контрпримера )
Я со всей серьезностью призываю читателей не присылать мне доказательств. Я недостаточно компетентен, чтобы в них разобраться. Карл Фердинанд Линдеман, первым доказавший в 1882 г. трансцендентность числа л(пи) опубликовал однажды пространное доказательство большой теоремы Ферма, которое, как оказалось, в самом начале содержало ошибку, роковым образом повлиявшую на ход всех рассуждений. Были опубликованы десятки других неправильных доказательств, полученных многими известными математиками. Когда однажды Давида Гильберта спросили, почему он никогда не пробовал заняться этой задачей, он ответил: ╚Прежде чем приступить к ней, нужно потратить по крайней мере три года на интенсивную подготовку, а у меня нет возможности тратить столько времени без малейшей уверенности в конечном результате╩.
Кафедры математики многих крупных университетов возвращают авторам любые доказательства большой теоремы Ферма, сопровождая их стандартным письмом, в котором говорится, что доказательство будет рассмотрено только после получения университетом определенной суммы в качестве залога. Немецкий математик Эдмунд Ландау пользовался обычно специальным бланком, на котором было напечатано:
╚Дорогой сэр (мадам)! Мы получили Ваше доказательство большой теоремы Ферма. Первая ошибка находится на стр. ... , строка ... ╩. Затем Ландау поручал заполнить бланк кому-либо из аспирантов.
Дональд Кнут заканчивает предисловие к первому тому своего капитального труда ╚Искусство программирования╩(Knuth D, Е. The Art of Computer Programming ≈1968) лукавым замечанием, в котором читателю предлагается доказать большую теорему Ферма. Автор утверждает, будто бы кто-то, читавший книгу в рукописи, пометил сбоку страницы, что у него есть поистине замечательное доказательство, но здесь, на полях, оно никак не поместится.
Леонард Эйлер также не сумел доказать большую теорему Ферма, однако сформулировал более общее утверждение, которое, если оно верно, включает в себя теорему Ферма в качестве частного случая. Эйлер предположил, что ни одну n-ную степень, большую 2, нельзя представить в виде суммы менее чем п слагаемых n-ной степени. Как мы уже убедились, это предположение справедливо при п = 3, поскольку в этом случае оно представляет собой просто большую теорему Ферма для показателя степени 3. Вместе с тем пока не известно, обладает ли целочисленным решением уравнение вида x4 + y4+ z4 = a4.
В 1966 г., примерно через два столетия после того, как Эйлер высказал свою догадку, был опубликован пример, опровергающий ее. Леон Ландер и Томас Паркин с помощью расчетов на ЭВМ показали, что предположение Эйлера нарушается при п = 5. Этот контрпример в случае минимально возможных чисел имеет вид
275 + 843 + 1105 + 1335 = 1445.
Полученный результат позволяет предположить, что если где-то во вселенной имеются разумные существа, живущие в пространстве пяти измерений, то в их задачниках по математике наверняка приводится такая задача. Какой наименьший пятимерный гиперкуб можно сложить из единичных гиперкубиков, так чтобы из того же самого числа единичных гиперкубиков можно было образовать четыре меньших гиперкуба и при этом не осталось бы ни одного лишнего гиперкубика? Ответ: это гиперкуб размером 144 x 144 x144 x144 x 144.
1. Задача про фермера и домашних животных сводится к диофантову уравнению вида 11х + 5y = 200. Используя метод непрерывных дробей, нетрудно получить следующие три решения в положительных целых числах:
| Коровы | Свиньи | Овцы |
| 5 | 29 | 66 |
| 10 | 18 | 72 |
| 15 | 7 | 78 |
2. Л. Лонгли-Кук в своей книге ╚Развлечения с головоломками╩ (задача 87)( Longley-Cook L. H. Fun with Brain Puzzles. ≈ Fawcett, 1965) решает задачу о прямоугольнике следующим образом. Пусть х и у≈длины сторон большого прямоугольника. Общее число клеток в этом прямоугольнике равно ху. Граница шириной в одну клетку содержит 2х + 2y - 4 клеток. Поскольку в условии задачи сказано также, что граница должна иметь ху/2 клеток, мы можем записать следующее соотношение:
ху/2 = 2х + 2y - 4.
Умножая обе части этого уравнения на 2 и перегруппировав члены, находим
ху -4х- 4у = -8.
Прибавляя 16 к обеим частям уравнения, получаем ху≈4х≈4у+16=8.
Разложение левой части на множители дает
(х-4)(у-4)=6.
Ясно, что выражения (х ≈ 4) и (у ≈ 4) должны быть целыми положительными множителями числа 8. Единственные пары таких множителей ≈ это пары (8, 1) и (4, 2). Они дают нам два решения: х= 12, y=5 и x=8,y=6.
Эта задача тесно связана с задачей о прямоугольных треугольниках с целочисленными сторонами. В самом деле, ширина границы выражается целым числом только тогда, когда диагональ большого прямоугольника делит его на два ╚пифагоровых треугольника╩.
Если обобщить данную задачу и допустить существование нецелых решений в случае границы произвольной равномерной ширины, сохранив лишь условие равенства площадей границы и внутреннего прямоугольника, то оказывается, что существует на удивление простая формула для ширины границы. (Эту формулу мне любезно сообщил С. Л. Портер.) Для этого нужно просто сложить две соседние стороны границы, затем вычесть диагональ большого прямоугольника и разделить полученный результат на 4. Описанная процедура даст нам ширину границы прямоугольника.
Некоторые читатели обобщили рассматриваемую задачу на случай трех измерений, с тем чтобы выразить в целых числах размеры кирпича, составленного из такого количества единичных кубиков, которое потребовалось бы, чтобы покрыть кирпич со всех сторон слоем единичных кубиков. Д. Слитор с помощью ЭВМ сумел найти полное решение этой задачи: таких кирпичей может быть всего 20. Самый маленький кирпич имеет ребра длиной 8, 10 и 12, самый большой≈5, 13 и 132. Это подтверждает догадку М. Гринблата, высказанную им в книге ╚Математические развлечения╩ ( Greenblatt М. Н, Mathematical Entertainment,≈ Crowell, 1965), где он утверждает, что данная задача имеет ╚около╩ 20 решений.
ДОПОЛНЕНИЕ
Одна из самых известных среди нерешенных задач в диофантовом анализе, так называемая десятая проблема Гильберта, была блестяще решена в 1970 г, 22-летним аспирантом Ленинградского университета Юрием Матиясевичем. Как известно, в 1900 г. замечательный немецкий математик Давид Гильберт составил перечень из 23 наиболее важных нерешенных математических проблем, которые, как он надеялся, будут решены в течение столетия. Десятая проблема Гильберта состояла в том, чтобы найти достаточно общий алгоритм, следуя которому можно было бы узнать, имеет ли произвольно заданное алгебраическое уравнение с целыми рациональными коэффициентами решение в целых числах или не имеет.
Матиясевич показал, что такого алгоритма не существует. Иными словами, он ╚решил╩ десятую проблему Гильберта, доказав, что она не имеет решения. Особую роль в его доказательстве играет последовательность чисел Фибоначчи.
Детали его рассуждений приведены в статье М. Дэвиса и Р. Херша ╚Десятая проблема Гильберта╩(Scientific American, p 84≈91 (November 1973)), а также в статье М. Дэвиса ╚Десятая проблема Гильберта неразрешима╩(The American Mathematical Monthly, 80, 233≈269 (March 1973)).
Назад, к статье "Мистер Аполлинакс в Нью-Йорке" | Вперед, с статье "Эллипс"