Конечные цепные дроби и неопределенные уравнения

Введение
Актуальность исследования. Применение аппарата цепных дробей к
прикладным задачам, в том числе олимпиадного характера, позволяет
углубить математические знания, расширить кругозор и повысить
мотивацию к изучению математики.
Объект исследования: цепные дроби.
Предмет исследования: применение последовательности подходящих
дробей для решения диафантовых уравнений и других задач.
Цель исследования:
1. Обработка теоретического материала (его отбор, а также
последовательное и доступное изложение);
2. Поиск областей применения цепных дробей;
3. Составление практического материала в форме упражнений.
Гипотеза исследования: применение цепных дробей позволяет найти
один из способов решения диофантовых уравнений и других задач
олимпиадного характера.
Задачи исследования:
1. Изучить понятие цепных дробей;
2. На примерах приближения различных чисел подходящими
дробями (рациональные числа, квадратичные иррациональности) понять
закономерности использования аппарата цепных дробей;
3. Ознакомиться с историей возникновения и использования
цепных дробей;
4. Выявить и применить возможности цепных дробей к решению
разных видов олимпиадных задач.
Практическая значимость.
Действительные числа однозначно отображаются цепными дробями.
Основное значение такого изображения заключается в том, что, зная цепную
дробь, изображающую действительное число, можно определить это число с
достаточной точностью.

ГЛАВА 1. ПОНЯТИЕ ЦЕПНЫХ ДРОБЕЙ
1.1 Представление рациональных чисел цепными дробями
Целое число, являющееся делителем каждого из целых чисел 
, называется общим делителем этих чисел. Общий делитель этих
чисел называется их наибольшим общим делителем, если он делится на
всякий общий делитель данных чисел.

Пусть  - рациональное число, причем . Применяя к a и b
алгоритм Евклида для определения их наибольшего общего делителя,
получаем конечную систему равенств:

  ,        (1)
где неполным частным последовательных делений 
 соответствуют остатки  с условием , а
соответствует остаток 0.
Системе равенств (1) соответствует равносильная система

,        (2)

4
из которой последовательной заменой каждой из дробей  и т. д. ее
соответствующим выражением из следующей строки получается
представление дроби  в виде:

  
Такое выражение называется правильной (конечной) цепной или
правильной непрерывной дробью, при этом предполагается, что  – целое
число, а , …,  - натуральные числа.
Имеются различные формы записи цепных дробей:

Согласно последнему обозначению имеем

5

Числа  называются элементами цепной дроби.
Алгоритм Евклида дает возможность найти представление (или
разложение) любого рационального числа в виде цепной дроби. В качестве
элементов цепной дроби получаются неполные частные последовательных
делений в системе равенств (1), поэтому элементы цепной дроби называются
также неполными частными. Кроме того, равенства системы (2) показывают,
что процесс разложения в цепную дробь состоит в последовательном
выделении целой части и перевертывании дробной части [5, с. 32]
Последняя точка зрения является более общей по сравнению с первой,
так как она применима к разложению в непрерывную дробь не только
рационального, но и любого действительного числа.
Разложение рационального числа  имеет, очевидно, конечное число
элементов, так как алгоритм Евклида последовательного деления a на b
является конечным.
Каждая цепная дробь представляет определенное рациональное число,
то есть равна определенному рациональному числу. Но возникает вопрос, не
имеются ли различные представления одного и того же рационального числа
цепной дробью? Оказывается, что не имеются, если потребовать, чтобы
было .
Теорема. Существует одна и только одна конечная цепная дробь,
равная данному рациональному числу, но при условии, что  [3, с. 19]
При соблюдении условия  между рациональными числами и
конечными цепными дробями существует взаимно однозначное
соответствие.
Замечания:
В случае разложения правильной положительной дроби первый

элемент , например, . При разложении

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

Пример: , а так как , то 

.

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

