Гашков С.Б. Современная элементарная алгебра в задачах и решениях
Подождите немного. Документ загружается.
§ 1.3. Алгоритм Евклида и цепные дроби 21
Поэтому ясно, что произвольную (как правильную, так и неправиль
-
ную) положительную дробь можно представить в виде цепной дроби
с натуральными элементами a
i
, а именно
a
1
+
1
a
2
+
.
.
.
+
1
a
k−1
+
1
a
k
,
где возможно a
1
= 0.
!
Запись числа в виде цепной дроби неоднозначна, так как
1
a
k
=
1
a
k
−1 +
1
1
.
Чтобы сделать ее однозначной, далее используем только запись, в кото
-
рой последний элемент a
k
6= 1.
Будем использовать также сокращенную запись цепной дроби:
a
1
+
1
a
2
+
1
a
3
+
...
1
+a
k
.
С объявлением однозначности записи числа в виде цепной дроби мы
поторопились, так как можно рассматривать цепные дроби с нецелы
-
ми элементами. Но для дробей с натуральными элементами это верно:
действительно, из равенства
l
1
l
2
= a
1
+
1
a
2
+
.
.
.
+
1
a
k−1
+
1
a
k
следует, что a
1
равно целой части дроби l
1
/
l
2
, так как дробь
1
a
2
+
.
.
.
+
1
a
k−1
+
1
a
k
22 Глава I. Числа и комбинаторика
очевидно меньше 1, и поэтому определяется однозначно. Отсюда следует,
что и дробь
a
2
+
1
a
3
+
.
.
.
+
1
a
k−1
+
1
a
k
определяется однозначно; аналогичным образом получаем, что элемент a
2
определяется однозначно, и т. д.
!
Алгоритм Евклида заканчивает работу не всегда, а лишь когда
отрезки l
1
и l
2
соизмеримы, т. е. когда отношение l
1
/
l
2
––
рацио
-
нальное число, и только в этом случае соответствующая цепная дробь
будет конечной.
Определение 6. Если отрезки несоизмеримы, то число, равное от
-
ношению их длин, называется иррациональным числом.
В этом случае алгоритм Евклида будет работать бесконечно, и тогда
возникнет бесконечная цепная дробь.
Упражнение 3. а) Примените алгоритм Евклида для проверки соиз
-
меримости основания и боковой стороны равнобедренного треугольника
с углом 72
◦
при основании и проверьте, что алгоритм будет работать бес
-
конечно и породит бесконечную цепную дробь
1 +
1
1 +
.
.
.
+
1
1 + ...
.
б) Найдите геометрически, чему равно отношение боковой стороны
к основанию в этом треугольнике, и докажите его иррациональность,
не пользуясь алгоритмом Евклида.
Далее иногда удобнее элементы цепной дроби нумеровать, начиная
с a
0
. Цепную дробь
a
0
+
1
a
1
+
.
.
.
+
1
a
n−1
+
1
a
n
можно рассматривать с произвольными, а не только натуральными эле
-
ментами. Если выполнить все действия, указанные в ней, то ее можно
преобразовать в обыкновенную дробь.
§ 1.3. Алгоритм Евклида и цепные дроби 23
Определение 7. Выражение числителя и знаменателя преобра
-
зованной дроби через a
0
, a
1
, .. ., a
n
обозначим [a
0
, ..., a
n
] и [a
1
, ..., a
n
].
Выражение [a
0
, ..., a
n
] представляет из себя многочлен с перемен
-
ными a
0
, ..., a
n
.
Упражнение 4. Непосредственно проверьте, что
[a
0
, ..., a
n
] = a
0
[a
1
, ..., a
n
] + [a
2
, ..., a
n
].
Можно считать, что это равенство справедливо и при n = 1, если послед
-
ней скобке в этом случае приписать значение 1.
Применяя алгоритм Евклида к числителю и знаменателю дроби
[a
0
, ..., a
n
]
[a
1
, ..., a
n
]
,
где числа a
i
––
натуральные, замечаем, что она несократима, так как в ре
-
зультате его работы получается как раз цепная дробь
a
0
+
1
a
1
+
.
.
.
+
1
a
n−1
+
1
a
n
,
и
([a
0
, ..., a
n
], [a
1
, ..., a
n
]) = ([a
n−1
, a
n
], [a
n
]) = ([a
n
], 1) = 1.
Со времен Евклида придумано немало новых вариантов его алгоритма,
в основном с целью ускорения работы. Опишем некоторые из них.
Обобщенный алгоритм Евклида определяет последовательность
вычислений вида
a = bq
2
+ ε
2
r
2
, b = r
2
q
3
+ ε
3
r
3
, r
2
= r
3
q
4
+ ε
4
r
4
, ...,
r
k−3
= r
k−2
q
k−1
+ ε
k−1
r
k−1
, r
k−1
= r
k
q
k
,
где
ε
i
= ±1, 0 < r
i
< r
i−1
, i > 1, b = r
1
, a = r
0
.
Число k −1 назовем его длиной. Как и в обычном алгоритме Евклида,
(a, b) = r
k
.
Алгоритмом Евклида с выбором минимального по модулю
остатка называется обобщенный алгоритм Евклида, в котором всегда
2r
i
6 r
i−1
, т. е. на каждом шаге из двух возможных вариантов деления
r
i−2
= r
i−1
q
i−1
+ r
i
, где 0 < r
i
< r
i−1
,
и
r
i−2
= r
i−1
(q
i−1
+ 1) − (r
i−1
−r
i
)
выбираем тот, при котором получается минимальный по абсолютной ве
-
личине остаток (если они равны по модулю, то берем любой из них).
24 Глава I. Числа и комбинаторика
Упражнение 5. а) Если u и v четны, то (u, v) = 2(u
/
2, v
/
2);
б) если u четно, а v нечетно, то (u, v) = (u
/
2, v);
в) если u и v нечетны, то u −v четно,
|u −v|< max (u, v), (u, v) = (|u −v|, min (u, v)).
Алгоритм, основанный на этих утверждениях, называется бинарным
вариантом алгоритма Евклида. Как выяснилось, этот вариант алго
-
ритма Евклида был известен в Древнем Китае (но обычного варианта там
не знали).
Задачи и упражнения к § 1.3
1. При каких целых n дробь
5n + 6
8n + 7
несократима? Докажите, что дробь
21n + 4
14n + 3
несократима при всех целых n.
2. На миллиметровой бумаге нарисован прямоугольник размером
a ×b так, что стороны его идут по линиям сетки. На какое число частей
делят узлы сетки его диагональ?
3. От нарисованного прямоугольника отрезают несколько квадратов
со стороной b до тех пор, пока не останется прямоугольник с шириной
меньше b, и с ним поступают точно так же, пока не получится прямо
-
угольник, который целиком разрезается на квадраты. Приведите пример
прямоугольника a ×b, который разрезается ровно на n квадратов.
4. Пусть (m, 360) = 1, 1 < m < 360. Докажите, что с помощью одного
циркуля можно разделить угол в m градусов на m равных частей.
5. Примените бинарный алгоритм для доказательства равенства
(2
m
−1, 2
n
−1) = 2
(m,n)
−1.
6. Докажите, что при любом целом a 6= 1 имеем (a
m
−1, a
n
−1) =
= a
(m,n)
−1.
7. Докажите иррациональность квадратного корня из любого нату
-
рального числа, не являющегося полным квадратом (т. е. квадратом на
-
турального числа).
8. Примените алгоритм Евклида для доказательства открытой,
по преданию, Пифагором несоизмеримости диагонали квадрата с его
стороной.
9. Разложите
√
2 в цепную дробь.
§ 1.3. Алгоритм Евклида и цепные дроби 25
10. (Эйлер *.) Докажите индукцией по n, что выражение (называемое
иногда континуантом, или скобками Эйлера)
[a
0
, ..., a
n
]
можно получить следующим образом: берем произведение всех элемен
-
тов, затем всевозможные произведения, которые можно получить, опу
-
стив какую
-
нибудь пару соседних элементов, затем из этих произведений
получаем новые, выбрасывая произвольным образом пары соседних эле
-
ментов, и так далее, и, наконец, суммируем все различные из получив
-
шихся произведений (если n + 1 четно, то на последнем шаге получается
«
пустое
»
произведение, не содержащее вообще сомножителей; как при
-
нято, его значение по определению полагаем равным 1).
11. Докажите, что [a
0
, ..., a
n
] = [a
n
, ..., a
0
], т. е. при изменении по
-
рядка элементов на противоположный числитель дроби не меняется.
12. Докажите, что [a
0
, ..., a
n
] = a
n
[a
0
, ..., a
n−1
] + [a
0
, ..., a
n−2
].
Определение 8. Дробь, образованная первыми k этажами, называ
-
ется k-й подходящей дробью для исходной дроби. Ее величина изобра
-
жается обыкновенной дробью
[a
0
, .. ., a
k
]
[a
1
, .. ., a
k
]
, которую для краткости далее
обозначаем p
k
/
q
k
.
Определение 9. Дробь
[a
k+1
, ..., a
n
]
[a
k+2
, ..., a
n
]
называется k-м остатком
и обозначается r
k
.
13. Проверить, что
[a
0
, ..., a
n
]
[a
1
, ..., a
n
]
=
[a
0
, .. ., a
k
, r
k
]
[a
1
, .. ., a
k
, r
k
]
.
14. Докажите, что при k > 2 справедливы равенства
p
k
= a
k
p
k−1
+ p
k−2
, q
k
= a
k
q
k−1
+ q
k−2
.
15*. (Конструкция для наименьших решений в натуральных числах
уравнения ax −by = 1.) Разложим
a
b
в цепную дробь
a
b
= a
0
+
1
a
1
+
1
a
2
+
.
.
.
+
1
a
n−1
+
1
a
n
.
* Л. Эйлер (Leonhard Euler, 1707
–
1783)
––
один из самых знаменитых математиков
в истории. Родился в Базеле (Швейцария), б
´
ольшую часть своей жизни провел в Санкт
-
Пе
-
тербурге, будучи членом Петербургской академии наук.
26 Глава I. Числа и комбинаторика
Заменяя в случае необходимости a
n
на (a
n
−1) +
1
1
, можно считать, что n
нечетно. Докажите, что наименьшее решение в натуральных числах урав
-
нения ax −by = 1 есть x = q
n−1
, y = p
n−1
.
Обозначим L(a, b) минимальную длину обобщенного алгоритма Ев
-
клида для вычисления (a, b), а L
0
(a, b)
––
длину алгоритма Евклида с вы
-
бором минимального по модулю остатка.
16*. (Кронекер *.) Докажите, что L
0
(a, b) 6 L(a, b).
17*. (Дюпре **.) Докажите, что
L
0
(a, b) 6min {⌊log
α
(2
√
2 min (a, b) +
√
2)⌋, ⌊log
α
(2
√
2(a+b) +
√
2)⌋−1},
где α =
√
2 + 1.
18*. Алгоритм Евклида с выбором минимального по модулю остат
-
ка на каждом шаге не более чем вдвое короче по числу шагов деления
обычного алгоритма Евклида. Оценка достигается на паре (F
2n−1
, F
2n
).
19**. (Д. Кнут.) Число вычитаний, выполняемых бинарным алгорит
-
мом в применении к паре чисел u, v, не больше 1 + ⌊log
2
max (u, v)⌋
и равенство возможно, лишь когда ⌊log
2
(u + v)⌋> ⌊ log
2
max (u, v)⌋.
§ 1.4. Числа Фибоначчи
Определение 10. Последовательность {F
n
}, определенная равен
-
ствами
F
0
= 0, F
1
= 1, F
n
= F
n−1
+ F
n−2
, n = 2, 3, 4, .. .,
называется последовательностью Фибоначчи ***.
Числа Фибоначчи тесно связаны с цепными дробями и алгоритмом
Евклида.
Например, обозначив n
-
этажную цепную дробь 1 +
1
1+
...
1
+1
че
-
рез ϕ
n
и преобразовывая ее от n
-
этажного вида к обыкновенному, полу
-
чим дробь F
n+1
/
F
n
= ϕ
n
.
Связь с цепными дробями видна также в следующей лемме.
Лемма 2. Число одночленов в многочлене [a
1
, ..., a
n
] рав-
но F
n+1
и при любых натуральных a
1
, ..., a
n
справедливо нера-
венство F
n+1
6 [a
1
, . .., a
n
], которое обращается в равенство, лишь
когда a
1
= ... = a
n
= 1.
* Л. Кронекер (Leopold Kroneсker, 1823
–
1891)
––
известный немецкий математик. Автор
афоризма:
«
Господь создал натуральные числа. Остальное дело рук человека
»
.
** Французский математик Дюпре доказал эту теорему в середине XIX в.
*** Она появилась в XIII столетии в книге Леонардо Пизанского, по прозвищу Фибоначчи
(Leonardo da Pisa, Fibonacci, ок. 1170
–
1228), в задаче, в которой шла речь о размножении
кроликов.
§ 1.4. Числа Фибоначчи 27
Д о к а з а т е л ь с т в о. Первое утверждение леммы следует из вто
-
рого, поэтому достаточно доказать индукцией по n, что F
n+1
6 [a
1
, ..., a
n
],
причем равенство F
n+1
= [a
1
, ..., a
n
] справедливо, лишь когда a
1
= ...
... = a
n
= 1.
Удобно начинать индукцию с n = 0, полагая формально, как и раньше,
[a
1
, .. ., a
n
] = 1, F
1+a
1
+. . .+a
n
= F
1
= 1 при n = 0, тогда неравенства леммы
очевидно обращаются в равенства.
База индукции (n = 0, 1) теперь очевидна. Проведем индукционный
переход. Согласно равенству
[a
1
, ..., a
n
] = a
1
[a
2
, ..., a
n
] + [a
3
, ..., a
n
]
и предположению индукции, справедливы неравенства
F
n
6 [a
2
, ..., a
n
], F
n−1
6 [a
3
, ..., a
n
],
следовательно,
F
n+1
= F
n
+ F
n−1
6 [a
2
, ..., a
n
] + [a
3
, ..., a
n
] 6 [a
1
, ..., a
n
]
и равенство F
n+1
= [a
1
, ..., a
n
] справедливо лишь при a
1
= ... =
= a
n
= 1.
Обозначая предел последовательности ϕ
n
через ϕ и переходя к пре
-
делу в обеих частях равенства
ϕ
n
= 1 +
1
ϕ
n−1
,
получаем уравнение
ϕ = 1 +
1
ϕ
,
у которого на роль ϕ годится только положительный корень
ϕ = (
√
5 + 1)
/
2
––
так называемое золотое сечение.
Среди огромного числа фактов о числах Фибоначчи мы приведем
только небольшое количество.
Лемма 3. Для чисел Фибоначчи справедливо тождество
F
n+m
= F
m
F
n+1
+ F
m−1
F
n
, m > 1, n > 0.
Д о к а з а т е л ь с т в о. Доказательство тождества проведем индук
-
цией по m. База индукции при m = 1, 2 очевидно справедлива, а для
выполнения шага индукции достаточно проверить равенство
F
n+m+1
= F
n+m
+ F
n+m−1
= (F
m
F
n+1
+ F
m−1
F
n
) + (F
m−1
F
n+1
+ F
m−2
F
n
) =
= (F
m
+ F
m−1
)F
n+1
+ (F
m−1
+ F
m−2
)F
n
= F
m+1
F
n+1
+ F
m
F
n
.
28 Глава I. Числа и комбинаторика
Следующая теорема довольно удивительна: в ней целое число выра
-
жается через иррациональное.
Теорема 6 (Бине *). Справедлива формула
F
n
=
ϕ
n
− (−ϕ)
−n
√
5
.
Д о к а з а т е л ь с т в о. Доказательство также проведем по индук
-
ции. База индукции при n = 0, 1 очевидно справедлива, так как
ϕ − (−ϕ)
−1
√
5
=
1 +
√
5
2
−
1 −
√
5
2
√
5
= 1,
а для выполнения шага индукции достаточно проверить равенства
ϕ
2
= ϕ + 1, (−ϕ)
−2
= (−ϕ)
−1
+ 1,
из них выведите почленным умножением равенства
ϕ
n+1
= ϕ
n
+ ϕ
n−1
, (−ϕ)
−n−1
= (−ϕ)
−n
+ (−ϕ)
−n+1
и заметить, что тогда
F
n+1
= F
n
+ F
n−1
=
=
ϕ
n
− (−ϕ)
−n
√
5
+
ϕ
n−1
− (−ϕ)
−n+1
√
5
=
ϕ
n+1
− (−ϕ)
−n−1
√
5
.
Напомним, что целой частью числа x называется наибольшее целое
число n такое, что n 6 x. Обозначается целая часть символом ⌊x⌋.
Лемма 4. Неравенство F
n
6 m справедливо тогда и только
тогда, когда
n 6 ⌊log
ϕ
(
√
5(m + 1
/
2))⌋.
Неравенство F
n
> m справедливо тогда и только тогда, когда
n > ⌊log
ϕ
(
√
5(m −1
/
2))⌋+ 1.
Д о к а з а т е л ь с т в о. Для доказательства леммы перепишем нера
-
венство F
n
6 m с помощью формулы Бине в виде
ϕ
n
− (−ϕ)
−n
√
5
6 m,
что равносильно неравенствам
ϕ
n
√
5
6 m +
(−ϕ)
−n
√
5
< m +
1
2
,
* Ж. Бине (Jacques Philippe Marie Binet, 1786
–
1856)
––
французский математик и астро
-
ном, член Парижской академии наук.
§ 1.4. Числа Фибоначчи 29
так как если
ϕ
n
√
5
< m +
1
2
,
то
F
n
=
ϕ
n
− (−ϕ)
−n
√
5
< m +
1
2
−
(−ϕ)
−n
√
5
< m + 1,
и значит, F
n
6 m. Неравенство
ϕ
n
√
5
< m +
1
2
равносильно
n < log
ϕ
(
√
5(m + 1
/
2)),
а значит, и неравенству
n 6 ⌊log
ϕ
(
√
5(m + 1
/
2))⌋,
так как log
ϕ
(
√
5(m + 1
/
2)) не может быть целым числом, ведь в против
-
ном случае
ϕ
k
√
5
= m + 1
/
2,
откуда
F
k
=
ϕ
k
− (−ϕ)
−k
√
5
= m +
1
2
−
(−ϕ)
−n
√
5
= m + α, 0 < α < 1,
что невозможно, так как F
k
––
целое число.
Второе утверждение леммы очевидно равносильно первому.
Отметим, что из леммы вытекает, что последовательность
Φ(m) = ⌊log
ϕ
(
√
5(m + 1
/
2))⌋
обратна к последовательности Фибоначчи F
n
в том смысле, что
Φ(F
n
) = n.
Теорема 7 (Дюпре). Наибольшее число делений в алгоритме Ев-
клида нахождения (a, b) не превосходит
⌊log
ϕ
(
√
5 (min (a, b) + 1
/
2))⌋.
Оценка точная.
Д о к а з а т е л ь с т в о. Можно считать, что a > b. Пусть число де
-
лений равно k + 1, значит, a
/
b представимо k
-
этажной дробью
[a
0
, ..., a
k
]
[a
1
, ..., a
k
]
,
а так как [a
0
, ..., a
k
] и [a
1
, ..., a
k
] взаимно просты, то
[a
1
, ..., a
k
] 6 b,
30 Глава I. Числа и комбинаторика
и из леммы 2 следует, что F
k
6 b, а из леммы 4 следует, что
k 6 ⌊log
ϕ
(
√
5(b + 1
/
2))⌋.
На практике более удобно для применения следующее утверждение.
Следствие из теоремы 7 (Ламе *). Наибольшее число делений
в алгоритме Евклида нахождения (a, b) не превосходит 5k, где k
––
число десятичных знаков в наименьшем из чисел a, b.
Задачи и упражнения к § 1.4
1. Проверьте, что F
n
––
ближайшее целое к числу ϕ
n
/
√
5.
2. Докажите следствие из теоремы 7.
3. Сколькими способами можно замостить прямоугольник размера
2 ×n фишками домино размера 1 ×2?
У к а з а н и е. Можно применить задачу 10 из § 1.3 и лемму 3.
4. Сколько подмножеств можно выбрать в множестве чисел от 1
до n, не включающих двух соседних чисел?
У к а з а н и е. Можно применить задачу 10 из § 1.3 и лемму 3.
5. Докажите, что F
m+1
F
n
−F
m
F
n+1
= (−1)
m
F
n−m
.
6. Докажите, что (F
n
, F
n+1
) = 1.
7. Если продолжить последовательность Фибоначчи в
«
отрицатель
-
ную
»
сторону с сохранением равенства F
n
+ F
n+1
= F
n+2
, то будут вы
-
полняться равенства F
−k−1
= (−1)
k
F
k
и сохранятся все формулы преды
-
дущих задач.
Следующая задача обобщает задачу 6.
8*. (Люка **.) Докажите, что (F
n
, F
m
) = F
(n,m)
.
9. Последовательность Фибоначчи содержит бесконечно много по
-
парно взаимно простых чисел.
10*. Вместо чисел Фибоначчи рассмотрим остатки от их деления
на данное число m. Докажите, что последовательность остатков являет
-
ся чисто периодической с периодом, не большим m
2
−1.
11. В случае m = F
k
найдите точно период последовательности
из предыдущей задачи.
12*. Найдите остаток от деления F
n
на F
k
.
* Г. Ламе (Gabriel Lamé, 1795
–
1870)
––
французский инженер и математик, член Па
-
рижской и Петербургской академий наук.
** Эдуард Люка (Eduard Lucas, 1842
–
1891)
––
известный французский специалист по те
-
ории чисел и педагог, автор множества красивых задач и четырехтомника о математических
развлечениях, сильно сокращенный перевод которого был издан в 1885 г. в Санкт
-
Петер
-
бурге и с тех пор, к сожалению, не переиздавался.