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

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

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

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

Диофантовыназывают уравнение в целых числах вида где Р — многочлен от п переменных с целыми коэффициентами. Предметом изучения в этом параграфе будет служить линейное диофантово уравнение с двумя неизвестными где а.Ь и с — целые константы, ахи у — неизвестные, или переменные. Решением (более точно, частным решением) уравнения, как известно, называют набор значений переменных, обращающих его в верное равенство. Стоит задача описания всех решений уравнения (1) в целых числах.

Если один из коэффициентов при неизвестных равен нулю, то уравнение фактически содержит лишь одно неизвестное. Поэтому будем считать, что а ф. О иМО. Более того, при необходимости меняя знак переменной, можно без ограничения общности считать в этом случае, что Пусть d — наибольший общий делитель а и Ь. Тогда для любых целых хну левая часть уравнения ах + by делится на d. Если при этом с не делится на d, то уравнение В чссгъ древнегреческого математика Диофанта, жившего в веке. не имеет (целых) решений.

Если же с кратно d, т.е. с = qd для некоторого целого С|, то, положив а = aid, b = b\d и сократив на d, уравнение (1) сведем к виду в котором коэффициенты при неизвестных являются взаимно простыми числами.

Теорема 7. Уравнение (1) с взаимно простыми коэффициентами при неизвестных разрешимо в и,е.1ых чиыах. Рассмотрим сначала уравнение Построим цепочку делений с остатком Линейные диофантовы уравнения Последний ненулевой остаток, как известно, равен наибольшему общему делителю 1. Заметим, что каждый остаток г,- может быть представлен целочисленной лдаейной комбинацией . Действительно, Последнее равенство показывает, что пара целых чисел (a„,/3n) является решением (2).

Возможно вам будут полезны данные страницы:

Мощность цепи синусоидального тока. Понятие о коэффициенте мощности
Задача двойной интеграл. Определение. Основные свойства двойного интеграла
Пространственное строение молекул
Проекция вектора на ось. Скалярное произведение векторов

Очевидно, что пара целых чисел (сап, фп) — суть решение (1). Теорема доказана. Пример 1. Найти какие-нибудь целые а: и у, для которых Применив алгоритм Евклида к паре чисел 1000 и 73. получим цепочку равенств из которых получаем Ответом в данной задаче может служить пара Итак, мы теперь умеем находить частное решение уравнения (1) (в том случае, когда это диофантово уравнение разрешимо). О том, каким является общее решение (1) — множество всех (частных) решений, говорит Теорема 8.

Пусть а и Ь — взаимно простые

натуральные числа, {хо, Уо) — некоторое решение диофантова уравнения (1). Тогда множество всех решений (1) описывается формулами Линейные диофантовы уравнения Очевидно, что для любого целого t значения х и у, определяемые формулами (3), дают решение (1). Действительно, так как (хсьУо) удовлетворяет (1) по условию теоремы.

Цедимся теперь в том, что произвольное решение (1) имеет вид (3) для некоторого целого t. Вычтя из (1) почленно равенство ахо + Ьуо = с, получим равносильное уравнение а(х - яо) + Ну - уо) = 0, или Линейные диофантовы уравнения Из того, что а(х - а?о) кратно 6 и а взаимно просто с 6, следует (. для некоторого целого t имеем х-хо — bt, или х = xo + bt. Подставив выражение для х в (4), получим abt = b{yo - у) и, поскольку 6^0, справедливо равенство Теорема доказана. Пример 2. Общее решение рассматривавшегося выше уравнения таково