Xreferat.com » Рефераты по математике » Линейные диофантовы уравнения

Линейные диофантовы уравнения

сразу общее решение: Линейные диофантовы уравнения Линейные диофантовы уравнения, откуда получаем:

Линейные диофантовы уравнения. Доказательство завершено.

Встает вопрос о нахождении частного решения ЛДУ.

Линейные диофантовы уравнения

По теореме о линейном разложении НОД, это означает, что найдутся такие Линейные диофантовы уравнения и Линейные диофантовы уравнения из множества целых чисел, что Линейные диофантовы уравнения, причем эти Линейные диофантовы уравнения и Линейные диофантовы уравнения мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство Линейные диофантовы уравнения на Линейные диофантовы уравнения и получим: Линейные диофантовы уравнения, т.е.Линейные диофантовы уравнения, Линейные диофантовы уравнения.

Таким образом, для нахождения общего решения находим общее решение ЛОДУ, частное решение ЛДУ и их складываем.

Замечание: особенно этот способ удобен, когда Линейные диофантовы уравнения или Линейные диофантовы уравнения. Если, например, Линейные диофантовы уравнения, Линейные диофантовы уравнения, тогда 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 с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: