Курсовая работа: Линейные диофантовы уравнения

Курсовая работа

Выполнил студент 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 et delectables 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 с.

©2007—2016 Пуск!by | По вопросам сотрудничества обращайтесь в contextus@mail.ru