То же рекуррентное соотношение (если отбросить в нем qq) показывает, что

Вт = ЯтВт-1 + (9)

Таким образом, числители и знаменатели подходяш;их дробей получаются по одинаковым обш;им правилам. Эти правила очень удобны для вычислений. Написав первые две подходяш;ие дроби, мы получим последуюш;ие подходяш;ие, применяя (8) и (9).

Например, непрерывная дробь для имеет вид .

1 3

Две первые подходяш;ие дроби равны, очевидно, -. Так как следуюш;ее неполное частное равно 1, то следуюш;ая подходя-

ш;ая дробь равна --- = -. Следуюш;ее неполное частное равно 2i ~\~ 1 о

4, поэтому следуюш;ая подходяш;ая дробь равна f =

4-3 + 2 14

Последнее неполное частное равно 2, значит, последняя подхо-

2-19 + 4 42 дящая дробь есть = -.

Между двумя последовательными подходяш;ими дробями имеется очень важное простое соотношение. Вот оно:

АтВт-1 - ВтАт-1 = (-1)"" (Ю)

Например, если т равно 1, то Ло = до? = 1, = QoQi + 1? 5i = gi, откуда

AiBo - BoAi = (gogi + 1) - gogi = 1. (11)

Чтобы доказать (10) в обш;ем случае, подставим А и из рекуррентных соотношений (8) и (9). Это дает

АтВт-1 ~ ВтАт-1 = {QmAm-l + Ат-2)Вт-1 ~

- {ЧтВт-1 + Вт-2)Ат-1 = -{Am-lBm-2 " Pm-lm-2)-

Следовательно, выражение в левой части (10), скажем Za, обладает свойством = -Аш-ь откуда А = -A i = А 2 = = ... = ±Ai, в конце берется знак плюс, если т нечетно, и знак минус, если т четно, поэтому вместо него можно поставить ( 1)-1 Хак как в силу (И) Ai = 1, отсюда следует обш;ий результат.

Из равенства (10) немедленно следует, что Am и Вт взаимно просты: любой их обгций множитель должен быть делителем

ПОДХОДЯЩИЕ ДАННОЙ НЕПРЕРЫВНОЙ ДРОБИ 87

1. Таким образом, дробь -, представляющая общую подхо-

дящую дробь, записана с наименьшими из возможных числителем и знаменателем. В частности, взяв т равным п, видим, что это верно и для прежней формулы (3), выражающей значение общей непрерывной дроби. Таким образом, мы доказали предложение, высказанное в конце п. 2.

Если рациональнее число j- разложить в непрерывную

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

этих чисел и величиной у? Легко установить, что подходящие

дроби поочередно меньше или больше, чем значение у. Чтобы

доказать это, перепишем соотношение (10) в виде

Ащ Ат-1 (~1) j-2

Вт В т-1 Bm-lBm

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

тельность, разность в (12) монотонно убывает при возрастании

т. Таким образом, - больше, чем -; - меньше, чем -, но Bi Bq В2 Bi

Ао As А2 Ai

больше, чем --; -- больше, чем --, но меньше, чем --, ..., i)o Bs В2 Bi

и, наконец, последняя подходящая дробь - = -. Отсюда сле-

Вп о 0 А2

дует, что все четные подходящие дроби меньше, чем

Bq В2

а а

-, а все нечетные - больше, чем -. о о

Можно доказать, что каждая подходящая дробь ближе к

окончательному значению чем предшествующие подходя-

щие. Доказательство несложно, но мы его здесь опускаем.

Другой интересный факт состоит в том, что подходящие

дроби являются «наилучшими из возможных» приближений к

дробями фиксированной сложности. Мы измеряем сложность

дроби величиной ее знаменателя, так что любая дробь, расположенная к 7 ближе, чем подходящая дробь -, имеет знаме-

b Вт

натель, больший Вт-

Чтобы проиллюстрировать эти свойства подходящих дро-

бей, рассмотрим непрерывную дробь для -. Последователь-

1 3 4 19 42 ными подходящими являются в представлении

1 2 3 14 31

десятичными дробями эти числа имеют вид

1; 1,5; 1,333...; 1,3571...; 1,3548...;

мы видим, что они поочередно меньше или больше окончательного числа и монотонно приближаются к нему.

5. Уравнение ах - by = 1. В (I, 8) было доказано, что если аиЬ - произвольные взаимно простые натуральные числа, то можно найти натуральные числа х и у, удовлетворяющие

уравнению ах - by = 1. Процесс разложения у в непрерывную

дробь дает точную конструкцию для чисел х иу. Предположим, что имеется непрерывная дробь

а 1 1

т = 90 + -Г"--

о qi+ Яп

Последняя подходящая дробь - равна самой дроби -. Пред-

Вп о

шествующая ей подходящая дробь удовлетворяет равен-

ству АпВп-1 - ВпАп-1 = или аВп-1 - bA-i =

(ввиду (10) из предыдущего пункта). Следовательно, если взять = Бп-ь У = Ап-1, мы получим решение в натуральных числах уравнения ах - by = (-1)~ Если п нечетно, то это - рассматриваемое уравнение. Если п четно, так что (-1)" = = - 1, мы все же можем решить уравнение с +1 одним из следующих двух способов (по существу, оба способа одинаковы). Один способ - взять X = b - Bn-i и у = а - A-i, тогда

ах - by = a{b - B-i) - b{a - A-i) = -aB-i + bA-i = 1. Другой способ - изменить непрерывную дробь, представив по-