Учебная работа № 1764. Линейные диофантовы уравнения
Курсовая работа
Выполнил студент 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]
Первое общее решение уравнения первой степени
В 1624 г. в публикуется книга французского математика Баше де Мезирьяка «Problẻmes plaisans et delectables que se font par les nombres». Баше де Мезирьяк для решения уравнения
После Баше де Мезирьяка в XVII и XVIII веках различные правила для решения неопределенного уравнения 1й степени с двумя неизвестными давали Роль, Эйлер, Саундерсон и другие математики.
Цепные дроби к решению таких уравнений были применены Лагранжем, который, однако, замечает, что фактически это тот же способ, который был дан Баше де Мезирьяком и другими математиками, рассматривавшими неопределенные уравнения до него. Неопределенные уравнения 1й степени стали записываться и решаться в форме сравнения значительно позже, начиная с Гаусса. [2]
В августе 1900 г. в Париже состоялся II Международный конгресс математиков. 8 августа Д.Гильберт прочитал на нем доклад «Математические проблемы». Среди 23 проблем, решение которых (по мнению Д.Гильберта) совершенно необходимо было получить в наступающем XX в., десятую проблему он определил следующим образом:
«Пусть задано диофантово уравнение с произвольным числом неизвестных и рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых числах». [7]
Гипотезу, что такого способа нет, первым выдвинул (с достаточным на то основанием) американский математик М.Дэвис в 1949 г. Доказательство этой гипотезы растянулось на 20 лет последний шаг был сделан только в 1970 г. Юрием Владимировичем Матиясеевичем, на первом году аспирантуры он показал алгоритмическую неразрешимость 10 проблемы Гильберта.
Однако, если про произвольное диофантово уравнения нельзя сказать, имеет ли оно целые корни, или нет, то проблема существования целых корней ЛДУ решена. Приведем теоремы, пользуясь которыми всегда можно сказать, имеет ли целые решения данное ЛДУ или нет.
Теорема 1. При взаимно простых коэффициентах
имеет решение в целых числах.
Доказательство. Обозначим через
имеет решение в целых числах.
В множестве
Пусть
Мы подобрали целые значения:
Аналогично получаем:
Мы видим, что
Теорема 2. Пусть
Докажем последовательно все три утверждения теоремы.
1). Пусть
где
Тогда
т. е.
2). Пусть теперь
3). Если
также удовлетворяют этому уравнению и, таким образом, у нас либо совсем не будет решений, либо их будет бесконечное множество.
Если хоть одна пара коэффициентов взаимно простая, то
3. Нахождение решений для некоторых частных случаев ЛДУ.
Рассмотрим линейное уравнение с одной неизвестной, т.е. уравнение вида
Ясно, что решением данного уравнения будет
3.2. ЛДУ с двумя неизвестными.
Рассмотрим теперь линейное уравнение с двумя неизвестными
Покажем несколько алгоритмов для нахождения решения.
Способ 1.
Пусть
Рассмотрим два случая:
а).
б).
Таким образом получили новое ЛДУ, с тем же множеством решений, но уже со взаимнопростыми коэффициентами. Поэтому далее мы будем рассматривать именно такие уравнения.
Рассмотрим
Т.к.
Обозначим
Тогда общее решение можно найти по формулам:
Пример.
Найдем решение сравнения
Получили общее решение:
Способ 2.
Рассмотрим еще один способ нахождения решения ЛДУ с двумя неизвестными, а для этого рассмотрим уравнение вида
Рассмотрим теперь уравнение
Общее решение ЛДУ
Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения
Встает вопрос о нахождении частного решения ЛДУ.
По теореме о линейном разложении НОД, это означает, что найдутся такие
Таким образом, для нахождения общего решения находим общее решение ЛОДУ, частное решение ЛДУ и их складываем.
Замечание: особенно этот способ удобен, когда
Пример.
Найдем частное решение. Используем алгоритм Евклида.
Получаем линейное разложение НОД:
Получили общее решение:
Как видим, получили решение, не совпадающее с решением, найденным первым способом.
Обозначим
Способ 3.
Еще один способ опирается на теорему:
Пусть
множество решений уравнения в целых числах совпадает с множеством пар
Доказательство этого несложного факта можно найти, например, в книге Бухштаба [2, стр. 114].
Опять же частное решение можно легко отыскать с помощью алгоритма Евклида.
4. Нахождение решений произвольного ЛДУ.
Перейдем теперь к решению ЛДУ с
где все коэффициенты и неизвестные – целые числа и хотя бы одно
Положив
перейдем к равносильному уравнению
где
Перепишем это уравнение в виде
где
Очевидно, что решения уравнения (*) и (**) связаны между собой взаимно однозначным соответствием и, таким образом, решив уравнение (**), несложно найти все решения уравнения (*). С другой стороны отметим, что
Отметим также, что
Следовательно, за конечное число шагов уравнение (*) приведется к виду
где числа
где t2, t3, …, tn произвольные целые числа. Отсюда, учитывая проведенные замены, получается и решение уравнения (*). Отметим, что при получении решения уравнения (***) использовался лишь факт, что
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 с.