Линейное диофантово уравнение – это уравнение вида
a1 * x1 + a2 * x2 +…+ an *xn = b
где a1 , a2 , …, an и b – целые числа и решение x1 , x2 , … , xn тоже ищется во множестве целых чисел.
Сначала рассмотрим решение диофантова уравнения с двумя неизвестными [34]
a*x +b*y = c (3)
Для существования решений необходимо и достаточно, чтобы правая часть c делилась на наибольший общий делитель НОД(a,b) чисел a и b. Необходимость очевидна: поскольку левая часть равенства делится на НОД(a,b), то и правая часть этого равенства тоже должна делиться на это же число.
С помощью алгоритма Евклида помимо НОД(a,b) можно найти и такие числа r и s , для которых выполняется равенство
a*r + b*s = НОД(a,b)
Тогда частным решением уравнения (3) является следующая пара чисел:
X0 = r*c/ НОД(a,b)
Y0 = s*c/ НОД(a,b)
Рассмотрим решение однородного уравнения
a*r + b*s = 0
Разделим обе части равенства на НОД(a,b) .
(a/ НОД(a,b))*r + (b/ НОД(a,b))*s = 0 (4)
Заметим, что числа a/ НОД(a,b) и b/ НОД(a,b) целые и взаимно простые. Первое слагаемое равенства (4) делится на a/ НОД(a,b) – следовательно, и второе слагаемое тоже должно делиться на это же выражение. Но, поскольку числа a/ НОД(a,b) и b/ НОД(a,b) взаимно просты, число s должно делиться на число a/ НОД(a,b) . Значит, существует такое целое число t , что
s = ( a/ НОД(a,b) ) * t
тогда
r = - ( b/ НОД(a,b) ) * t
Итак, для любого t Î Z решением уравнения (3) является пара чисел
X = - ( b/ НОД(a,b) ) * t + X0
(5)
Y = ( a/ НОД(a,b) ) * t + Y0
(Это легко проверяется подстановкой этих равенств в (3) ).
a*X +b*Y = c (6)
Докажем, что других решений не существует. Действительно, предположим, что пара чисел u и v – некоторое решение уравнения (3). Тогда выполняется равенство
a*u +b*v = c
Вычтем это равенство из равенства (6):
a*(X-u) +b*(Y-v) = 0
Получено однородное уравнение с коэффициентами a и b . Общее решение этого уравнения имеет вид
X - u = - ( b/ НОД(a,b) ) * w
Y - v = ( a/ НОД(a,b) ) * w w Î Z.
Тогда, подставляя значения X и Y, получим
u = - ( b/ НОД(a,b) ) * t + X0 + ( b/ НОД(a,b) ) * w
v = ( a/ НОД(a,b) ) * t + Y0 - ( a/ НОД(a,b) ) * w w Î Z.
или
u = - ( b/ НОД(a,b) ) * z + X0
v = ( a/ НОД(a,b) ) * z + Y0
где z = (t - w ) Î Z.
Таким образом, решения u и v имеют такой же вид, как и (5).
Следствие. Линейная функция двух целых переменных a*x +b*y с целыми коэффициентами принимает множество значений вида НОД(a,b) * w, w Î Z.
Доказательство: Действительно, для каждого w Î Z уравнение
a*x +b*y = НОД(a,b) * w
имеет решение. С другой стороны, если правая часть уравнения (3) не представима в таком виде, т.е. не делится на НОД(a,b), то уравнение не имеет решений.
Теорема 1. Уравнение
a1*x1 +a2 *x2 +…+an *xn = c (7)
имеет решение тогда и только тогда, когда число c делится на НОД(a1,a2,…,an) . Общее решение этого уравнения имеет вид
x1 = g11 * t1 + g12 t2 + … + g1(n-1) * tn-1
… (8)
xn = gn1 * t1 + gn2 t2 + … + gn(n-1) * tn-1
где t1 , t2 , … tn-1 пробегают множество целых чисел Z .
Доказательство проведем методом математической индукции.
Для n=2 теорема уже доказана выше.
Предположим, что теорема верна для n=k.
Докажем теорему для n=k+1.
Сгруппируем в левой части уравнения два последних слагаемых.
a1*x1 +a2 *x2 +…+ (ak *xk + ak+1 *xk+1 ) = c
Выражение (ak *xk + ak+1 *xk+1) принимает значения вида НОД(ak, ak+1) * w , где w – некоторая переменная, пробегающая множество целых чисел. Подставим это выражение в исходное уравнение и получим следующее:
a1*x1 +a2 *x2 +…+ ak-1 *xk-1 + НОД(ak, ak+1) * w = c
Согласно предположению индукции, это уравнение имеет решение тогда и только тогда, когда число c делится на следующую величину
НОД(a1,a2,…,ak-1, НОД(ak,ak+1) ) = НОД(a1,a2,…,an)
и это решение имеет вид
x1 = g11 * t1 + g12 t2 + … + g1(k-1) * tk-1
…
xk-1 = g(k-1)1 * t1 + g(k-1)2 t2 + … + g(k-1)(k-1) * tk-1
w = gk1 * t1 + gk2 t2 + … + gk(k-1) * tk-1
где t1 , t2 , … tk-1 пробегают множество целых чисел Z .
Рассмотрим последнее уравнение, заменив w исходным выражением
(ak *xk + ak+1 *xk+1 ) = gk1 * t1 + gk2 t2 + … + gk(k-1) * tk-1
и решим это равенство относительно xk и xk+1 :
xk = -(ak+1/НОД(ak, ak+1))*tk + r*(gk1*t1 + gk2t2 + … + gk(k-1)*tk-1)/НОД(ak, ak+1)
xk+1 = (ak/НОД(ak,ak+1))*tk + s*(gk1*t1 + gk2t2 + … + gk(k-1)*tk-1)/НОД(ak, ak+1)
Здесь r, s – константы, которые находятся алгоритмом Евклида, а переменная tk пробегает множество целых чисел. Заменяя этими двумя равенствами в системе равенство для переменной w, получим систему равенств искомого вида
x1 = g11 * t1 + g12 t2 + … + g1(k-1) * tk-1
…
xk-1 = g(k-1)1 * t1 + g(k-1)2 t2 + … + g(k-1)(k-1) * tk-1
xk = -(ak+1/НОД(ak, ak+1))*tk + r*(gk1*t1 + gk2t2 + … + gk(k-1)*tk-1)/НОД(ak, ak+1)
xk+1 = (ak/НОД(ak,ak+1))*tk + s*(gk1*t1 + gk2t2 + … + gk(k-1)*tk-1)/НОД(ak, ak+1)
Конец доказательства.
Следствие. Линейная функция целых переменных a1*x1 +a2 *x2 +…+an *xn с целыми коэффициентами принимает множество значений вида
НОД(a1,a2,…,an) * w, w Î Z.
Дата: 2018-12-21, просмотров: 527.