Дипломная работа: Теория остатков
ax + by = c ,
где a , b , c Z ; a и b - не нули.
Попробуем порассуждать, глядя на это уравнение.
Пусть ( a , b ) = d . Тогда a = a 1 d ; b = b 1 d и уравнение выглядит так:
a 1 d· x + b 1 d· y = c , т.е. d· ( a 1 x + b 1 y ) = c .
Теперь ясно, что у такого уравнения имеется решение (пара целых чисел x и y ) только тогда, когда d | c . Пусть d | c . Поделим обе части уравнения на d , и всюду далее будем считать, что ( a , b ) = 1.
Рассмотрим несколько случаев.
Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение".
|
x = - |
b a |
y . |
Так как x должен быть целым числом, то y = at , где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt , at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.
Случай 2. Пусть теперь c 0. Этот случай закрывается следующей теоремой.
Теорема. Пусть ( a , b ) = 1, { x 0 , y 0 } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:
|
|
x = x 0 - bt y = y 0 + at . |
Таким образом, и в теории линейных диофантовых уравнений общее решение неоднородного уравнения есть сумма общего решения соответствующего однородного уравнения и некоторого (любого) частного решения неоднородного уравнения.
Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения ax + by = c . Тогда ax * + by * = c , но ведь и ax 0 + by 0 = c . Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:
a ( x *- x 0 ) + b ( y *- y 0 ) = 0
- однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x 0 = - bt , y *- y 0 = at , откуда моментально, используя навыки третьего класса средней школы, получаем:
|
|
x * = x 0- bt , y * = y 0 + at. |