Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В

• Название: Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
• Дата: 16.10.2022
• Размер: 3.28 Mb.
• Имя файла: algebra.pdf
• Тип: Учебное пособие; #736986
• страница: 58 из 71

32.30. Это следует из рекуррентного соотношения T
n
+1
(x)
=
= 2xT
n
(x)
− T
n
−1
(x), которое доказано при решении задачи 32.27.
32.31. Мы воспользуемся лишь одним свойством многочлена. . . , а именно тем, что T
n
(cos(k
p
/n))
=cos при k=0, 1, . . . , n. Рассмотрим многочлен Q(x)=
1 Его степень не превосходит n − 1, поскольку старшие члены многочленов) и P
n
(x) равны. Из того, что 6 при 6 1 следует, что в точке x
k
= cos(k
p
/n) знак числа Q(x
k
) совпадает со знаком числа T
n
(x
k
). Таким образом, в концах каждого отрезка [x
k
+1
, x
k
] многочлен Q(x) принимает значения разного знака, поэтому у многочлена Q(x) на этом отрезке есть корень.
Чуть более аккуратные рассуждения нужны в том случае, когда 0. В этом случае либо x
k
— двукратный корень, либо внутри одного из отрезков [x
k
+1
, x
k
] и [x
k
, x
k
−1
] есть ещё один корень.
Это следует из того, что в точках и многочлен принимает значения одного знака (рис. Рис. 32.1

Глава 32. Многочлены — Количество отрезков [x
k
+1
, x
k
] равно n, поэтому многочлен) имеет по крайней мере n корней. Для многочлена степени не более n − 1 это означает, что он тождественно равен нулю,
т. е. P
n
(x)
=
1 Замечание. По поводу другого решения см. задачу 11.38.
32.32. Пусть x = cos f
. Тогда T
n
(x)
= cos(n
f
)
= y и T
m
(y)
=
=cos m(n
f
), поэтому T
m
(T
n
(x))
=cos mn
f
. Аналогично T
n
(T
m
(x))
=
= cos mn
f
. Таким образом, равенство T
n
(T
m
(x))
= T
m
(T
n
(x)) выполняется при |x| < 1, а значит, это равенство выполняется при всех x.
32.33. а) Пусть n = 2k + 1 и f
= 2l
p
/n. Тогда T
k
+1
(cos f
)
−
−T
k
(cos f
)
=cos(k+1)
f
−cos k
f
. При этом (k+1)
f
+k
f
=(2k+1)
f
=
= 2l
p
. Значит, cos(k + 1)
f
= cos k
f б) Пусть n = 2k и f
= 2l
p
/n. Тогда T
k
+1
(cos f
)
− T
k
−1
(cos f
)
=
= cos(k + 1)
f
−cos(k −1)
f
. При этом (k + 1)
f
+ (k −1)
f
= 2k
f
= Значит, cos(k + 1)
f
= cos(k − 1)
f
32.34. а) Пользуясь результатом задачи 32.28, получаем T
2
−
− T
1
= 2x
2
− x − 1, T
3
− T
2
= 4x
3
− 2x
2
− 3x + 1, T
4
− T
3
= 8x
4
− 4x
3
−
− 8x
2
+ 3x + 1, T
5
− T
4
= 16x
5
− 8x
4
− 20x
3
+ 8x
2
+ 5x − б) Согласно задаче 32.33 числа cos 0=1, и являются корнями многочлена T
3
− T
2
. Поделив этот многочлен на x − получим требуемый многочлен.
в) Числа 1, cos
2
p
7
, и являются корнями многочлена. Поделив этот многочлен на x − 1, получим требуемый многочлен.
г) Числа 1, cos
2
p
9
, cos
4
p
9
, cos
6
p
9
= −
1 и являются корнями многочлена T
5
−T
4
. Поделив этот многочлен на (2x + 1)×
×(x − 1) = 2x
2
− x − 1, получим требуемый многочлен. Пусть a
= m/n — несократимая дробь. Положим x
0
=
=2 cos t, где t=
ap
. Тогда P
n
(x
0
)
=2 cos(nt)=2 cos(n
ap
)
=2 cos(m
p
)
=
= ±2. Поэтому x
0
— корень многочлена P
n
(x)
∓ 2 = x
n
+ b
1
x
n
−1
+ . . .
. . .
+ с целыми коэффициентами. Пусть x
0
= 2 cos(
ap
)
= p/q несократимая дробь. Тогда p
n
+ b
1
p
n
−1
q
+ . . . + b
n
q
n
= 0, а значит,
p
n
делится на q. Но числа p и q взаимно простые, поэтому q = те целое число. Число y
0
= является корнем многочлена+ a
1
y
n
−1
+ a
2
a
0
y
n
−2
+ . . . + a
n
−1
a
n
−2 0
y
+ a
n
a
n
−1 0
= При a
0
= 0 это очевидно, а при a
0 6= 0 нужно положить y = после сокращения на a
n
−1 получим исходный многочлен