Пример: 5=(5); .
Таким образом делаем вывод, что алгоритм Евклида дает возможность
найти представление (или разложение) любого рационального числа в виде
цепной дроби. В качестве элементов цепной дроби получаются неполные
частные последовательных делений в системе равенств (1), поэтому
элементы цепной дроби называются также неполными частными. Кроме
того, равенства системы (2) показывают, что процесс разложения в цепную
дробь состоит в последовательном выделении целой части и перевертывании
дробной части.
1.2 Сходимость правильных бесконечных цепных дробей
В процессе поиска наилучшего приближения значений квадратных
корней итальянский математик Пиетро Антонио Катальди (1552- 1626)
пришел в 1613г. к цепным дробям, с чего и началось их изучение. Правда,
они встречались почти на 40 лет раньше в «Алгебре» другого итальянского
математика – Рафаэля Бомбелли (ок. 1526- 1572). Но Катальди выделил
цепные дроби в отдельный тип, выявил некоторые их свойства.
Современное обозначение непрерывных дробей предложил
выдающийся нидерландский ученый Христиан Гюйгенс (1629- 1695).
Гюйгенс был не только знаменитым физиком, он был и замечательным

7
математиком, удивительным изобретателем и конструктором. К тому же он
писал неплохие стихи [6, с. 41]
К цепным дробям Гюйгенс вынужден был обратиться (1680) при
построении планетария в Париже. Он хотел получить наилучшие
приближения для отношений периодов обращения планет. Эти отношения и
отношения чисел зубцов соответствующих связанных между собой шестерен
планетария должны были совпадать. Но число зубцов шестерен по
техническим причинам не могут быть очень большими. Необходимо было
так их подобрать, чтобы полученные отношения как можно меньше
отличались от истинных. Гюйгенс обратился к цепным дробям и с их
помощью нашел решение стоящей перед ним задачи. При этом он детально
изучил теорию цепных дробей [9, с. 5]
Задаче разложения обыкновенной дроби в непрерывную дробь
противостоит обратная задача – обращения или свертывания цепной дроби 

 в простую дробь .
При этом основную роль играют дроби вида:

 или
 которые называются подходящими
дробями данной непрерывной дроби или соответствующего ей числа .
Заметим, что ==. Считается, что подходящая дробь 
 имеет порядок k.
Прежде чем приступить к вычислению подходящих дробей заметим,

что  переходит в , если в первой заменить  выражением .

Имеем ,

8

,

, …,

при этом принимается, что , , , , , 
 и так далее.
Закономерность, которую мы замечаем в построении формулы для 
 (ее числителя  и знаменателя ), сохраняется при переходе к  и
сохранится также при переходе от k к (k+1).
Поэтому, на основании принципа математической индукции, для
любого k, где , имеем

 (1),
причем  (2)
 (3)

Далее, говоря о подходящих дробях  (в свернутом виде), мы будем

иметь в виду их форму .
Соотношения (1) являются рекуррентными формулами для вычисления
подходящих дробей, а также их числителей и знаменателей. Из формул для
числителя и знаменателя сразу видно, что при увеличении k они возрастают.
Последовательное вычисление числителей  и знаменателей  подходящих
дробей по формулам (2) и (3) удобно располагать по схеме:
… …
… …
… …

Пример: Найти подходящие дроби к цепной дроби (2, 2, 1, 3, 1, 1, 4, 3).

9
2 2 1 3 1 1 4 3
2 5 7 26 33 59 269 866
1 2 3 11 14 25 114 367

Подходящие дроби () равны соответственно ; ; ; ; 
; ; ; .
Следовательно делаем вывод, что последовательность подходящих дробей с
чётным номером ограничена сверху, а с нечётным ограничена снизу. Значит
они имеют предел.
Исходя из результатов, которые мы получили выше, можно
утверждать, что для каждого действительного иррационального
 существует представление в виде бесконечной непрерывной дроби.

