3.2. ЛДУ с двумя неизвестными.

Рассмотрим теперь линейное уравнение с двумя неизвестными

, .

Покажем несколько алгоритмов для нахождения решения.

Способ 1.

Пусть

Рассмотрим два случая:

а). не делится на . В этом случае решений нет по теореме 2.

б). делится на , поделим на .

;

.

Таким образом получили новое ЛДУ, с тем же множеством решений, но уже со взаимно-простыми коэффициентами. Поэтому далее мы будем рассматривать именно такие уравнения.

Рассмотрим , .

, перейдем к сравнению,

.

Т.к. , то сравнение имеет единственное решение .

; подставим в уравнение.

;

;

, причем .

Обозначим .

Тогда общее решение можно найти по формулам: , где .

Пример. , .

Найдем решение сравнения ;

;

, т.е.

.

;

Получили общее решение: , где .

Способ 2.

Рассмотрим еще один способ нахождения решения ЛДУ с двумя неизвестными, а для этого рассмотрим уравнение вида . Уравнения такого вида называются линейными однородными диофантовыми уравнениями (ЛОДУ). Выражая неизвестную , через неизвестную приходим к . Так как x должен быть целым числом, то, где - произвольное целое число. Значит. Решениями ЛОДУ являются n-ки вида , где . Множество всех таких n-ок называется общим решением ЛОДУ, любая же конкретная пара из этого множества называется частным решением.

Рассмотрим теперь уравнение , . Пусть n-ка его частное решение, а множество n-ок общее решение соответствующего ЛОДУ. Докажем предложение.

Общее решение ЛДУ , задается уравнениями , где .

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения имеет именно такой вид, какой указан в формулировке предложения. Пусть - какое-нибудь решение уравнения . Тогда , но ведь и . Вычтем из первого равенства второе и получим:

- однородное уравнение. Пишем сразу общее решение: , откуда получаем:

. Доказательство завершено.

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

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

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

Замечание: особенно этот способ удобен, когда или . Если, например, , , тогда n-ка , очевидно, будет частным решением ЛДУ. Можно сразу выписывать общее решение.

Пример. , .

Найдем частное решение. Используем алгоритм Евклида.

;

Получаем линейное разложение НОД:

, т.е .

,

Получили общее решение: , где .

Как видим, получили решение, не совпадающее с решением, найденным первым способом.

Обозначим и получим , т.е эти решения равносильны.

Способ 3.

Еще один способ опирается на теорему:

Пусть - произвольное решение диофантова уравнения

, , тогда

множество решений уравнения в целых числах совпадает с множеством пар , где , , где t - любое целое число.

Доказательство этого несложного факта можно найти, например, в книге Бухштаба [2, стр. 114].

Опять же частное решение можно легко отыскать с помощью алгоритма Евклида.