Решения задач. Если |
a
− p/q| > 1, то требуемое неравенство выполняется при c = 1. Поэтому будем считать, что |
a
− p/q| < 1, а значит < |
a
| + 1. Запишем многочлен f(x) в виде f(x) = где a
1
=
a
. Тогда
˛
˛
˛f
“
p
q
”˛˛
˛=|a
n
|
˛
˛
˛
a
−
p
q
˛
˛
˛
n
Y
i
=2
˛
˛
˛
p
q
−
a
i
˛
˛
˛<|a
n
|
˛
˛
˛
a
−
p
q
˛
˛
˛
n
Y
i
=2
(
|
a
|+1+|
a
i
|)=c
1
˛
˛
˛
a
−
p
q
˛
˛
˛,
где c
1
— положительное число, зависящее только от |a
n
| и Будем считать, что a
0
, . . . , a
n
— целые числа, взаимно простые в совокупности. Тогда число |a
n
| полностью определяется числом a
. Кроме того, число a
n
p
n
+ a
n
−1
p
n
−1
q
+ . . . + целое, поэтому |q
n
f(p/q)
| > 1. Следовательно >
1
c
1
˛
˛
˛f
“
p
q
”˛˛
˛ где c = c
−1 1
32.38. Для каждого натурального n рассмотрим число a
=
=
n
P
k
=0 2
−k!
= p/q, где p — целое число и q = 2
n!
. При этом =
1 2
(n
+1)!
“
1 +
1 2
n
+2
+
1 2
(n
+2)(n+3)
+ . . .
”
<
2 Предположим, что a
— алгебраическое число степени N. Тогда согласно задаче 32.37
˛
˛
˛
a
−
p
q
˛
˛
˛ а значит, 2q
−n−1
>
cq
−N
, те. Но lim
n
→∞
2
n! (N
−n−1)
= 0. Приходим к противоречию. а) Пусть {
a
1
, . . . ,
a
n
} и {
b
1
, . . . ,
b
m
} — наборы чисел, со- пряжённых си соответственно. Рассмотрим многочлен

Глава 32. Многочлены — Коэффициенты этого многочлена являются симметрическими функциями от a
1
, . . . и b
1
, . . . ,
b
m
. Поэтому они являются рациональными числами.
б) Решение аналогично. Пусть {
a
1
, . . . ,
a
n
} и {
b
1
, . . . ,
b
m
} — наборы чисел, сопря- жённых си соответственно. Рассмотрим многочлен
f(x)
=
m
Y
j
=1
f
(x,
b
j
).
Коэффициенты этого многочлена рациональны и f(
a
)
= 0. Поэтому) делится на, а значит, f(
a
i
)
= 0, те для некоторого j.
32.41. Рассмотрим многочлен+ . . . где {
b
n
−1,i
}, . . . , {
b
0,l
} — все числа, сопряжённые с b
n
−1
, . . . соответственно. Легко проверить, что коэффициенты многочлена целые числа. Ясно также, что a
— корень многочлена F.
32.42. Ясно, что a
=
e
+
e
−1
, где e
= exp(k
p
/n). Пусть число сопряжено с a
. Из задачи 32.40 следует, что a
1
=
e
1
+
e
−1 где число сопряжено с e
. Число удовлетворяет уравнению, поэтому тоже будет корнем этого уравнения, а значит exp(l
p
/n). В таком случае число a
1
= 2 cos(l
p
/n) вещественно. Ясно, что все числа указанного вида должны входить в k(
a
). Поэтому достаточно доказать, что числа указанного вида образуют поле. Для этого, в свою очередь, достаточно доказать,
что произведение чисел такого вида имеет такой же вид и обратный элемент для числа такого вида тоже имеет такой вид (ясно,
что сумма чисел указанного вида имеет требуемый вид. Мы докажем более общее утверждение если f
(x) и y
(x) — многочлены с коэффициентами из поля k, причём y
(
a
)
6= 0, то f
(
a
)
y
(
a
)
= c
n
−1
a
n
−1
+ c
n
−2
a
n
−2
+ . . . + c
1
a
+ для некоторых чисел c
0
, . . . , из поля Многочлен f(x) неприводим над k, поэтому он не имеет общих делителей с y
(x). Значит, найдутся многочлены a(x) и b(x) с коэффициентами их поля k, для которых a(x)
y
(x)
+ b(x)f(x) = см. с. 437). При x =
a получаем a(
a
). Таким образом