ГЛАВА 2. ПРИЛОЖЕНИЯ ЦЕПНЫХ ДРОБЕЙ
2.1 Календарь и подходящие дроби
Древнеримские жрецы, ведавшие исчислением времени, произвольно
удлиняли некоторые года, чтобы согласовать календарные даты с сезонными
явлениями природы. Впервые порядок в счете времени навел в I в. до нашей
эры римский император Юлий Цезарь. Он постановил считать одни годы по
365 суток, а другие по 366 суток, чередуя их по правилу три года подряд
коротких, четвертый – длинный. Гораздо позже, с введением христианского
летоисчисления, високосным стали считать каждый год, порядковый номер
которого делится на 4. Этот календарь в честь Юлия Цезаря называется
юлианским. По нему продолжительность суток составляет 365 суток 6 ч, что
больше истинной лишь на 11 мин 14 с. Однако и это решение оказалось
неудовлетворительным. К XVI в. ошибка, накапливаясь, составила уже около
10 суток [2, с. 30]

10
Следующую реформу календаря провел Григорий XIII – папа римский.
Было решено: сдвинуть числа на 10 дней, оставить чередование простых и
високосных лет, при этом, если порядковый номер года оканчивается двумя
нулями, но число сотен не делится на 4, то этот год простой. В настоящее
время расхождение между юлианским и новым, григорианским календарями
составляет 13 дней, поскольку с тех пор накопилось еще три дня (в 1700,
1800 и 1900 гг.). Продолжительность григорианского года составляет
365, 2425 суток, т.е. 365 суток 5 ч 49 мин 12 с, т.е. она больше истинной
лишь на 26с. Полученная точность очень велика и вполне достаточна для
практических нужд.
Интересная система календаря была предложена среднеазиатским
математиком и поэтом Омаром Хайямом (ок.1048-1122), по ней високосными
годами должны были считаться 8 лет из каждых 33. Продолжительность года
по О. Хайяму составляет 365 суток, его погрешность всего 19с в год [10, с.
18]
В 1864 г. русский астроном И. Медлер предложил с XX столетия
ввести в России следующую поправку к юлианскому календарю: через
каждые 128 лет пропускать один високосный год из 32, которые выпадают на
этот период. Этот календарь самый точный из всех перечисленных. Здесь
погрешность сокращается всего до 1с. Однако календарь И. Медлера не был
принят, видимо, из-за того, что период в 128 лет не является «круглым»
числом.
Системы календаря оказываются связанными с записью
астрономического года в виде цепной дроби.
Год продолжительностью 365 суток - это нулевая подходящая дробь
этой цепной дроби, 365 - юлианский год – первая подходящая дробь, 365, 365
и 365 - вторая, третья и четвертая подходящие дроби.
Системой, соответствующей второй подходящей дроби: семь
високосных лет из 29, никто не предложил воспользоваться, видимо, потому,
что третья подходящая дробь не намного сложнее, а точность ее гораздо

11
больше (вспомним, что это система О. Хайяма), а четвертой подходящей
дроби соответствует система И. Медлера [8, с. 62]
Второе свойство цепных дробей
Вспомним, как вычисляются подходящие дроби.
Имеют место рекуррентные соотношения
Р k+1  = q k+1  . P k +P k-1  и Q k+1 = q k+1 .Q k +Q k-1.
Второе свойство цепных дробей: для любого k = 1,2,…, n имеет место
формула
P k-1 Q k  – P k Q k-1  = (-1) k .
Диофантовы уравнения вида ax+by=с [7, с. 20]
Используем отмеченное нами свойство цепных дробей для решения
уравнения ax+by=c Коэффициенты a и b взаимно просты. Разложим в
цепную дробь. При этом .
Поскольку обе дроби несократимы, то a = P n , b = Qn. По свойству
имеем
bP n-1  – aQ n-1  = (-1) n .
Умножив обе части этого равенства на (-1) n c, получим
(-1) n+1 aQ n-1 c + (-1) n bP n-1 c =c,
откуда видно, что пара чисел
x 0  = (-1) n+1 cQ n-1 , y 0  = (-1) n cP n-1
представляет собой решение уравнения.
Общее решение запишется в виде:
x = (-1) n+1 c Q n -1  + bt, y = (-1) n  c P n –1  – at,
где t принимает целые значения
Решим уравнение 17х + 13у = 5.
Поскольку , то n = 2, ,
откуда х 0  = -5•3 = -15, у 0  = 4•5 = 20 и общее решение имеет вид
x = -15+13t, y = 20-17t.
При решении уравнений вида ax + by = c будем использовать
следующий алгоритм :

