ГНОМОН. От фараонов до фракталов - Газале М.
ISBN 5-93972-171-0
Скачать (прямая ссылка):
Это простое свойство деления и послужило фундаментом, на котором Евклид построил свой алгоритм, действующий следующим образом.
Для определения НОД целых чисел ао и ai, где ао > запишем, следуя модели выражения (2.1),
а = bq + г,
(2.1)
(2.2а)
Подставив эти выражения в (2.1), получим
а — Pq +
d
(2.2 Ъ)
(а, Ъ) = {Ъ, г).
(2.3)
а0 = ai^o + ai = a2^i + аз
&2 — ^3^2 + аз = а4<7з + а$
ai > а2 &2 > а3
аз > а4 а4 > as
(2.4)
ai—1 — ^%qi— 1 + ^г+1? ^ ^г+1
&п—1 — ^nQn—i Н- 0*
Непрерывные дроби
45
Остаток ап = 0 обязательно возникнет при некотором значении п, поскольку убывающая последовательность ао > а>1 > > аз > <24 ... > ап может
содержать не более чем ао положительных целых чисел. Появление нулевого остатка говорит о том, что число ап является НОД для числа an_i и себя самого, т. е. (an_i, ап) = ап. Согласно уравнению (2.3) из вышеприведенной последовательности делений получаем
(«о, ai) = (ai, a2) = (a2, a3) = ... = (an_i, an).
Искомый НОД, таким образом, равен ап. Определим, например, наибольший общий делитель чисел 1785 и 374:
1785 = 374 х 4 + 289, 374 = 289 х 1 + 85, 289 = 85 х 3 + 34,
85 = 34 х 2 + 17,
34 = 17 х 2 + 0. Следовательно, (1785, 374) = 17.
Непрерывные дроби
Фп-1 = тогда урав-
нения (2.4) можно записать в виде
(2.5)
Фп—1
&П—1
Qn—1 + 0.
Или иначе:
1
46
Глава II
Такое разложение принято называть непрерывной (или цепной) дробью, а числа go, <7i, <72, ••• — неполными частными. Следуя предыдущей схеме, можно записать
Простые непрерывные дроби
Исходя из вышеизложенного, можно предложить для непрерывных дробей следующий общий вид:
ниже приведены поразительные примеры таких дробей (выражения (2.17) и (2.18)). Положив pi = 1 для всех г, получим частный случай непрерывных дробей — простые непрерывные дроби (ПНД). Если все q являются к тому же положительными целыми числами, то такая дробь называется регулярной непрерывной дробью (РНД). В дальнейшем для простых непрерывных
4+------±---
374/289
<7о = 4
1 н----,
289/85’
<7i = 1
3 + ~1— 85/34
42 = 3
(2.66)
<й = 2
q4 = 2
ИЛИ
1
(2.6с)
1
Ф — Qo +
Pi
(2.7)
Qi +
<72 +
Рз
<7з + .
Подходящие дроби
47
дробей (как регулярных, так и нерегулярных) мы будем использовать следующую форму записи:
Ьо, (7i, Q2, • • •, Qn] — Qo +
1
Qi +
1
<72 +
1
Qn-1 +
qn
(2.8)
можно легко показать, что
[(Zo, (Zi, (Z2, • • •, 9n] — Qo, [(Zi? 0.2, • • •, (Zn-i
9o +
1
a[<7o, <7b <72, • • •
<7i <7з
«<70, ?? ’ ^(Z2, ^ 5
(2.9)
Подходящие дроби
Несократимую дробь
— Ьо, (Zl, ^2, • • • , Qi\ —
Ni
Di
(2.10)
называют i-й подходящей дробью непрерывной дроби. Числа Ni и Di являются, соответственно, г-ми числителем и знаменателем этой непрерывной дроби. Возвращаясь к нашему численному примеру, получаем
?о =
4, — 4 + — — 5, 82 — 4 +
1
1
1 + -3
19 4 ’
?з=4 +
1
1 +
1
43 9 ’
1
2
$4 — 4 +
1
1 +
1
105 = 1785 22 374
1
48
Глава II
Доведя идею до логического завершения и введя «виртуальные» числители
iV_i = 1, JV_2 = 0, ?>-1=0, ?>-2 = 1, (2.11)
можно вывести два фундаментальных рекурсивных соотношения, которые в совокупности дают последовательные несократимые подходящие дроби:
Ni = Ni-2 + qiNi-i и Di = Di-2 + • (2-12)
Соответствующая процедура проиллюстрирована в таблице II. 1.
Таблица II. 1. Подходящие дроби
i -2 1 0 1 2 3 4
qi --- 4 1 3 2 2
0 1 4 5 19 43 105
А; 1 0 1 1 4 9 22
<5г --- 4 5 4,75 4,7 4,7(72)
Гюйгенс показал, что в общем случае
Ni-xDi - NiDi-i = (-1)\ (2.13)
В качестве упражнения читателю также предлагается самостоятельно убедиться в том, что если в непрерывной дроби (2.7) положить
N-1 = 1, N- 2 = 0, D-1 = 0, D-2 = 1 и ро = 1,
то числитель (Ni) и знаменатель (Di) подходящей дроби Si будут иметь следующий вид:
