Линейные диофантовы уравнения (стр. 3 из 4)
Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения
имеет именно такой вид, какой указан в формулировке предложения. Пусть 
- какое-нибудь решение уравнения . Тогда 
, но ведь и 
. Вычтем из первого равенства второе и получим: 
- однородное уравнение. Пишем сразу общее решение: 
, откуда получаем: 
. Доказательство завершено.Встает вопрос о нахождении частного решения ЛДУ.
По теореме о линейном разложении НОД, это означает, что найдутся такие
и 
из множества целых чисел, что 
, причем эти и мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство на 
и получим: 
, т.е. 
, 
.Таким образом, для нахождения общего решения находим общее решение ЛОДУ, частное решение ЛДУ и их складываем.
Замечание: особенно этот способ удобен, когда
или 
. Если, например, , 
, тогда n-ка 
, очевидно, будет частным решением ЛДУ. Можно сразу выписывать общее решение.Пример.
, 
.Найдем частное решение. Используем алгоритм Евклида.
; 
Получаем линейное разложение НОД:
, т.е 
. 
, 
Получили общее решение:
, где 
.Как видим, получили решение, не совпадающее с решением, найденным первым способом.
Обозначим
и получим 
, т.е эти решения равносильны.Способ 3.
Еще один способ опирается на теорему:
Пусть
- произвольное решение диофантова уравнения , , тогдамножество решений уравнения в целых числах совпадает с множеством пар
, где 
, 
, где t – любое целое число.Доказательство этого несложного факта можно найти, например, в книге Бухштаба [2, стр. 114].
Опять же частное решение можно легко отыскать с помощью алгоритма Евклида.
4. Нахождение решений произвольного ЛДУ.
Перейдем теперь к решению ЛДУ с
неизвестных, т. е. уравнений вида 
где все коэффициенты и неизвестные – целые числа и хотя бы одно
. Для существования решения по теореме 2, необходимо, чтобы 
Положив
перейдем к равносильному уравнению
(*),где
. Пусть 
, 
- два ненулевых числа, таких, что 
Для определенности предположим, что 
, 
Разделив с остатком на , получим представление 
. Заменив на 
в уравнении (*), приведем его к виду 
Перепишем это уравнение в виде
(**)где
, 
.Очевидно, что решения уравнения (*) и (**) связаны между собой взаимно однозначным соответствием и, таким образом, решив уравнение (**), несложно найти все решения уравнения (*). С другой стороны отметим, что
Отметим также, что
Следовательно, за конечное число шагов уравнение (*) приведется к виду
(***)где числа
(i = 1,...,n), которые не равны нулю, равны между собой по абсолютной величине. Из соотношения 
следует, что числа могут принимать только значения 0,±1, причем не все из них равны нулю. Предположим, для определенности, 
. Тогда уравнение (***) имеет следующее решение: 
где t2, t3, ..., tn - произвольные целые числа. Отсюда, учитывая проведенные замены, получается и решение уравнения (*). Отметим, что при получении решения уравнения (***) использовался лишь факт, что
, поэтому, при выполнении алгоритма можно остановиться на том шаге, когда хотя бы один из коэффициентов станет равным ±1. 1). Решить в целых числах уравнение
4x - 6y + 11z = 7, (4,6,11)=1.
Разделив с остатком -6 на 4, получим -6 = 4(-2) + 2. Представим исходное уравнение в виде