85000 (612455), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

.

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 с.

Для подготовки данной работы были использованы материалы с сайта http://revolution.allbest.ru/

Характеристики

Список файлов курсовой работы