12
1) Разложим в цепную дробь (с помощью алгоритма Евклида или с
помощью соответствующих преобразований).
2) Из разложения =определяем значение n (т.е. длину цепной дроби).
3) Находим n-1 – подходящую дробь (в случае необходимости
используем таблицу).
4) Применяем формулы:
Общее решение: x = (-1) n+1 c Q n -1  + bt, y = (-1) n  c P n –1  – at.
Замечания.
1) Можно находить сначала частное решение:
x 0  = (-1) n+1 cQ n-1 , y 0 = (-1) n cP n-1  .
А затем общее решение: x = x 0  + bt, y = y 0  – at
2) Если уравнение имеет вид ax – by = c, то, очевидно, что x = (-
1) n+1 c Q n -1  + bt,
y = (-1) n+1  c P n –1 +  at.
3) Если a > b и =, то = [0; q 0,  q 1 ,…,q n ].
Цепные дроби стали систематически изучать в XVII веке.
И достижением, и толчком в развитии этой теории стала работа Христиана
Гюйгенса по созданию модели Солнечной системы с помощью зубчатых
колёс (см. «Зубчатые колёса»). О характере и стиле этой научной работы
Гюйгенса выразительно рассказывается в классической книге А. Я. Хинчина
«Цепные дроби» [7, с. 39]:
«Гюйгенс был поставлен перед задачей определения числа зубцов
колёс таким образом, чтобы отношение этих чисел для двух связанных
между собою колёс (равное отношению времени полного оборота их) было
по возможности близко к отношению  времени обращения соответствующих
планет. Вместе с тем число зубцов по техническим причинам не могло,
разумеется, быть чрезмерно большим. Таким образом, встал вопрос об
отыскании такой рациональной дроби, числитель и знаменатель которой
не превосходили бы данного предела и которая вместе с тем возможно ближе

13
лежала бы к данному числу теория цепных дробей даёт возможность
полностью решить поставленную таким образом задачу» [6, с. 45]
Александр Яковлевич Хинчин, автор процитированной книги — один
из создателей школы теории вероятностей в нашей стране, уделявший много
внимания развитию математического образования, популяризации
математики.
В григорианском календаре в 400‐летнем цикле число недель —
ровно . Это период во всех смыслах, на его основе можно создавать «вечные»
календари. За 400‐летний период тринадцатое число месяца встретится  раз,
но распределение по дням недели не будет одинаковым: понедельник
встретится 685 раз, вторник — 685, среда — 687, четверг — 684, пятница —
688, суббота — 684, воскресенье — 687. Такое расхождение в частотах
связано с тем, что начало каждого цикла — вполне определённый день
недели: понедельник (очередной цикл начался 1 января 2001 года).
Следовательно, за длительный период наблюдений среди тринадцатых
чисел месяцев чаще других выпадает «пятница, тринадцатое». (Избранные
задачи из журнала «American Mathematical Monthly», М.: Мир, 1977, задача
303).
Подводя итог можно сказать, что разложение в каноническую цепную
дробь  произвольного действительного числа - это однообразный процесс,
который состоит из двух многократно повторяющихся и чередующихся друг
с другом действий: "получения достатка" и "обращения остатка".  
"День и ночь - сутки прочь", "Зима и лето - года нету": С незапамятных
времён люди подметили, что важнейшие отрезки времени - год и сутки -
определяются различными природными процессами. Однако в том, что год
не измеряется целым числом суток, они разобрались далеко не сразу. Но ведь
если измерять год с целым количеством суток, то постепенно набегут (или
убегут) "лишние" секунды, минуты, часы, которые со временем составят дни,
недели и месяцы. Так оно и произошло.
2.2 Олимпиадные задачи с использованием цепных дробей