Решения задач. Поделим многочлен f
(x)a(x) нас остатком q(x)f(x) + r(x), где r(x) — многочлен степени не выше 1. Остаётся заметить, что f
(
a
)a(
a
)
= r(
a
).
32.44. Пусть b
m
= c
m
− d
m
. Нужно доказать, что если 0, где b
0
, . . . , b
n
−1
— числа из поля k, то b
0
= b
1
= . . . = b
n
−1
= Многочлен g(x) = b
n
−1
x
n
−1
+ . . . + имеет общий корень с неприводимым многочленом f(x), поэтому g(x) делится на f(x). Но степень g(x) меньше степени f(x), поэтому g(x) = 0, те ГЛАВА АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ
Когда дело доходит до конкретных вычислений, бывает важно выбрать наиболее быстрый способ вычислений. При этом нужно иметь ввиду, что умножение двух больших чисел занимает больше времени, чем сложение.
Иррациональные числа обычно вычисляются приближённо,
поэтому при таких вычислениях важно оценить погрешность вычислений. Это относится и к приближённому представлению десятичными дробями рациональных чисел с большими числителями и знаменателями. Вычисления некоторых чисел. Докажите, что дробь . . . 4748495051 0,51504948 . . . начинается с цифр 0,239.
33.2. Докажите, что если квадрат числа начинается с 0,999 . . . 9 (100 девяток, то и само число начинается с 0,999 . . . 9 (100 девяток. Вычислите с точностью до 0,00001 произведение −
1 10

1 −
1 10 2

1 −
1 10 3

. . .

1 −
1 10 99

33.4. Докажите, что 3,14 <
p
<
3,142 и 9,86 <
p
2
<
9,87.
33.2. Арифметические операции. Многочлены. Дано число a. Докажите, что можно вычислить сделав не более 2 log
2
n умножений.

Условия задач. Чтобы вычислить значение многочлена P(x)=a
n
x
n
+
+ a
n
−1
x
n
−1
+ . . . + при x = x
0
, можно вычислить a
n
x
n
0
,
a
n
−1
x
n
−1 0
, . . . , a
1
x
0
, а затем сложить все полученные числа и a
0
. Для этого потребуется 2n − 1 умножений (вычисление
x
k
0
для k = 2, 3, . . ., n требует n − 1 умножений). Придумайте способ вычисления P(x
0
), требующий лишь n умножений и n сложений (схема Горнера).
33.7. Укажите алгоритм, позволяющий разложить данный многочлен с целыми коэффициентами на неприводимые множители (в частности, выяснить, является ли данный многочлен неприводимым. Сортировка
Задача
сортировки заключается в следующем. Дана последовательность чисел a
1
, a
2
, . . . , a
n
. Требуется их переставить так,
чтобы они были упорядочены по возрастанию a
s
(1)
6
a
s
(2)
6
. . .
. . . 6 a
s
(n)
; здесь s
(1), . . . ,
s
(n) — перестановка чисел 1, . . . , У этой задачи есть разные варианты найти наибольшее (или наименьшее) изданных чисел найти два наибольших числа;
выяснить, есть ли среди данных чисел равные, и т. п. Дано n попарно различных чисел. Требуется найти наибольшее из них, сравнивая за один шаг пару чисел.
а) Докажите, что это можно сделать за n − 1 шаг.
б) Докажите, что этого нельзя сделать меньше, чем за 1 шаг.
Известно много разных алгоритмов сортировки. Здесь мы разбе- рём некоторые из них.
Сортировка вставками заключается в следующем. Сначала сравниваем и и, если надо, меняем их местами. Затем в новой последовательности сравниваем и здесь a
2
— элемент,
который стоит нам месте в новой последовательности) и, если нужно, меняем их местами. Если элементы и пришлось поменять местами, то сравниваем и и т. д. Докажите, что для сортировки вставками количество сравнений чисел заключено между n − 1 и 1)
2

