1111

2 +----.

1+ 3+ 1+ 4

Числа 2, 1, 3, 1, 4 называются элементами непрерывной дроби, или неполными частными; они служат неполными частными в последовательных шагах алгоритма Евклида, применяемого к числителю и знаменателю исходной дроби. Полные частные - 67 24 19 5

это сами числа -, -, -, -. Каждое из них разлагается в

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

24 1 1 1 о 1 1

19~ зТГТ4 У~ TTi*

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

а 111 7 = 5+--... -,

о г + S + W

где элементы 5, г, s, ,,w являются натуральными числами. Последний элемент, w в предыдуп1;ей записи, должен быть больше 1, так как это последнее частное в алгоритме Евклида.

Легко доказать, что имеется только одно представление данного рационального числа непрерывной дробью. Действительно, предположим, что

а 11 ,11

7 = 5 +--... = q +---;- ...,

b r+ s+ г+ +

где q, г, s ... - натуральные числа, последнее из которых больше 1. Дроби, которые прибавляются в левой части к 5, а в правой части к 5, меньше 1. Поэтому числа 5 и 5 равны целой части рационального числа и, следовательно, q = q. Вычитая

qvL q VL переходя к обратной дроби, получаем г Н- ... = г +

+ -j-- ... Аналогичное рассуждение показывает, что г = г и S +

так далее.

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

2] ОБЩАЯ НЕПРЕРЫВНАЯ ДРОБЬ 81

нии рациональных чисел. Вот примеры:

1711 iii

11 ~ 1+ 1+ 5 31 ~ 2+ 1+ 4+ 2 • Если рациональное число, как во втором примере, меньше 1, то первое неполное частное равно О, и мы его опускаем.

2. Общая непрерывная дробь. Непрерывные дроби оказываются очень полезными в теории чисел; используя их, часто можно дать точную конструкцию для решения задачи, в то время как другими методами доказывается лишь существование такого решения.

Представим общую непрерывную дробь в виде

qi+ q2+ Qn

Прежде чем исследовать арифметические свойства непрерывных дробей, нужно установить некоторые чисто алгебраические соотношения. Эти соотношения не зависят от природы элементов до? 9ь • • •? Мы будем поэтому обращаться с этими элементами как с переменными, не обязанными быть натуральными числами.

Если шаг за шагом вычислять значение непрерывной дроби (1), то, в конце концов, для нее, очевидно, получится выражение, являющееся отношением двух сумм, составленных из различных произведений чисел до? Qi? • • •? Яп- Если п равно 1, мы имеем

, 1 qoqi + 1 9о Н--=-.

qi qi

Если п равно 2, получаем

1 92 909192 + 90 + 92

91+ 92 " 9192 + 1 " 9192 + 1

Значение 9i + мы получили из предыдущего вычисления,

подставив qi и q2 вместо qo и qi. Аналогично при п = 3 имеем

, 1 1 1 , 9293 + 1

9о + - - - = 9о +

91+ 92+ 9з 919293 + 9i + 9з

9o9i9293 + 9o9i + 9о9з + 929з + 1 919293 + 91 + 93

Здесь мы снова использовали результат предшествующего шага.

Ясно, что, продолжая таким образом, мы можем найти значение любой непрерывной дроби. Будем обозначать числитель непрерывной дроби (1), вычисленный таким способом, через 9о? 9ь • • • ? 9п]- Таким образом,

qo] = 90, [go, qi] = qoqi + 1, ко, 91,2] = qoqiq2 + qo + 92, 90,9i,92,93] = 9o9i9293 + 9o9i + 9о9з + 929з + 1, • • •

Мы видели, что в рассмотренных случаях выражение, получаемое для знаменателя непрерывной дроби, равно [91, 92, ..., 9п. • Это верно и в общем случае. Действительно, если посмотреть на третий шаг (довольно типичный) в (2), то мы увидим, что

знаменателем результата становится числитель qi + -, поэтому знаменатель равен [91,92,93]-

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

9о +

91 +

9о, 9i, • • •, 9п

91,92,... ,9п

Из вычисления в (2) ясно, как строится функция [9о,91,92,9з

91,92,9з] и [92,9з]- Это вычисление дает

.90, 91, 92, 9з] = 9о[91,92,9з

.91,92

Такое же соотношение имеет место и в общем случае:

9o,9i,...,9n] = 9o[9i,...,9n] + [9i, 92, • • •, 9п]. (4)

Это рекуррентное соотношение шаг за шагом определяет функцию «квадратные скобки». Формула (4) применима, начиная с п = 2. Если при п = 1 второй скобке в равенстве (4) приписать значение 1, то это соотношение можно будет применять и при п = 1. Действительно, в этом случае получаем верное равенство

9о, 9i] = 9o[9i] + 1 = 9o9i + 1-В качестве иллюстрации это правило можно применить к последнему примеру, рассмотренному в конце п. 1. Мы имеем

4, 2] = 4 . 2 + 1 = 9, 1,4,2] = 1.[4,2] + [2] = 9 + 2 = 11, 2,1,4, 2] = 2 • [1,4, 2] + [4, 2] = 2 • 11 + 9 = 31.