14
1. Олимпиадная задача по математике из коллекции задач Турнира
Ломоносова
Решить уравнение в целых положительных числах

Решение:
Любое число единственным образом представляется в виде суммы двух
чисел, одно из которых — целое, а другое — неотрицательно и меньше
единицы. Это — сумма его целой и дробной части. Для  таким
представлением будет . Поэтому x = 1, . Аналогично
разлагаем  в сумму целой и дробной части. Получаем y = 2, z = 3.

2. Олимпиадная задача No. 32127.
Докажите, что

Решение:
Докажем тождество

Действительно,

Требуемое в задаче равенство получается подстановкой в доказанное

тождество 

15
3. Олимпиадная задача по математике из коллекции задач
Международного Турнира Городов
Условие
Решить в натуральных числах уравнение: 
x + 1/(y + 1/z) = 10/7
Решение:
Так как числа x, y, z — натуральные, x =  = 1, y =  = 2, z = 3.
4. Олимпиадная задача по математике из коллекции задач
Международного Турнира Городов
Решение:
Докажем тождество

 = 1 при x ≠ – 1, x ≠ – 2.

Действительно,

Требуемое в задаче равенство получается подстановкой в доказанное
тождество
x =  .

5. Олимпиадная задача No 105047
Сравнив дроби 111110/111111, 222221/222223, 333331/333334,
расположите их в порядке возрастания.
Решение:
Рассмотрим числа
1-x=1/111111,

16

1-y=2/222223,
1-z=3/333334,
а также обратные к ним
1/(1-x)=111111,
1/(1-y)=111111+1/2,
1/(1-z)=111111+1/3.
Мы видим, что 1/(1-x) < 1/(1-z) < 1/(1-y).
Поскольку все рассматриваемые числа положительны, 1-x > 1-z > 1-y.
Следовательно, x<z<y.
6. Олимпиадная задача No 105120
На острове 2/3 всех мужчин женаты и 3/5 всех женщин замужем. Какая
доля населения острова состоит в браке?
Решение:
Пусть число супружеских пар на острове равно N, то есть
замужем N женщин, женаты N мужчин. Замужние женщины составляют
3/5 всех женщин острова, значит, на острове (5/3)N женщин. Женатые
мужчины составляют 2/3 всех мужчин острова, значит, на острове
(3/2)N мужчин. Всего на острове (5/3)N+(3/2)N=(19/6)N жителей, а в браке
состоит 2N жителей. Искомая доля равна (2N)/((19/6)N)=12/19.
Ответ:
12/19 населения острова.
7. Олимпиадная задача No 105216
Найти все несократимые дроби а/b, представимые в виде b,а (запятая
разделяет десятичные записи натуральных чисел b и а).
Решение:
Пусть натуральные числа a и b взаимно просты, а десятичная запись
числа a имеет n знаков. Тогда условие задачи для них записывается в виде
уравнения

a : b = , a         = b + a  .  10 -n         10 n (a - b 2 ) = a  .  b,

17
из которого следует, в частности, что a > b. В силу взаимной простоты
чисел a и b, число a - b 2  не имеет общих делителей ни с a, ни с b,
следовательно, уравнение превращается в систему из двух уравнений
a - b 2  = 1,        10 n  = a  .  b.
В силу все той же взаимной простоты чисел a и b (с учетом
неравенства a > b), последнему уравнению удовлетворяют только пары
чисел a=10 n , b = 1, а также a = 5 n  и b = 2 n . Первая пара при подстановке
в первое уравнение дает для числа n уравнение 10 n  = 2, которое, очевидно,
не имеет решений. Вторая пара чисел a и b при подстановке в первое
уравнение дает для числа n уравнение

