Курсоваяработа
Выполнилстудент IV курса физико-математического факультета Белов Денис Владимирович
Вятскийгосударственный гуманитарный университет
Киров, 2006 г.
Введение.
Определим цели, стоящие перед даннойработой. Для этого дадим два определения.
Определение 1. Диофантовым уравнением1-ой степени (линейным) с /> неизвестными называется уравнениевида
/> ,
где все коэффициенты и неизвестные –целые числа и хотя бы одно />.
Для сокращения записи условимся далеесокращать фразу линейное диофантово уравнение, как ЛДУ.
Определение 2. Решением ЛДУназывается упорядоченная n-ка целых чисел />, такая, что />.
Нашей целью будет научиться находить решениянеопределенного уравнения первой степени, если это решение имеется.
Для этого, необходимо ответить наследующие вопросы:
1). Всегда ли ЛДУ имеет решений,найти условия существования решения.
2). Имеется ли алгоритм, позволяющийотыскать решение ЛДУ.
Работа состоит из двух глав, в первойприведены теоретические материалы, во второй решения некоторых задач.
В части 1.1 приведены выдержки изистории неопределенных уравнений. В части 1.2. в виде теоремы приводитсянеобходимое и достаточное условие существования решения ЛДУ, также говорится очисле решений. Далее рассматриваются методы нахождения решений, в пункте 1.3для некоторых частных случаев, в пункте 1.4 для любого ЛДУ, имеющего решение.
1. Диофант и история диофантовых уравнений.
Диофант (Dióphantos)представляет одну из занимательных загадок в истории математики. Мы не знаем,кем был Диофант, точные года его жизни, нам не известны его предшественники,которые работали бы в той же области, что и он. [10]
На могиле Диофанта естьстихотворение-загадка, решая которую нетрудно подсчитать, что Диофант прожил 84года. О времени жизни Диофанта мы можем судить по работам французскогоисследователя науки Поля Таннри, и это, вероятно, середина III в.н.э. [10]
Наиболее интересным представляетсятворчество Диофанта. «Труды его подобны сверкающему огню среди полнойнепроницаемой тьмы». [Стройк] До нас дошло 7 книг из, возможно, 13 [1], которыебыли объединены в «Арифметику». Стиль и содержание этих книг резко отличаютсяот классических античных сочинений по теории чисел и алгебре, образцы которыхмы знаем по «Началам» Евклида, леммам из сочинений Архимеда и Аполлония.«Арифметика», несомненно, явилась результатом многочисленных исследований,многие из которых остались нам неизвестны. Мы можем только гадать о её корнях иизумляться богатству и красоте её методов и результатов.
«Арифметика» Диофанта – это сборникзадач (их всего 189), каждая из которых снабжена решением и необходимымпояснением. В собрание входят весьма разнообразные задачи, а их решение часто ввысшей степени остроумно. Диофант практиковался в нахождении решенийнеопределенных уравнений вида />, /> или систем таких уравнений.Типично для Диофанта, что его интересуют только положительные целые ирациональные решения. Иррациональные решения он называет «невозможными» и тщательноподбирает коэффициенты так, чтобы получились искомые положительные,рациональные решения.
Поэтому, обычно, произвольноенеопределенное уравнение (но, как правило, все-таки с целыми коэффициентами)получает титул «диофантово», если хотят подчеркнуть, что еготребуется решить в целых числах.
Неопределенные уравнения 1-й степениначали рассматриваться индусскими математиками позднее, примерно с V века.Некоторые такие уравнения с двумя и тремя неизвестными появились в связи спроблемами, возникшими в астрономии, например, при рассмотрении вопросов,связанных с определением периодического повторения небесных явлений.[2]
Первое общее решение уравнения первойстепени />,где /> -целые числа, встречается у индийского мудреца Брахмагупты (ок. 625 г). Поэтому,строго говоря, нет оснований называть линейные неопределенные уравнениядиофантовыми. Однако, исторически все же сложилось применять термин«диофантово», к любому уравнению, решаемому в целых числах.
В 1624 г. в публикуется книгафранцузского математика Баше де Мезирьяка «Problẻmes plaisans etdelectables que se font par les nombres». Баше де Мезирьяк для решенияуравнения /> фактическиприменяет процесс, сводящийся к последовательному вычислению неполных частных ирассмотрению подходящих дробей.
После Баше де Мезирьяка в XVII иXVIII веках различные правила для решения неопределенного уравнения 1-й степенис двумя неизвестными давали Роль, Эйлер, Саундерсон и другие математики.
Цепные дроби к решению такихуравнений были применены Лагранжем, который, однако, замечает, что фактическиэто тот же способ, который был дан Баше де Мезирьяком и другими математиками,рассматривавшими неопределенные уравнения до него. Неопределенные уравнения 1-йстепени стали записываться и решаться в форме сравнения значительно позже,начиная с Гаусса. [2]
В августе 1900 г. в Париже состоялсяII Международный конгресс математиков. 8 августа Д.Гильберт прочитал на немдоклад «Математические проблемы». Среди 23 проблем, решение которых(по мнению Д.Гильберта) совершенно необходимо было получить в наступающем XXв., десятую проблему он определил следующим образом:
«Пусть задано диофантовоуравнение с произвольным числом неизвестных и рациональными числовымикоэффициентами. Указать способ, при помощи которого возможно после конечногочисла операций установить, разрешимо ли это уравнение в целых числах». [7]
Гипотезу, что такого способа нет,первым выдвинул (с достаточным на то основанием) американский математик М.Дэвисв 1949 г. Доказательство этой гипотезы растянулось на 20 лет — последний шагбыл сделан только в 1970 г. Юрием Владимировичем Матиясеевичем, на первом годуаспирантуры он показал алгоритмическую неразрешимость 10 проблемы Гильберта.
Однако, если про произвольноедиофантово уравнения нельзя сказать, имеет ли оно целые корни, или нет, топроблема существования целых корней ЛДУ решена. Приведем теоремы, пользуяськоторыми всегда можно сказать, имеет ли целые решения данное ЛДУ или нет.
2. О числе решений ЛДУ.
Теорема 1. При взаимно простыхкоэффициентах /> диофантово уравнение
/>
имеет решение в целых числах.
Доказательство. Обозначим через />множество техположительных чисел />, для которых уравнение
/>
имеет решение в целых числах. />, очевидно, непусто, так как при заданных />, можно подобрать целые значения />, такие, чтобы /> былоположительным числом.
В множестве />существует наименьшее число (/>– подмножествонатуральных чисел), которое мы обозначим через /> /> Обозначим через /> - целые числа, такие,что
/>.
Пусть />, где />; тогда
/>
/>.
Мы подобрали целые значения: />, />,…, />, такие, что />, но />, а /> - наименьшееположительное число в />, т. е. /> не может быть положительным, />, />, />.
Аналогично получаем: />,…,/>.
Мы видим, что /> – общий делитель чисел />, следовательно,поскольку />,/>, />, />, то уравнение разрешимов целых числах.
Теорема 2. Пусть /> - наибольший общийделитель коэффициентов />. Диофантово уравнение имеетрешение тогда и только тогда, когда />. Число решений такого уравненияравно либо нулю, либо бесконечности.
Докажем последовательно все триутверждения теоремы.
1). Пусть />. Для уравнения
/>,
где />, существуют целые числа: /> удовлетворяющиеему. Т.е. такие, что
/>.
Тогда
/>
т. е. /> - решение уравнения.
2). Пусть теперь /> не делит />. Тогда левая частьуравнения при любых целых /> делится на />, а правая на /> не делиться,так что равенство при целых значениях /> невозможно.
3). Если /> - упорядоченная n-ка чисел,удовлетворяющий уравнению, то например, все n-ки
/> при />
также удовлетворяют этому уравнениюи, таким образом, у нас либо совсем не будет решений, либо их будет бесконечноемножество.
Если хоть одна пара коэффициентоввзаимно простая, то />, и уравнение имеет бесчисленноемножество решений.
3. Нахождение решений для некоторых частных случаев ЛДУ.
3.1. ЛДУ c одной неизвестной.
Рассмотрим линейное уравнение с однойнеизвестной, т.е. уравнение вида
/> />
Ясно, что решением данного уравнениябудет />, ирешение будет целым числом только в том случае, когда />.
3.2. ЛДУ с двумя неизвестными.
Рассмотрим теперь линейное уравнениес двумя неизвестными
/>, />.
Покажем несколько алгоритмов длянахождения решения.
Способ 1.
Пусть />
Рассмотрим два случая:
а). /> не делится на />. В этом случае решенийнет по теореме 2.
б). /> делится на />, поделим на />.
/>;
/>.
Таким образом получили новое ЛДУ, стем же множеством решений, но уже со взаимно-простыми коэффициентами. Поэтомудалее мы будем рассматривать именно такие уравнения.
Рассмотрим />, />.
/>, перейдем к сравнению,
/>.
Т.к. />, то сравнение имеет единственноерешение />.
/>; подставим в уравнение.
/>;
/>;
/>, причем />.
Обозначим />.
Тогда общее решение можно найти поформулам: />,где />.
Пример. />, />.
Найдем решение сравнения />;
/>;
/>, т.е. />
/> />.
/>;
/>
Получили общее решение: />, где />.
Способ 2.
Рассмотрим еще один способ нахождениярешения ЛДУ с двумя неизвестными, а для этого рассмотрим уравнение вида />. Уравнениятакого вида называются линейными однородными диофантовыми уравнениями (ЛОДУ).Выражая неизвестную />, через неизвестную /> приходим к />. Так как xдолжен быть целым числом, то/>, где /> — произвольное целое число. Значит/>. Решениями ЛОДУ/> являютсяn-ки вида />,где />.Множество всех таких n-ок называется общим решением ЛОДУ, любая же конкретнаяпара из этого множества называется частным решением.
Рассмотрим теперь уравнение />, />. Пусть n-ка/>его частноерешение, а множество n-ок /> общее решение соответствующего ЛОДУ.Докажем предложение.
Общее решение ЛДУ />, /> задается уравнениями />, где />.
Доказательство. То, что правые частиуказанных в формулировке теоремы равенств действительно являются решениями,проверяется их непосредственной подстановкой в исходное уравнение. Покажем, чтолюбое решение уравнения /> имеет именно такой вид, какойуказан в формулировке предложения. Пусть /> — какое-нибудь решение уравнения />. Тогда />, но ведь и />. Вычтем изпервого равенства второе и получим:
/> - однородное уравнение. Пишемсразу общее решение: /> />, откуда получаем:
/>. Доказательство завершено.
Встает вопрос о нахождении частногорешения ЛДУ.
/>
По теореме о линейном разложении НОД,это означает, что найдутся такие /> и /> из множества целых чисел, что />, причем эти /> и /> мы легко умеемнаходить с помощью алгоритма Евклида. Умножим теперь равенство /> на /> и получим: />, т.е./>, />.
Таким образом, для нахождения общегорешения находим общее решение ЛОДУ, частное решение ЛДУ и их складываем.
Замечание: особенно этот способудобен, когда /> или />. Если, например, />, />, тогда n-ка />, очевидно,будет частным решением ЛДУ. Можно сразу выписывать общее решение.
Пример. />, />.
Найдем частное решение. Используемалгоритм Евклида.
/>;
/>
Получаем линейное разложение НОД:
/>, т.е />.
/>, />
Получили общее решение: />, где />.
Как видим, получили решение, несовпадающее с решением, найденным первым способом.
Обозначим /> и получим />, т.е эти решения равносильны.
Способ 3.
Еще один способ опирается на теорему:
Пусть /> - произвольное решение диофантовауравнения
/>, />, тогда
множество решений уравнения в целыхчислах совпадает с множеством пар />, где />, />, где t – любое целое число.
Доказательство этого несложного фактаможно найти, например, в книге Бухштаба [2, стр. 114].
Опять же частное решение можно легкоотыскать с помощью алгоритма Евклида.
4.Нахождение решений произвольного ЛДУ.
Перейдем теперь к решению ЛДУ с /> неизвестных, т.е. уравнений вида />
/>
где все коэффициенты и неизвестные –целые числа и хотя бы одно />. Для существования решения потеореме 2, необходимо, чтобы/>
Положив
/>
перейдем к равносильному уравнению />
/> (*),
где/>/>. Пусть/>, /> - два ненулевых числа, таких, что /> Дляопределенности предположим, что/>, /> Разделив с остатком /> на />, получим представление />. Заменив /> на /> в уравнении(*), приведем его к виду />
/>
Перепишем это уравнение в виде />
/> (**)
где
/>, />.
Очевидно, что решения уравнения (*) и(**) связаны между собой взаимно однозначным соответствием и, таким образом,решив уравнение (**), несложно найти все решения уравнения (*). С другойстороны отметим, что
/> />
Отметим также, что
/>
Следовательно, за конечное числошагов уравнение (*) приведется к виду />
/> (***)
где числа /> (i = 1,...,n), которые не равнынулю, равны между собой по абсолютной величине. Из соотношения /> следует, что числа /> могут приниматьтолько значения 0,±1, причем не все из них равны нулю. Предположим, дляопределенности, />. Тогда уравнение (***) имеетследующее решение:
/>
где t2, t3, ..., tn — произвольныецелые числа. Отсюда, учитывая проведенные замены, получается и решениеуравнения (*). Отметим, что при получении решения уравнения (***) использовалсялишь факт, что />, поэтому, при выполнении алгоритмаможно остановиться на том шаге, когда хотя бы один из коэффициентов станетравным ±1.
5. Примерырешений задач.
1). Решить в целых числах уравнение
4x — 6y + 11z = 7, (4,6,11)=1.
Разделив с остатком -6 на 4, получим-6 = 4(-2) + 2. Представим исходное уравнение в виде
4(x — 2y) + 2y + 11z = 7.
После замены x = x — 2y этоуравнение запишется следующим образом
4x + 2y + 11z = 7.
Учитывая, что 11 = 2·5 + 1,преобразуем последнее уравнение:
4x + 2(y + 5z) + z = 7.
Положив y = y + 5z, получим
4x + 2y + z = 7.
Это уравнение имеет следующеерешение: x, y — произвольные целые числа, z = 7 — 4x — 2y.
Следовательно y = y — 5z =20x + 11y — 35, x = x + 2y = 41x + 22y- 70.
Таким образом, решение исходногоуравнения имеет вид
/>, где/>, /> - произвольные целые числа.
2). Решить в целых числах уравнение
/>
Разделим 5 на -4 с «остатком», />, преобразуемисходное уравнение к виду
/>.
Заменив /> получим />, следовательно
/>, является решением данного ЛДУ.
Список литературы
Башмакова, И.Г. Диофант и диофантовыуравнения [Текст]. – М.: «Наука», 1972 г. — 68 с.
Бухштаб, А. А. Теория чисел [Текст].- М.: Государственное учебно-педагогическое издательство министерствапросвещения РСФСР, 1960. — 378 с.
Виноградов, И.М. Основы теории чисел:Учебное пособие. 11-е изд. [Текст]. – СПб.: Издательство «Лань», 2006. — 176 с.
Гаусс, Карл Фридрих Труды по теориичисел. Под общей ред. Виноградова И.М. [Текст] – М.: Изд. академических наукСССР, 1959 г. — 980 с.
Гельфонд, А.О. Решение уравнений вцелых числах. Популярные лекции по математике, вып. [Текст]. М.: «Гостехиздат»,1957 г. — 66 с.
Давенпорт, Г. Введение в теорию чисел[Текст]: Пер. с английского Мороза Б.З. под ред. Линника Ю.В. – М.: «Наука»,1965 г. — 176 с.
Матисеевич, Ю.В. Десятая проблемаГильберта [Текст]. — М.: «Физматлит», 1973 г. — 224 с.
Михелович, Ш.Х. Теория чисел [Текст].– М.: «Высшая школа», 1962 г. — 260 с.
Соловьев, Ю. Неопределенные уравненияпервой степени [Текст]: Квант, 1992 г., №4.
Стройк, Д.Я. Краткий очерк историиматематики [Текст]. – М.: «Наука», 1990 г. — 256 с.
Для подготовки данной работы былииспользованы материалы с сайта revolution./