Глава 33. Алгоритмы и вычисления
Для оценки числа сравнений, достаточных для решения различных задач сортировки, часто используется результат следующей задачи. Есть куча из n > 2 камней. На первом шаге она делится примерно пополам, те. если n чётно, то она делится на две кучи из n/2 камней, а если n нечётно, тона две кучи из 1 и+ 1 камней. На втором шаге с каждой кучей,
в которой есть по крайней мере два камня, повторяется тоже самое и т. д. Процесс останавливается после го шага,
когда в каждой куче остался ровно один камень. Докажите,
что число m определяется неравенствами m − 1 < log
2
n 6 Сортировка слияниями заключается в следующем. Предположим, что у нас уже есть две отсортированные последовательности и y
1 6
y
2 6
. . . 6 y
q
. Тогда по ним можно построить отсортированную последовательность всех этих чисел следующим образом. Сравним числа и и заберём меньшее из них (если x
1
= y
1
, то забираем любое из этих чисел. Это будет первое число новой последовательности. Для оставшихся последовательностей (теперь водной из них на одно число меньше) повторяем тоже самое. Так находим второе число новой последовательности и т. д. Для сортировки произвольной последовательности чисел этот алгоритм слияния двух последовательностей используется следующим образом. Разобьём исходную последовательность n чисел примерно пополам, как это делается в задаче 33.10. После того как мы отсортируем две полученные последовательности, к ним можно будет применить алгоритм слияния. Каждую полученную последовательность мы снова делим примерно пополам (если в ней есть по крайней мере два числа) и т. д. до тех пор, пока не останутся только последовательности, каждая из которых состоит из одного числа. После этого мы начинаем сливать последовательности в порядке, обратном разбиению. Дана последовательность из n чисел. Докажите,
что для её сортировки слияниями требуется не более mn −
− 2
m
+ 1 сравнений пар чисел, где число m определяется неравенствами m − 1 < log
2
n 6 m.
33.12. В последовательности из 2n чисел требуется одновременно найти наибольшее число и наименьшее

Условия задача) Докажите, что это можно сделать, сравнив 3n −2 пары чисел.
б) Докажите, что сравнением менее 3n −2 пар чисел в общем случае нельзя обойтись. В последовательности из n различных чисел требуется одновременно найти самое большое и следующее за ним по величине.
а) Докажите, что это можно сделать, сравнив n + m − пары чисел, где целое число m определяется неравенствами 1 < log
2
n 6 б) Докажите, что сравнением менее n + m − 2 пар чисел в общем случае нельзя обойтись. Криптография с открытым ключом
Пусть m — произведение двух различных простых чисел и q. Выберем число e так, чтобы оно было взаимно просто си. Числа m и e доступны всем желающим,
а числа p и q известны только владельцу шифра. Здесь нужно сказать, что если числа p и q достаточно большие,
то с практической точки зрения восстановить их по известному числу m те. разложить m на простые множители)
невозможно.
Теперь любой желающий может зашифровать сообщение, которое представлено натуральным числом x < следующим образом числу x сопоставляется остаток отделения числа на Покажем, как владелец ключа может расшифровать это сообщение. Для расшифровки важны не исходные простые числа p и q, а натуральное число d, которое определяется следующим образом 1 (mod f
(m)),
1 6 d <
f
(m).
* Для шифровки текстового сообщения нужно преобразовать его в число по стандартному правилу пробела, б = 02, . . .

Глава 33. Алгоритмы и вычисления
Здесь f
(m)
= (p − 1)(q − 1) — функция Эйлера. Существование и единственность числа d следуют из того, что e взаимно просто с Чтобы расшифровать сообщение, нужно научиться решать сравнение x
e
≡ a (mod m). Если x взаимно просто сто согласно малой теореме Ферма x
f
(m)
≡ 1 (mod m), поэтому. Поэтому расшифровка сообщения состоит просто в возведении полученного сообщения в степень и приведении по модулю m). Легко проверить, что это остаётся верными в том случае, когда x не взаимно просто стене взаимно просто с m. Действительно, пусть
НОД(a, m) = r и s = m/r. Число m является произведением двух взаимно простых чисел, поэтому s и r — это простые числа p и q. В частности) делится на f
(s). Следовательно) и a
d
≡ x
ed
≡ x (mod s). Числа a и делятся на простое число r, поэтому a
d
≡ 0 ≡ x (mod r). Но числа r и s взаимно простые, поэтому a
d
≡ x (mod Решения. Пусть a = 0,1234 . . . 5051 и b = 0,5150 . . . 321. Требуется доказать, что 0,239b 6 a < 0,24b. Но 0,515 < b < 0,516, поэтому и 0,24b>0,24·0,515=0,1236>a.