Что такое конечная цепная дробь и с чем это едят?
Определение. Конечной цепной дробью называется выражение вида:
,где a₀, a₁, ..., aₙ - целые числа; a₁ ≥ 1, a₂ ≥ 1, ... aₙ₋₁ ≥1, aₙ > 1. При этом числа a₀, a₁, ..., aₙ неполными частными или элементами цепной дроби, n - длиной цепной дроби.
Обратите внимание, что длина этой цепной дроби равняется n, а не n + 1
Одно из возможных обозначений такой цепной дроби следующее: [a₀; a₁; ...; aₙ], которое мы будем использовать дальше для удобства повествования.
Представление любого рационального числа в виде цепной дроби с помощью Алгоритма Евклида
(Теорема 1) Дробь m/n равна некоторой цепной дроби тогда и только тогда когда элементы этой цепной дроби - последовательные неполные частные в алгоритме Евклида для пары (m, n).
Докажем, что если элементы цепной дроби - последовательные неполные частные в алгоритме Евклида для пары (m, n), то m/n равна этой цепной дроби
Для этого распишем алгоритм Евклида для этой пары:
Перепишем его в следующем виде:
Попробуем выразить m/n через имеющиеся выражения:
Нетрудно видеть, что все элементы полученной цепной дроби удовлетворяют условиям указанным в определении.
Докажем, что если дробь m/n равна некоторой цепной дроби, то элементы этой цепной дроби - последовательные неполные частные в алгоритме Евклида для пары (m, n).
Попробуем воспользоваться индукцией по длине цепной дроби. Пусть ℓ - длина цепной дроби.
Рассмотрим случай ℓ = 1 (это будет базой индукции). Пусть m/n = a₀ + 1/a₁. Так как 1/a₁ < 1, то [m/n] = a₀.
[x] - это наибольшее целое число, меньшее числа x. Называется целой частью числа x. Например: [3.4] = 3; [-2.7] = -3.
Пусть m = kn + r, тогда k = a₀. Отсюда r/n = 1/a₁, тогда r = 1 и n = a₁. Отсюда получаем, что алгоритм Евклида для пары (m, n) выглядит следующим образом: m = a₀n + r; n = 1 × n. Нетрудно видеть, что мы получили необходимое. База индукции есть!
Теперь шаг индукции. Предположим, что для всех цепных дробей длины ≤ℓ справедливо доказываемое утверждение. Докажем, что оно справедливо и для цепных дробей длиной ℓ + 1.
Пусть m/n = [a₀, a₁, a₂ ..., aₙ], отсюда a₀ = [m/n], то есть a₀ - одно из частных в алгоритме Евклида. Тогда n/r₁ = [a₁, a₂ ..., aₙ], что является цепной дробью длины n, значит для нее мы можем применить предположение индукции и получить доказываемое утверждение.
(Следствие теоремы 1) Любое рациональное число представимо единственным способом в виде конечной цепной дроби.
Пример. Попробуем представить дробь 17/37 в цепном виде.
Для начала распишем алгоритм Евклида для пары (17, 37):
17 = 0⨯37 + 17
37 = 2⨯17 + 3
17 = 5⨯3 + 2
3 = 1⨯2 + 1
2 = 2⨯1
Тогда 17/37 = [0, 2, 5, 1, 2].
Подходящие цепные дроби
Определение. Подходящей дробью к дроби [a₀; a₁; ...; aₙ] называют дробь Pₘ/Qₘ = [a₀; a₁; ...; aₘ], где m ≤ n. Pₘ называют подходящим числителем, а Qₘ соответственно подходящим знаменателем.
Заметим, что последнему элементу в подходящей дроби мы позволяем быть равным 1.
Например, подходящими к дроби [0, 2, 5, 1, 2] будут [0], [0, 2], [0, 2, 5], [0, 2, 5, 1], [0, 2, 5, 1, 2].
(Теорема 2). Подходящие числители и знаменатели связаны следующим рекуррентным соотношением:
P₀ = a₀; Q₀ = 1
P₁ = a₀a₁ + 1; Q₁ = a₁
...
Pₘ = aₘPₘ₋₁ + Pₘ₋₂; Qₘ = aₘQₘ₋₁ + Qₘ₋₂
Докажем это утверждение по индукции по параметру m. Базу для m = 0, m = 1, m = 2 достаточно легко проверить "ручками" (оставим читателю в качестве несложного упражнения :D).
Пусть теперь это утверждение верно для некоторого m (m < n). Докажем, что оно верно и для m + 1.
Рассмотрим цепную дробь длины m + 1: [a₀; a₁; ...; aₘ; aₘ₊₁]. Заменим aₘ + 1/aₘ₊₁ в этой дроби на bₘ. Тогда: [a₀; a₁; ...; aₘ₋₁; aₘ; aₘ₊₁] = [a₀; a₁; ...; aₘ₋₁; bₘ]. Пусть P - подходящий числитель дроби [a₀; a₁; ...; aₘ₋₁; bₘ], а Q - подходящий знаменатель.
Заметим, что для [a₀; a₁; ...; aₘ₋₁; bₘ] выполняется предположение индукции, поэтому P/Q = (bₘPₘ₋₁ + Pₘ₋₂)/(bₘQₘ₋₁ + Qₘ₋₂) = ((aₘ + 1/aₘ₊₁)Pₘ₋₁ + Pₘ₋₂)/((aₘ + 1/aₘ₊₁)Qₘ₋₁ + Qₘ₋₂) = (Pₘ + Pₘ₋₁/aₘ₊₁)/(Qₘ + Qₘ₋₁/aₘ₊₁) = (aₘ₊₁Pₘ + Pₘ₋₁)/(aₘ₊₁Qₘ + Qₘ₋₁). Осталось вспомнить, что Pₘ₊₁/Qₘ₊₁ = P/Q и теорема доказана!
Парочка свойств подходящих дробей
(Свойство 1). PₘQₘ₋₁ + Pₘ₋₁Qₘ = (-1)ᵐ⁻¹, для всех 0≤ m ≤ n.
Докажем Свойство 1 по индукции.
База для m = 0, 1 очевидна.
Докажем шаг индукции. Предположим, что для m данной утверждение справедливо. Докажем, что оно справедливо и для m + 1. Для этого воспользуемся Теоремой 2: Pₘ₊₁Qₘ + PₘQₘ₊₁ = (aₘ₊₁Pₘ + Pₘ₋₁)Qₘ - Pₘ(aₘ₊₁Qₘ + Qₘ₋₁) = Pₘ₋₁Qₘ - PₘQₘ₋₁ = -(-1)ᵐ⁻¹ = (-1)ᵐ.
(Свойство 2) НОД(Pₘ; Qₘ) = 1
Предположим противное. Пусть НОД(Pₘ; Qₘ) = k, k > 1. Тогда PₘQₘ₋₁ + Pₘ₋₁Qₘ делится на k, но по Свойству 1 PₘQₘ₋₁ + Pₘ₋₁Qₘ = (-1)ᵐ⁻¹, то есть (-1)ᵐ⁻¹ делится на k > 1. Противоречие, значит изначальное предположение неверно.
У подходящих дробей еще множество интересных свойств, но все мы здесь разобрать не сможем, увы :(
Немного про бесконечною цепную дробь
Зная, что такое конечная цепная дробь, несложно понять, что называется бесконечной цепной дробью. Бесконечная цепная дробь - цепная дробь, у которой бесконечно много элементов. Этого интуитивного определения нам достаточно.
Заметим, что бесконечной цепной дроби могут быть равны только иррациональные числа. Также и любое иррациональное число можно представить в виде цепной дроби и единственным способом.
Пусть нам необходимо представить иррациональное число α в виде цепной дроби. Тогда α₀ = α, a₀ = [α₀]; αᵢ = 1/(αᵢ₋₁ - aᵢ₋₁), aᵢ = [αᵢ], где aᵢ - i-й элемент цепной дроби.
Например, √19 = [4, 2, 1, 3, 1, 2, 8, 2, 1, 3, 1, 2, 8, 2, 1, 3, 1, 2, 8 ... ]. Заметим, что данная цепная дробь периодическая, то есть ,начиная с определенного элемента (здесь с a₁), элементы зацикливаются.
Фух... Большое спасибо за прочтение статьи! Статья получилась сложной, но надеюсь очень интересной и познавательной. Если найдёте какие-то неточности или у вас появятся вопросы, то смело спрашиваете в комментариях, обсудим вместе!
Больше интересного контента каждый день в телеграм канале "Сложно-простая математика".
Подписывайтесь, не забывайте ставить лайки и писать комментарии. Надеюсь, что мы не прощаемся :-3!