Линейные диофантовы уравнения (стр. 2 из 4)
Аналогично получаем:
,…, 
.Мы видим, что
– общий делитель чисел 
, следовательно, поскольку 
, 
, 
, 
, то уравнение разрешимо в целых числах.Теорема 2. Пусть
- наибольший общий делитель коэффициентов . Диофантово уравнение имеет решение тогда и только тогда, когда 
. Число решений такого уравнения равно либо нулю, либо бесконечности.Докажем последовательно все три утверждения теоремы.
1). Пусть
. Для уравнения 
,где
, существуют целые числа: 
удовлетворяющие ему. Т.е. такие, что 
.Тогда
т. е.
- решение уравнения.2). Пусть теперь
не делит 
. Тогда левая часть уравнения при любых целых 
делится на , а правая на не делиться, так что равенство при целых значениях невозможно.3). Если
- упорядоченная n-ка чисел, удовлетворяющий уравнению, то например, все n-ки 
при 
также удовлетворяют этому уравнению и, таким образом, у нас либо совсем не будет решений, либо их будет бесконечное множество.
Если хоть одна пара коэффициентов взаимно простая, то
, и уравнение имеет бесчисленное множество решений.3. Нахождение решений для некоторых частных случаев ЛДУ.
Рассмотрим линейное уравнение с одной неизвестной, т.е. уравнение вида
Ясно, что решением данного уравнения будет
, и решение будет целым числом только в том случае, когда 
.3.2. ЛДУ с двумя неизвестными.
Рассмотрим теперь линейное уравнение с двумя неизвестными
, 
.Покажем несколько алгоритмов для нахождения решения.
Способ 1.
Пусть
Рассмотрим два случая:
а).
не делится на . В этом случае решений нет по теореме 2.б).
делится на , поделим на . 
; 
.Таким образом получили новое ЛДУ, с тем же множеством решений, но уже со взаимно-простыми коэффициентами. Поэтому далее мы будем рассматривать именно такие уравнения.
Рассмотрим
, 
. 
, перейдем к сравнению, 
.Т.к.
, то сравнение имеет единственное решение 
. 
; подставим в уравнение. 
; 
; 
, причем 
.Обозначим
.Тогда общее решение можно найти по формулам:
, где 
.Пример.
, 
.Найдем решение сравнения
; 
; 
, т.е. 
. 
; 
Получили общее решение:
, где .Способ 2.
Рассмотрим еще один способ нахождения решения ЛДУ с двумя неизвестными, а для этого рассмотрим уравнение вида
. Уравнения такого вида называются линейными однородными диофантовыми уравнениями (ЛОДУ). Выражая неизвестную 
, через неизвестную 
приходим к 
. Так как x должен быть целым числом, то 
, где 
- произвольное целое число. Значит 
. Решениями ЛОДУ являются n-ки вида 
, где . Множество всех таких n-ок называется общим решением ЛОДУ, любая же конкретная пара из этого множества называется частным решением.Рассмотрим теперь уравнение
, . Пусть n-ка 
его частное решение, а множество n-ок общее решение соответствующего ЛОДУ. Докажем предложение.Общее решение ЛДУ
, задается уравнениями , где .