Непрерывные дроби и их связь с алгоритмом Евклида

Пусть a - любое вещественное число. Обозначим буквою q₁ наибольшее целое число, не превосходящее a. При нецелом a имеем ; a₂ > 1.

; a₃ > 1,

…

; a_s > 1,

ввиду чего получаем следующее разложение a в непрерывную дробь:

(1)

Если a - иррациональное, то и всякое a₁ - иррациональное (при рациональном a_s, ввиду (1) рациональным оказалось бы и a и указанный процесс может быть неограниченно продолжен.

Если же a - рациональное и, следовательно, может рыть представлено рациональной несократимой дробью с положительным знаменателем, то указанный процесс будет конечен и может быть выполнен с помощью алгоритма Евклида. Действительно, имеем:

a = bq₁ + r₂; ,

b = r₂q₂ + r₃; ,

…

r_n-2 = r_n-1q_n-1 + r_n; ,

r_n-1 = r_nq_n; ,

.

Числа q₁, q₂, …, участвующие в разложении числа a в непрерывную дробь, называются неполными частными (в случае рационального a это будут, неполные частные последовательных делений алгоритма Евклида), дроби же

называются подходящими дробями.

Весьма простой закон вычисления подходящих дробей получим, заметив, что d_s (s > 1) получается из d_s-1 заменой в буквенном выражении для d_s-1 числа q_s-1 числом .

Доказательство: Полагая ради единообразия Р₀ = 1, Q₀ = 0, мы можем последовательно представить подходящие дроби в следующем виде (здесь равенство пишем, желая обозначить A символом P_s, а В - символом Q_s):

,

,

и т.д. и вообще при s > 1

. (2)

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

P_s = q_sP_s-1 + P_s-2, Q_s = q_sQ_s-1 + Q_s-2. (3)

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

Пример: Разложим в непрерывную дробь несократимую дробь . Здесь имеем

				105	38
				76	2
			38	29
			29	1
		29	9
		27	3
	9	2
	8	4
2	1
2	2
0

Поэтому указанная выше схема дает:

Теорема 1: При s > 0 имеем P_sQ_s-1 - Q_sP_s-1 = (-1)^s.

При s > 1 имеем .

Доказательство: Приняв обозначение h_s = P_sQ_s-1 - Q_sP_s-1, мы при s = 1 получим h₁ = q₁?0 - 1?1 = -1, а при s > 1 с помощью равенств (3) найдем h_s = -h_s-l. Отсюда получим h_s = (-1)^s. Пользуясь же этим равенством при s > 1, легко найдем

.

Теорема 2: Пусть 1 < s, а если a - рациональная несократимая дробь с положительным знаменателем, то пусть также s < n. Тогда a лежит между d_s-1 и d_s, причем ближе к d_s нежели к d_s-1.

Доказательство: Заменив в равенстве (2) число q_s числом , получим

,

,

,

откуда убеждаемся, что первая из разностей, стоящих в скобках, и по знаку противоположна второй и численно (ввиду Q_s > Q_s-1) меньше последней. А этим и доказываются наши утверждения.

Глава 2