Непрерывные дроби
Исторически непрерывные, или цепные дроби появились в связи с необходимости найти наилучшее приближение вещественного числа с помощью числа рационального. Так, при конструировании зубчатых передач для передачи вращения с одного колеса на другое требуется нарезать на одном из них \(q\) зубцов, а на другом — \(p\), так чтобы отношение \(\frac{p}{q}\) как можно лучше приближало заранее заданное отношение угловых скоростей \(\omega\). При этом ясно, что чем меньше зубцов нужно будет нарезать, тем это будет выгоднее. Интересно, что к такой же задаче сводится и установление длины года — ведь Земля совершает оборот вокруг Солнца за \(365.24219878\ldots\) суток, а это число иррациональное. Давайте же посмотрим, что такое цепные дроби и как они связаны с алгоритмом Евклида нахождения наибольшего общего делителя двух чисел.
Определение. Непрерывной (или цепной) дробью называется выражение вида
\[q_1+\frac{1}{q_2+\frac{1}{q_3+\ddots+\frac{1}{q_n+\ddots}}}\]Непрерывная дробь может быть как конечной, так и бесконечной.
Числа \(q_1,q_2,\ldots\), участвующие в разложении числа \(\alpha\) в непрерывную дробь, называются неполными частными.
Иногда непрерывную дробь обозначают следующим образом (с помощью неполных частных): \([q_1,q_2,q_3,\ldots,q_s,\ldots]\).
Возьмем произвольное вещественное число \(\alpha\). Пусть \(q_1\) — целая часть числа \(\alpha\) (\(q_1=[\alpha]\) — наибольшее целое число, не превосходящее \(\alpha\)). Если число \(\alpha\) не целое, то получим \(\alpha=q_1+\frac{1}{\alpha_2}\), \(\alpha_2>1\). Если \(\alpha_2\) не является целым числом, то для него также можно найти целую часть и найти число \(\alpha_3\) и т.д.:
\[\begin{array}{ll} \alpha_2=q_2+\frac{1}{\alpha_3}; & \alpha_3>1, \[2mm] \ldots & \ \alpha_{s-1}=q_{s-1}+\frac{1}{\alpha_{s}}; & \alpha_{s}>1, \end{array}\]откуда и получаем разложение \(\alpha\) в непрерывную дробь:
\[q_1+\frac{1}{q_2+\frac{1}{q_3+\ddots+\frac{1}{q_{s-1}+\frac{1}{\alpha_s}}}}.\]Ясно, что если число \(\alpha\) иррационально, то непрерывная дробь будет бесконечной. Действительно, любая конечная цепная дробь является рациональным числом.
Пример 1. Разложим в непрерывную дробь число \(\sqrt{3}\).
\([\sqrt{3}]=1\), поэтому
\[\sqrt{3}=1+\frac{1}{q_2};\quad q_2=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2}.\]\(\left[\frac{\sqrt{3}+1}{2}\right]=1\), следовательно,
\[\frac{\sqrt{3}+1}{2}=1+\frac{1}{\sqrt{3}-1}=\sqrt{3}+1;\]\([\sqrt{3}+1]=2\), поэтому
\[\sqrt{3}+1=2+\frac{1}{q_4};\quad q_4=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2},\]т.е. \(q_2=q_4\). Следовательно, неполные частные также будут повторяться. И разложение \(\sqrt{3}\) в непрерывную дробь имеет вид
\[\sqrt{3}=[1;1,2,1,2,1,2,\ldots]\]Если же число \(\alpha\) рационально, то оно представимо конечной непрерывной дробью. Разложить \(\alpha\) в непрерывную дробь в этом случае можно с помощью алгоритма Евклида.
\[\begin{array}{ll} a=bq_1+r_1; & \frac{a}{b}=q_1+\frac{r_1}{b}=q_1+\frac{1}{\frac{b}{r_1}}, \[3mm] b=r_1q_2+r_2; & \frac{b}{r_1}=q_2+\frac{r_2}{r_1}=q_2+\frac{1}{\frac{r_1}{r_2}}, \[3mm] r_1=r_2q_3+r_3; & \frac{r_1}{r_2}=q_3+\frac{r_3}{r_2}=q_3+\frac{1}{\frac{r_2}{r_3}}, \[3mm] \ldots & \ r_{n-2}=r_{n-1}q_n+r_n; & \frac{r_{n-2}}{r_{n-1}}=q_n+\frac{r_n}{r_{n-1}}=q_n+\frac{1}{\frac{r_{n-1}}{r_n}}, \[3mm] r_{n-1}=r_nq_{n+1}; & \frac{r_{n-1}}{r_n}=q_{n+1}. \end{array}\]Отсюда последовательной заменой каждой дроби
\[\frac{b}{r_1},\frac{r_1}{r_2},\ldots,\frac{r_{n-2}}{r_{n-1}},\frac{r_{n-1}}{r_n}\]на ее соответствующее выражение, получается представление
\[\frac{a}{b}=q_1+\frac{1}{q_2+\frac{1}{q_3+\ddots+\frac{1}{q_n}}}.\]Определение. Дроби
\[\delta_1=\frac{P_1}{Q_1}=q_1,\quad \delta_2=\frac{P_2}{Q_2}=q_1+\frac{1}{q_2},\quad \delta_3=\frac{P_3}{Q_3}=q_1+\frac{1}{q_2+\frac{1}{q_3}},\quad \ldots\]называются подходящими дробями.
Теорема. Для подходящих дробей при \(s>1\) справедливо соотношение
\[\delta_s=\frac{P_s}{Q_s}=\frac{q_sP_{s-1}+P_{s-2}}{q_sQ_{s-1}+Q_{s-2}}.\]Другими словами, числители и знаменатели подходящих дробей можно последовательно находить по формулам
\[P_s= q_sP_{s-1}+P_{s-2},\quad Q_s= q_sQ_{s-1}+Q_{s-2}.\]Доказательство. Доказывать будем по индукции. Проверим базу индукции. Положим \(P_0=1\), \(Q_0=0\). Тогда поскольку \(\delta_s\) получается из \(\delta_{s-1}\) заменой в выражении для \(\delta_{s-1}\) числа \(q_{s-1}\) на \(q_{s-1}+\frac{1}{q_s}\), имеем
\[\frac{P_1}{Q_1}=\frac{q_1}{1},\] \[\frac{P_2}{Q_2}=q_1+\frac{1}{q_2}=\frac{q_1+\frac{1}{q_2}}{1}=\frac{q_1q_2+1}{q_2\cdot1+0}=\frac{q_2P_1+P_0}{q_2Q_1+Q_0}.\]Предположим теперь, что справедливо равенство
\[\frac{P_k}{Q_k}=\frac{q_kP_{k-1}+P_{k-2}}{q_kQ_{k-1}+Q_{k-2}}.\]Тогда
\[\frac{P_{k+1}}{Q_{k+1}}=\frac{\left( q_k+\frac{1}{q_{k+1}}\right) P_{k-1}+P_{k-2}}{\left( q_k+\frac{1}{q_{k+1}}\right) Q_{k-1}+Q_{k-2}}=\] \[=\frac{q_{k+1}(q_kP_{k-1}+P_{k-2})+P_{k-1}}{ q_{k+1}(q_kQ_{k-1}+Q_{k-2})+Q_{k-1}}=\frac{q_{k+1}P_k+P_{k-1}}{ q_{k+1}Q_k+Q_{k-1}}.\]Тем самым, для \(\delta_{k+1}\) справедливо равенство того же вида. Теорема доказана.
Вычисления \(P_k\) и \(Q_k\) удобно производить с помощью следующей таблицы:
Замечание. Последний столбец пишем только в том случае, когда \(\alpha\) — несократимая дробь с положительным знаменателем: \(\alpha=\frac{a}{b}\).
Пример 2. Разложим в непрерывную дробь несократимую дробь \(\frac{125}{92}\):
Получаем непрерывную дробь:
\[\frac{125}{92}=1+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{2+\frac{1}{2}}}}}}.\]Таблица выглядит следующим образом:
Таким образом, подходящие дроби будут следующие:
\[\delta_1=1,\quad \delta_2=\frac{3}{2},\quad \delta_3=\frac{4}{3},\quad \delta_4=\frac{15}{11},\quad \delta_5=\frac{19}{14},\quad \delta_6=\frac{53}{39}.\]В случае же, когда числитель и знаменатель дроби не взаимно простые (\(\text{НОД}(a,b)=d\ne1\)), в последнем столбце таблицы будут стоять числитель и знаменатель несократимой дроби, равной данной дроби \(\frac{a}{b}\).
Пример 3. Разложим в непрерывную дробь \(\frac{525}{231}\):
\[\frac{525}{231}=\frac{25\cdot21}{11\cdot21}=\frac{25}{11}.\]Утверждение 1.
1) При \(s>0\) имеем
\[P_sQ_{s-1}-Q_sP_{s-1}=(-1)^s.\]2) При \(s>0\) имеем
\[\delta_s-\delta_{s-1}=\frac{(-1)^s}{Q_sQ_{s-1}}.\]Доказательство. Действительно, при \(s=1\) получаем
\[P_1Q_0-P_0Q_1=q_1\cdot0-1\cdot1=-1.\]Далее из равенств
\[P_s= q_sP_{s-1}+P_{s-2},\quad Q_s= q_sQ_{s-1}+Q_{s-2}\]получаем
\[P_sQ_{s-1}-Q_sP_{s-1}=-(P_{s-1}Q_{s-2}-Q_{s-1}P_{s-2}),\]откуда сразу же следует требуемое.
Вторая часть утверждения получается следующим образом:
\[\delta_s-\delta_{s-1}=\frac{P_s}{Q_s}-\frac{P_{s-1}}{Q_{s-1}}=\frac{P_sQ_{s-1}-P_{s-1}Q_s}{Q_sQ_{s-1}}=\frac{(-1)^s}{Q_sQ_{s-1}}.\]Следствие. Линейное представление наибольшего общего делителя чисел \(a\) и \(b\) получается из равенства
\[P_{n+1}Q_{n}-Q_{n+1}P_{n}=(-1)^{n+1}\]домножением на \(\text{НОД}(a,b)=d\), поскольку \(a=d\cdot P_{n+1}\), \(b=d\cdot Q_{n+1}\).
Пример 4. Приведем линейное представление наибольшего общего делителя чисел \(525\) и \(231\) (см. пример 3):
\[25\cdot4\cdot21-11\cdot9\cdot21=(-1)^4\cdot21\]или
\[4\cdot525-9\cdot231=21.\]Утверждение 2. Пусть \(s>1\), а если \(\alpha\) — рациональная несократимая дробь \(\alpha=\frac{a}{b}\) с положительным знаменателем, то пусть также \(s < n+1\). Тогда \(\alpha\) лежит между \(\delta_{s-1}\) и \(\delta_s\), причем ближе к \(\delta_s\), чем к \(\delta_{s-1}\).
Доказательство. Заменим в равенстве
\[\delta_s=\frac{P_s}{Q_s}=\frac{q_sP_{s-1}+P_{s-2}}{q_sQ_{s-1}+Q_{s-2}}\]\(q_s\) на \(q_s+\frac{1}{\alpha_{s+1}}\), получим
\[\alpha=\frac{\alpha_{s+1}P_s+P_{s-1}}{\alpha_{s+1}Q_s+Q_{s-1}},\] \[\alpha\alpha_{s+1}Q_s+\alpha Q_{s-1}-\alpha_{s+1}P_s-P_{s-1}=0,\] \[\alpha_{s+1}Q_s\left(\alpha-\frac{P_s}{Q_s}\right)+Q_{s-1}\left(\alpha-\frac{P_{s-1}}{Q_{s-1}}\right)=0,\]откуда ясно, что первая из разностей, стоящих в скобках, по знаку противоположна второй и численно меньше (так как \(Q_s>Q_{s-1}\)), что и доказывает наше утверждение.
Литература
- Баврин И.И., Фрибус Е.А. Занимательные задачи по математике.
- Виноградов И.М. Основы теории чисел.
- Нестеренко Ю.В., Никишин Е.М. Очерк о цепных дробях, Квант, 1983. – №5. – С. 16—20; №6. – С. 26—30.
