Цепная дробь¶

Цепная дробь (также непрерывная дробь) — это математическое выражение, представляющее собой последовательность вложенных дробей, где числитель каждой последующей дроби является целым числом (обычно единицей), а знаменатель состоит из целого числа и следующей дроби. В общем виде цепная дробь записывается как:

\[ a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ddots}}} \]

где \(a_0\) — целое число (может быть отрицательным), а \(a_1, a_2, a_3, \dots\) — положительные целые числа, называемые неполными частными или элементами цепной дроби. Цепные дроби применяются в теории чисел, приближённых вычислениях, криптографии и других областях математики.

¶История

Первые упоминания о цепных дробях встречаются в работах древнегреческих математиков. Евклид (III век до н. э.) в «Началах» описал алгоритм нахождения наибольшего общего делителя (алгоритм Евклида), который по сути порождает последовательность неполных частных, образующих цепную дробь для рационального числа. Однако систематическое изучение цепных дробей началось в XVI–XVII веках.

Итальянский математик Рафаэль Бомбелли в 1572 году в своей «Алгебре» использовал цепные дроби для приближённого вычисления квадратных корней. В 1613 году итальянский астроном и математик Пьетро Антонио Катальди впервые ввёл термин «цепная дробь» в трактате «Trattato del modo brevissimo di trovare la radice quadra delli numeri». В 1655 году английский математик Джон Валлис в книге «Arithmetica Infinitorum» дал систематическое изложение теории цепных дробей, а его ученик Уильям Броункер в 1658 году представил цепную дробь для числа \(\frac{4}{\pi}\).

В XVIII веке Леонард Эйлер внёс значительный вклад в теорию цепных дробей, связав их с дифференциальными уравнениями и непрерывными функциями. В XIX веке немецкий математик Карл Фридрих Гаусс использовал цепные дроби в теории гипергеометрических функций. В XX веке цепные дроби нашли применение в алгоритмах криптографии и теории приближений.

¶Определение и классификация

¶Конечные и бесконечные цепные дроби

Цепная дробь называется конечной, если она содержит конечное число элементов \(a_0, a_1, \dots, a_n\). Любое рациональное число можно представить в виде конечной цепной дроби, причём такое представление единственно (если не считать вариаций, связанных с заменой последнего элемента). Например:

\[ \frac{17}{5} = 3 + \frac{1}{2 + \frac{1}{2}} = [3; 2, 2] \]

где квадратные скобки обозначают сокращённую запись цепной дроби.

Бесконечная цепная дробь содержит бесконечное число элементов. Она представляет иррациональное число. Например, число \(\sqrt{2}\) имеет следующее представление:

\[ \sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots}}} = [1; 2, 2, 2, \dots] \]

¶Правильные и неправильные цепные дроби

Правильная цепная дробь — это дробь, у которой все неполные частные \(a_i\) при \(i \geq 1\) являются положительными целыми числами, а \(a_0\) — любое целое число. Большинство цепных дробей в классической теории являются правильными.

Неправильная цепная дробь допускает произвольные целые (или даже рациональные) значения неполных частных. Такие дроби встречаются в обобщённых теориях, например, в связи с непрерывными дробями Гаусса.

¶Обобщённые цепные дроби

В обобщённой цепной дроби числители могут быть не равны единице, а знаменатели — не обязательно целыми числами. Общий вид:

\[ b_0 + \cfrac{a_1}{b_1 + \cfrac{a_2}{b_2 + \cfrac{a_3}{b_3 + \ddots}}} \]

где \(a_i\) и \(b_i\) — числа (часто действительные или комплексные). Такие дроби используются для представления специальных функций, например, экспоненты или логарифма.

¶Основные свойства

¶Единственность представления

Для любого рационального числа существует единственное представление в виде конечной цепной дроби с условием, что последний элемент \(a_n > 1\) (если \(a_n = 1\), то дробь можно сократить). Для иррациональных чисел представление в виде бесконечной цепной дроби также единственно.

¶Подходящие дроби

