Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
c) ЬіСі_х — Ьі_гСі = ( —1)! 1 oYff г ^ 1.
Доказательство. Определим последовательности {&;} и {с;} с помощью соотношений из части а) (приравнивая соответствующие числители и знаменатели — прим. ред.); докажем по индукции, что тогда bi/ci — 2-е приближение. Докажем это, не предполагая, что йі — целые числа, т. е. докажем, что для любых вещественных чисел ui отношение bi/ci с bi и Сі, определенными формулами в части а), равно а0 + ¦^+- • ¦ • ^-- База индукции (г = 0,1,2) тривиальна. Предположим теперь, что утверждение справедливо вплоть до г-ro приближения, и докажем его для (г + 1)-го приближения. Заметим, что мы получим (г + 1)-е приближение, заменяя на a; ¦f l/ai+1 в формуле, которая выражает числитель и знаменатель г-ro приближения в терминах (г — 1)-го и (г — 2)-го приближений. Таким образом, (г + 1)-е приближение в силу предположения индукции равно
(Q« + ^77)6'-! + _ аг+і(агЬі-і + bj_2) + _ ai+ibi +
(а{ + )сг_! + Сг_2 Oi + 1(UiCi^1 + С;_2) + c,-_i ai + 1cl+ci_1'
Тем самым часть а) доказана.
. Часть с) также легко доказать по индукции. Шаг индукции проводится следующим образом:
Ьі+1Сі - ЬіСі+1 = (ai+1b, + Ь,_і)сі - bi(at+1Ci + с;_х) = Ьг_іct - Ь{с{-Х
= -(-1)^=(-1)',
Таким образом, из того, что часть с) справедлива для і, следует соответствующее утверждение для і -f 1.
Наконец, часть Ь) следует из части с), так как любой общий делитель bi и с,- должен быть делителем числа (—1)' 1, равного ±1. Предложение доказано.
Если разделить равенство в предложении V.4. 1 с) на CjC^1, то получим:
bi Ьі.г _ (-1Г1
176
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
Так как с,-, очевидно, образуют строго возрастающую последовательность натуральных чисел, это равенство показывает, что последовательность приближений ведет себя подобно знакопеременному ряду, т.е. она колеблется вперед и назад с уменьшающейся амплитудой, и, значит, последовательность приближений сходится к пределу.
Наконец, нетрудно заметить, что предел последовательности есть само число х, для которого строится разложение. Чтобы показать это, заметим, что х получается, если в (г + 1)-м приближении заменить а;+1 на 1/х{. Таким образом, по предложению V.4.1 а) (с г + 1 вместо г и заменой Oi+1 на \/х{) имеем:
Ьг/хг + Ьі_і bi + xibi_i
с-і/хі + ^i-1 (-і + Xi^i-I
при этом X оказывается в промежутке между Ь;_і/с;_і и bi/ct. (Чтобы убедиться в этом, рассмотрим два вектора U = (6;, Cj) И V = (&;_1, Cj_!) в плоскости, оба расположенные в одном и том же квадранте; заметим, что направление вектора u+XjV является промежуточным между направлениями векторов и и v.) Стало быть, последовательность Ьг/Сг колеблется вокруг X И СХОДИТСЯ К X.
Цепные дроби имеют много интересных свойств, что обусловило их применения в различных областях математики. Например, они доставляют «наилучший возможный» способ рациональной аппроксимации вещественных чисел (в том смысле, что любое рациональное число, более близкое к х, чем bi/ci, должно иметь знаменатель, больший, чем С;). Другое свойство аналогично тому факту, что в представлении вещественного числа х в десятичной (или Ь-ичной) системе знаки периодически повторяются тогда и только тогда, когда х рационально. В разложении х в цепную дробь, как мы видели, последовательность целых чисел обрывается в том и только том случае, когда х рационально. Можно показать, что последовательность целых чисел а, становится периодической последовательностью в том и только том случае, когда х — квадратичная иррациональность, т. е. имеет вид Xi + х2у/п, где Xi и X2 — рациональны, а п не есть полный квадрат. Это — известная теорема Лагранжа.
Пример 1. Выписывая по порядку первые члены разложения \/3 в цепную дробь, получаем
л/З= 1 + — — — — — —
+ 1+2+ 1+2+ 1+2+ '"'
Естественно предположить, что а; попеременно принимают значения 1 и 2. Докажем это. Пусть х равно бесконечной цепной дроби в правой части с чередующимися 1 и 2. Согласно определению цепной дроби
§ 4. МЕТОД ЦЕПНЫХ ДРОБЕЙ
177
для X мы, очевидно, имеем х = 1 + TTZTT- Упрощая это рациональное выражение и умножая затем обе части равенства на х + 2, получаем 2х + Xі = 3 + 2х, т.е. X = -\/3.
Предложение V. 4. 2. Пусть х > 1 — вещественное число, при разложении в цепную дробь имеющее приближения bj/cj.
Тогда \Ьг — х с; | < 2х при любом і.
Доказательство. Как мы видели, х лежит в промежутке между Ьі/сі и 6г+і /сг + 1. Разность между этими величинами по абсолютной величине равна с 1 (предложение V. 4. 1 с)). Поэтому
16
2 2, X С,
X —
X +
< C1
CiC
i + 1
X + [X +
C1Ci + I
Следовательно,
112
2 2,
X С,
2х < 2х
< 2х
1 + 1 +
Ci + I Сг+1 Сг + 1
+
2хс\
+ 1'
< 2х
1 +
+
-i + l
Ci + I
= 0.
Предложение доказано.
Предложение V.4.3. Пусть п — натуральное число, не являющееся полным квадратом. Пусть Ьі/сі — приближения при разложении у/п в цепную дробь. Тогда наименьший по абсолютному зна-чению вычет bj (mod п) (расположенный между —п/2 и п/2) меньше 2фг.
