Линейные диофантовы уравнения (стр. 3 из 4)

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

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

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

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

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

По теореме о линейном разложении НОД, это означает, что найдутся такие

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

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

Замечание: особенно этот способ удобен, когда

или . Если, например, , , тогда 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. Представим исходное уравнение в виде