Подходящая дробь — это конечная цепная дробь, полученная обрывом бесконечной цепной дроби на некотором шаге. Если цепная дробь представляет число \(x\), то последовательность подходящих дробей \(p_n / q_n\) сходится к \(x\). При этом каждая подходящая дробь является наилучшим рациональным приближением числа \(x\) среди всех дробей со знаменателем, не превосходящим \(q_n\). Это свойство делает цепные дроби мощным инструментом для приближённых вычислений.

¶Периодичность

Бесконечная цепная дробь, представляющая квадратичную иррациональность (корень квадратного уравнения с целыми коэффициентами), является периодической. Например, \(\sqrt{3} = [1; 1, 2, 1, 2, 1, 2, \dots]\). Теорема Лагранжа (1770) утверждает, что любая квадратичная иррациональность представляется периодической цепной дробью, и наоборот, любая периодическая цепная дробь является квадратичной иррациональностью.

¶Применение

¶Теория чисел

Цепные дроби используются для решения диофантовых уравнений, в частности, уравнения Пелля \(x^2 - Dy^2 = 1\). Решения этого уравнения находятся из разложения \(\sqrt{D}\) в цепную дробь. Также цепные дроби применяются для доказательства иррациональности чисел (например, числа \(e\)).

¶Приближённые вычисления

Благодаря свойству наилучших приближений, цепные дроби применяются для построения рациональных аппроксимаций иррациональных чисел. Например, число \(\pi\) можно приблизить дробью \(\frac{355}{113}\), которая является подходящей дробью его цепной дроби. В инженерных расчётах это позволяет заменить сложные иррациональные числа простыми дробями с заданной точностью.

¶Криптография

В криптографии цепные дроби используются в алгоритмах взлома RSA. В 1990 году Михаэль Винер показал, что если секретный ключ \(d\) в RSA мал по сравнению с модулем \(n\), то его можно восстановить, разложив \(e/n\) в цепную дробь (атака Винера). Также цепные дроби применяются в теории решёток и алгоритмах факторизации.

¶Математический анализ

Цепные дроби используются для представления элементарных и специальных функций. Например, разложение в цепную дробь для числа \(\pi\) (формула Броункера):

\[ \frac{4}{\pi} = 1 + \cfrac{1^2}{2 + \cfrac{3^2}{2 + \cfrac{5^2}{2 + \ddots}}} \]

Такие представления применяются в численных методах для быстрого вычисления функций.

¶Примеры

¶Рациональные числа

• \(\frac{7}{3} = 2 + \frac{1}{3} = [2; 3]\)
• \(\frac{45}{16} = 2 + \frac{1}{1 + \frac{1}{5 + \frac{1}{2}}} = [2; 1, 5, 2]\)

¶Иррациональные числа

• \(\sqrt{2} = [1; 2, 2, 2, \dots]\) (период 1)
• \(\sqrt{5} = [2; 4, 4, 4, \dots]\) (период 1)
• \(\varphi = \frac{1+\sqrt{5}}{2} = [1; 1, 1, 1, \dots]\) (золотое сечение)
• \(e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \dots]\) (непериодическая, но с закономерностью)

¶Интересные факты

• Цепная дробь для числа \(\pi\) начинается как \([3; 7, 15, 1, 292, 1, 1, 1, 2, \dots]\). Большой элемент 292 означает, что подходящая дробь \(\frac{355}{113}\) является очень точным приближением (ошибка около \(2.7 \times 10^{-7}\)).
• Алгоритм Евклида, используемый для нахождения НОД, фактически строит цепную дробь для отношения двух чисел.
• В 1970-х годах советский математик Анатолий Карацуба разработал метод быстрого вычисления цепных дробей для больших чисел, что нашло применение в вычислительной математике.

¶Источники

• Виноградов И. М. «Основы теории чисел». — М.: Наука, 1972.
• Хинчин А. Я. «Цепные дроби». — М.: Физматлит, 1960.
• Hardy G. H., Wright E. M. «An Introduction to the Theory of Numbers». — Oxford University Press, 2008.
• Энциклопедия элементарной математики / Под ред. П. С. Александрова, А. И. Маркушевича, А. Я. Хинчина. — М.: ГИТТЛ, 1951.