5 n  - 4 n  = 1         = 1 + .
Так как его левая часть представляет собой возрастающую функцию от n,
а правая --убывающую, то оно имеет не более одного корня, который
угадывается: n = 1, откуда и находим единственную пару a = 5 и b = 2.
Ответ
a = 5, b = 2.
Делая выводы можно сказать, что единственность представления
действительного иррационального числа правильной бесконечной цепной
дробью.
Исходя из результатов, которые мы получили выше, можно
утверждать, что для каждого действительного иррационального 
 существует представление в виде бесконечной непрерывной дроби. Таким
представлением является разложение  в бесконечную непрерывную дробь,
так как предел подходящих дробей последней равен как раз .
Возникает вопрос, сколько представлений действительного
иррационального  в виде бесконечных непрерывных дробей существует
вообще? Покажем, что только одно.

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

ЗАКЛЮЧЕНИЕ
Данная курсовая работа показывает значение цепных дробей в
математике.
Их можно успешно применить к решению неопределенных уравнений
вида ax+by=c. Основная трудность при решении таких уравнений состоит в
том, чтобы найти какое-нибудь его частное решение. Так вот, с помощью
цепных дробей можно указать алгоритм для разыскания такого частного
решения.
Цепные дроби можно применить и к решению более сложных
неопределенных уравнений, например, так называемого уравнения Пелля:
Бесконечные цепные дроби могут быть использованы для решения
алгебраических и трансцендентных уравнений, для быстрого вычисления
значений отдельных функций.
В настоящее время цепные дроби находят все большее применение в
вычислительной технике, ибо позволяют строить эффективные алгоритмы
для решения ряда задач на ЭВМ.
Подведем итоги. В ходе исследования была проведена следующая
работа:
1)Собран и освоен теоретический материал, составлены на основании
изученных свойств алгоритм решения приведенных в данной работе
диофантовых уравнений. Сформулированы замечания, использующиеся при
решении данных уравнений.
2)Найдены некоторые области применения цепных дробей.
3)Составлены и выполнены практические задания по разложению
действительных чисел в цепные дроби, а также по решению диофантовых
уравнений вида ax+by=c , других олимпиадных задач.
Список использованных источников

1. Баврин, И. И. Занимательные задачи по математике / И. И.
Баврин, Е. А. Фрибус, И. С. Хомякова, Т. Д. Стульник. – М. :
Питер, 2007. - 304 с.
2. Басова, Л.А.  Лекции и задачи по математике / Л.А. Басова, М.А.
Шубин. – М. : БГТУ, 2004. – 274 с.
3. Виленкин Н. Я. За страницами учебника математики:
Арифметика. Алгебра. Геометрия: Книга для учащихся 10-11 кл.
общеобразовательных учреждений / Н. Я. Виленкин. – Москва :
Издательство Московского университета, 2004. - С. 134–137.
4. Гожигова, Е. П. Что такое теория чисел / Е. П. Гожигова, В. В.
Агеносов, Э. З. Ганкина. – М. : Просвещение, 1989. - 399 с.
5. Кичурин, Л. Ф. За страницами учебника алгебры: Книга для
учащихся 7-9 кл. сред. шк. / Л. Ф. Кичурин. – М. : Изд-во Омского
гос. пед. университета, 1998. - 256 с.
6. Кавин, А. П. Энциклопедический словарь юного математика / А.
П. Кавин, В. М. Петрова. – М. : Просвещение, 1978. - 157 с.
7. Куликов, А. Я. Сборник задач по алгебре и теории чисел / А. Я.
Куликов. – М. : Просвещение, 1976. – 93 с.
8. Ляпин, Е. С. Алгебра и теория чисе: в 13 т. Т 1. / Е. С. Ляпин : под
ред. Н. Ф. Бельчикова [и др]. – М. : АН СССР, 1953. - 574 с.
9. Михелович, Ш. Теория чисел / Ш. Михелович. –М. :
Просвещение, 1976. - 56 с. 
10. Хипчин, А.Я. Цепные дроби / А. Я. Хипчин. – М. : Просвещение,
1978. – 112 с.