Теория остатков

1.3 Применения алгоритма Евклида

Пусть требуется решить линейное диофантово уравнение:

ax + by = c ,

где a , b , c ??Z ; a и b - не нули.

Попробуем порассуждать, глядя на это уравнение.

Пусть ( a , b ) = d . Тогда a = a ₁ d ; b = b ₁ d и уравнение выглядит так:

a ₁ d· x + b ₁ d· y = c , т.е. d· ( a ₁ x + b ₁ y ) = c .

Теперь ясно, что у такого уравнения имеется решение (пара целых чисел x и y ) только тогда, когда d | c . Пусть d | c . Поделим обе части уравнения на d , и всюду далее будем считать, что ( a , b ) = 1.

Рассмотрим несколько случаев.

Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение".

b

x = -

1

a	y .

Так как x должен быть целым числом, то y = at , где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt , at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.

Случай 2. Пусть теперь c ??0. Этот случай закрывается следующей теоремой.

Теорема. Пусть ( a , b ) = 1, { x ₀ , y ₀ } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:

?? ?? ??	x = x 0 - bt y = y 0 + at .

Таким образом, и в теории линейных диофантовых уравнений общее решение неоднородного уравнения есть сумма общего решения соответствующего однородного уравнения и некоторого (любого) частного решения неоднородного уравнения.

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения ax + by = c . Тогда ax * + by * = c , но ведь и ax ₀ + by ₀ = c . Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:

a ( x *- x ₀ ) + b ( y *- y ₀ ) = 0

- однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x ₀ = - bt , y *- y ₀ = at , откуда моментально, используя навыки третьего класса средней школы, получаем:

?? ?? ??	x * = x 0- bt , y * = y 0 + at.

?

Как же искать то самое частное решение { x ₀ , y ₀ }. Мы договорились, что ( a , b ) = 1. Это означает, что найдутся такие u и v из Z , что au + bv = 1, причем эти u и v мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv = 1 на c и получим: a ( uc ) + b ( vc ) = c , т.е. x ₀ = uc , y ₀ = vc .

Определение. Цепной (или, непрерывной) дробью называется выражение вида:



(Бедные наборщики в докомпьютерные времена буквально стрелялись, когда им приходилось набирать в книжках подобные многоэтажные выражения.) Договоримся называть числа q ₁ , q ₂ ,..., q _n ,... - неполными частными и считаем, что q ₁ ??Z , а q ₂ ,..., q _n ,... ??N . Числа называются подходящими дробями цепной дроби ??.

1

??1 = q 1 , ??2 , = q 1 +

1

1

q 2

, ??3 = q 1 +

1

q 2 + 1

1

q 3	, и т. д.

Цепная дробь может быть как конечной (содержащей конечное число дробных линий и неполных частных), так и бесконечной вниз и вправо (на юго-восток). В первом случае она, очевидно, представляет некоторое рациональное число, во втором случае - пока непонятно что она вообще из себя представляет, но ясно, что все ее подходящие дроби - рациональные числа.

Пусть ????Q , ??= a / b ; a , b ??Z , b > 0. Оказывается, что при этих условиях, указанный выше процесс разложения числа в цепную дробь всегда конечен и выполним с помощью достопочтенного и любимого нами алгоритма Евклида. Действительно, отдадим алгоритму числа a и b , и внимательно посмотрим, что получится.

a

a = bq 1 + r 1

т.е.

1

1

b

= q 1 +

1

b

b / r 1
	b = r 1 q 2 + r 2	т.е.

1

1

r 1

= q 2 +

1

r 1

r 1 / r 2
	r 1 = r 2 q 3 + r 3	т.е.

1

1

r 2

= q 3 +

1

r n -2

r 2 / r 3
. . . . . . .
	r n -2 = r n -1 q n + r n	т.е.

1

1

r n -1

= q n +

1

r n -1

r n -1 / r n
	r n -1 = r n q n +1	т.е.

1

r n	= q n +1 .

Значит:

где q ₁ , q ₂ ,..., q _{n +1} - как раз те самые неполные частные из алгоритма Евклида (вот откуда название этих чисел в цепных дробях). Таким образом, в случае рационального числа a / b , процесс разложения в цепную дробь конечен и дробь содержит не более b этажей. Наиболее одаренные читатели в этом месте уже поняли, что основная теорема о цепных дробях для рациональных чисел оказалась почти доказана (не доказали только единственность разложения, но она в случае конечных цепных дробей почти очевидна - приравняйте две цепных дроби и, рассуждая по индукции, получите, что у равных дробей совпадают все неполные частные).

Пример. Пример заимствован из книги И. М. Виноградова "Основы теории чисел". Итак: разложить 105/38 в цепную дробь.

Включаем алгоритм Евклида:

105 = 38 · 2 + 29

38 = 29 · 1 + 9

29 = 9 · 3 + 2

9 = 2 · 4 + 1

2 = 1 · 2

Неполные частные я специально подчеркнул потому, что теперь для написания ответа нужно аккуратно расположить их подряд на этажах цепной дроби перед знаками плюс:

2 Делимость в кольцах