Гашков С.Б. Современная элементарная алгебра в задачах и решениях
Подождите немного. Документ загружается.
§ 2.8. Первообразные корни 111
Задачи и упражнения к § 2.8
1. Найдите необходимое и достаточное условие того, что арифметиче
-
ская прогрессия an + b содержит бесконечно много квадратов натураль
-
ных чисел.
2. Докажите, что
−1
p
=
(
−1, если p = 4k + 3;
1, если p = 4k + 1.
Далее p
––
простое, p > 2.
3. Докажите индукцией, что (1 + p)
p
k
≡1 + p
k
(mod p
k+1
).
4*. Докажите, что элемент
1 + p ∈Z
∗
p
n
порождает циклическую
подгруппу порядка p
n−1
, состоящую из всех элементов вида
1 + ps,
s = 0, 1, .. ., p
n−1
−1.
5*. Докажите, что если натуральное g таково, что
¯
g
––
первообразный
корень группы Z
∗
p
, то элемент gp
n−1
группы Z
∗
p
n
порождает циклическую
подгруппу порядка p −1.
6*. Докажите, что если порядки элементов g и h взаимно просты,
то порядок элемента gh равен их произведению.
7*. Используя задачи 4, 5, 6, дайте еще одно доказательство суще
-
ствования первообразного корня в группе Z
∗
p
n
.
8. Докажите, что
¯
2
––
первообразный корень в группах Z
∗
5
n
и Z
∗
3
n
.
9. Докажите, что элемент
¯
3, так же, как и
¯
5, порождает в группе Z
∗
2
n
циклическую подгруппу порядка 2
n−2
.
10. Докажите, что если число
2
n
−2
n
целое, то и число
2
2
n
−1
−2
2
n
−1
тоже
целое.
11*. Докажите, что для любого нечетного a и l > 1 число
a
2
l−1
−1
2
l
целое.
12*. Найдите наибольшее k, при котором
а) число
3
2
n
−1
/
2
k
––
целое,
б) число
2
3
n
+ 1
/
3
k
––
целое.
13. Докажите, что 3
k+1
| (4
m
−4
n
) тогда и только тогда, когда
3
k
| (m −n).
14. Числа a, b, n
––
натуральные, n
––
нечетное, a
n
+ b
n
и a + b делят
-
ся на n. Докажите, что
a
n
+ b
n
a + b
также делится на n.
112 Глава II. Числа и группы
15*. Числа a, b, a 6= b, n
––
натуральные, a
n
−b
n
делится на n. Дока
-
жите, что
a
n
−b
n
a − b
также делится на n.
16*. Если для некоторого целого a
a
n−1
6= 0, 1 (mod n),
то число n
––
составное.
17*. Решите сравнение x
2
≡1 (mod m) при произвольном натураль
-
ном m.
18. Докажите, что при (2a, m) = 1 сравнение ax
2
+bx +c ≡0 (mod m)
равносильно некоторому сравнению x
2
≡q (mod m).
19*. Докажите, что при простом p сравнение
a
n
x
n
+ ... + a
1
x + a
0
≡0 (mod p)
равносильно некоторому сравнению
b
p−1
x
p−1
+ ... + b
1
x + b
0
≡0 (mod p).
20*. (Лагранж.) Докажите, что при простом p сравнение
a
n
x
n
+ ... + a
1
x + a
0
≡0 (mod p)
имеет не более max(n, p) решений.
21*. Если для любого простого p, p |n −1, найдется такое целое чис
-
ло a
p
, что a
(n−1)
/
p
p
6= 1 (mod n), a
n−1
p
≡1 (mod n), то число n
––
простое.
22*. Сравнение x
2
≡a (mod p
α
), p > 2
––
простое, (a, p) = 1, имеет
два решения, если
a
p
= 1, и не имеет решений, если
a
p
= −1.
23*. Сравнение x
2
≡a (mod 2
α
) имеет решение при любом a, ес
-
ли α = 1, при a ≡1 (mod 4), если α = 2, при a ≡1 (mod 8), если α > 2.
В остальных случаях оно не имеет решений. Если x ≡x
α
(mod 2
α
)
––
одно
из его решений, то все остальные его решения при α > 2 имеют вид
x ≡−x
α
(mod 2
α
),
x ≡ x
α
+ 2
α−1
(mod 2
α
),
x ≡−x
α
+ 2
α−1
(mod 2
α
).
24*. Пусть
√
a
––
обычный квадратный корень, z
––
решение сравне
-
ния z
2
≡a (mod p), где p > 2
––
простое, (a, p) = 1,
P =
(z +
√
a)
α
+ (z −
√
a)
α
2
, Q =
(z +
√
a)
α
− (z −
√
a)
α
2
√
a
.
§ 2.8. Первообразные корни 113
Докажите, что для любых целых чисел P и Q существует такое целое
число Q
′
, что QQ
′
≡1 (mod p
α
), и x ≡±PQ
′
(mod p
α
)
––
решения срав
-
нения
x
2
≡a (mod p
α
).
25. Докажите, что среди любых 6 человек найдутся либо трое попарно
знакомых, либо трое попарно незнакомых.
26*. (Рамсей.) Семнадцать ученых попарно переписываются по трем
темам. Докажите, что среди них найдутся трое, переписывающиеся по од
-
ной теме.
У к а з а н и е. Примените предыдущую задачу.
27*. (И. Шур.) Числа от 1 до 16 раскрашены в 3 разных цвета (дру
-
гими словами, разбиты на 3 непересекающихся непустых подмножества).
Докажите, что среди них найдутся числа x, y, z одного цвета такие, что
x + y = z.
У к а з а н и е. Занумеруем ученых из предыдущей задачи числами от 1
до 17 и пусть каждая пара (i, j) переписывается по теме, связанной с цве
-
том числа |i − j|.
28*. В любом конечном поле порядка более 5 найдутся такие нену
-
левые элементы x, y, z, что x
2
+ y
2
= z
2
.
29**. (А. Диксон.) Для любого простого p > 13 найдутся такие
некратные p целые числа x, y, z, что p | x
3
+ y
3
−z
3
.
У к а з а н и е. Возьмите какой
-
нибудь первообразный корень g
и покрасьте любой ненулевой элемент a поля Z
p
в цвет i = 0, 1, 2, если
a = g
3k+i
.
Доказательство квадратичного закона взаимности
методом Золотарёва
∗
В этом трудном цикле задач используется введенное в § 1.10 поня
-
тие знака перестановки π, который для краткости здесь будем обозна
-
чать ε(π). Вначале напомним одну задачу из § 1.10. Знаком перестановки
π ∈S
n
называется число ε(π) = (−1)
I(π)
, где I(π)
––
число инверсий в π.
1*. Докажите, что ε(f ◦ g) = ε(f) ·ε(g).
2*. Докажите, что ε(π) = (−1)
d(π)
, где d(π)
––
декремент π.
3*. Докажите, что цикл длины k имеет знак (−1)
k−1
.
* Золотарёв Егор Иванович (1847
–
1878)
––
выдающийся русский математик, ученик
А. Н. Коркина и П. Л. Чебышёва.
8 Гашков
114 Глава II. Числа и группы
4*. Докажите, что
ε(π) =
Q
i< j
(i − j)
Q
i< j
(π (i) − π(j))
.
5. Докажите, что
ε
1 2 ... n
n n − 1 ... 1
= (−1)
n(n−1)
/
2
.
6. Проверьте, что отображение смены знака i : Z
m
→Z
m
, задаваемое
формулой x →−x mod m, меняет порядок в Z
m
\{0} на противоположный
и соответствующая перестановка имеет знак (−1)
(n−1)(n−2)
/
2
.
7. Проверьте, что отображение сдвига Z
m
→Z
m
, задаваемое форму
-
лой x → x + k mod m, является перестановкой и имеет знак (−1)
k(n−1)
.
У к а з а н и е. Примените задачи 1 и 3.
8*. Пусть I = Z
n
= {0, 1, 2, ..., n −1}, J = Z
m
= {0, 1, 2, ..., m −1}.
Упорядочим множество I ×J в порядке (называемом лексикографиче-
ским)
{(0, 0), (0, 1), ..., (0, m −1), (1, 0), ...
..., (1, m −1), . .., (n −1, 0), . . ., (n −1, m −1)}.
Рассмотрим перестановку, которая переводит этот порядок в порядок
{(0, 0), (1, 0), ..., (n −1, 0), (0, 1), .. .
..., (n −1, 1), ..., (0, m −1), . . ., (n −1, m −1)}
(тоже лексикографический). Докажите, что знак этой перестановки равен
(−1)
n(n−1)
2
m(m−1)
2
.
9. Пусть далее m, n
––
взаимно простые нечетные числа. Проверьте,
что отображение
π
n,m
: Z
m
→Z
m
,
задаваемое равенством π
n,m
(x) = nx mod m (т. е. умножение на n по мо
-
дулю m), является перестановкой множества Z
m
.
Знак перестановки π
n,m
назовем символом Золотарёва и обозначим
(n |m).
10. Докажите следующие свойства символа Золотарёва:
(i) если n = n
′
mod m, то (n |m) = (n
′
|m),
(ii) (nn
′
|m) = (n |m) (n
′
|m).
У к а з а н и е. Примените задачу 1.
11. Докажите, что (−1 |m) = (−1)
(m−1)
/
2
.
У к а з а н и е. Примените задачу 6.
§ 2.8. Первообразные корни 115
12*. Докажите, что (2 |m) = (−1)
(m
2
−1)
/
8
.
У к а з а н и е. Примените определение знака перестановки.
13. Докажите, что (n | p) = n
(p−1)
/
2
для нечетного простого p.
У к а з а н и е. Примените задачу 4 и заметьте, что вычисление
Q
16i< j< p
(ni − nj)
Q
16i< j< p
(i − j)
=
Y
16i< j< p
n = n
p(p−1)
/
2
= n
(p−1)
/
2
,
использующее малую теорему Ферма, можно проделать в конечном по
-
ле Z
p
.
14. Определим две перестановки σ, τ множества I × J равенствами
σ(i, j) = ((mi + j) mod n, j), τ (i, j) = (i, (n j + i) mod m),
0 6 i < n, 0 6 j < m.
Докажите, что ε(σ) = (m |n), ε(τ) = (n |m).
У к а з а н и е. Перестановка σ каждое подмножество вида I ×{j} пе
-
реводит в себя, и на нем действует так же, как перестановка σ
j
(i) =
= mi + j mod n на множестве I , но последняя согласно задачам 1, 7
и определению (m |n) имеет знак
ε(σ
j
) = (−1)
(n−1) j
(m |n) = (m |n),
откуда согласно задаче 1
ε(σ) =
m−1
Y
j=0
ε(σ
j
) = (m |n)
m
= (m |n).
15. (Закон взаимности в форме Золотарёва.) Докажите, что
(m |n) (n |m) = (−1)
n(n−1)
2
m(m−1)
2
.
У к а з а н и е. Если обозначить через ϕ: I ×J = Z
n
×Z
m
→Z
nm
«
ки
-
тайский
»
изоморфизм, то ϕ(σ(i, j)) = mi + j, ϕ(τ (i, j)) = nj + i, поэтому
для перестановки ψ : Z
nm
→Z
nm
, соответствующей определенной в зада
-
че 8 и меняющей нумерацию ψ (mi + j) = nj + i, справедливо равенство
ϕ ◦τ = ψ ◦ϕ ◦σ, из которого согласно задачам 1, 8 следует равенство
ε(τ) = ε(σ)(−1)
n(n−1)
2
m(m−1)
2
= ε(σ)(−1)
(n−1)
2
(m−1)
2
.
16. Выведите из закона взаимности равенство (n |m) (n |m
′
) =
= (n |mm
′
). У к а з а н и е. Применить задачу 10.
17*. Пусть m = p
1
... p
k
, где p
i
––
простые числа, не обязательно
различные. Определим символ Якоби
“
n
m
”
как произведение символов
8*
116 Глава II. Числа и группы
Лежандра, определенных в этом параграфе:
“
n
m
”
=
„
n
p
1
«
...
„
n
p
k
«
.
Докажите, что (n |m) =
“
n
m
”
, т. е. символы Якоби и Золотарёва совпада
-
ют. Тем самым будет доказан и закон взаимности Гаусса в форме Якоби.
У к а з а н и е. Применить задачи 16, 13 и критерий Эйлера из этого
параграфа.
Дополнительные задачи и упражнения по теории чисел
и теории групп
1. Пусть целые r
i
, s
i
, i = 1, .. ., p, таковы, что
{
¯
r
i
: 1 6 i 6 p} = {
¯
s
i
: 1 6 i 6 p} = Z
p
.
Докажите, что {
r
i
s
i
: 1 6 i 6 p} 6= Z
p
при простом p > 2.
2. Докажите, что n | (2
n!
−1) при нечетных n.
3. Докажите, что n не делит 2
n
−1 при n > 1.
4. Докажите, что n не делит 3
n
+ 1 при нечетных n > 1.
5*. Докажите, что для любого m можно указать такое n, что среди
последних m цифр десятичной записи числа 2
n
будет
a) более половины девяток,
б) более половины нулей.
6*. Докажите, что степень двойки может иметь при любом k на k
-
м
месте от конца десятичной записи любую заданную цифру (кроме млад
-
шего разряда, который и является концом записи).
7*. Докажите, что степень двойки может иметь при любом k > 3
в разрядах, начиная с (k + 1)
-
го до 3k включительно, любую комбина
-
цию десятичных цифр.
8*. Докажите, что при любом заданном m последовательность
2
n
(mod 10
m
), n = 0, 1, 2, .. ., периодическая с периодом длины 4 ·5
m−1
и предпериодом длины m.
9*. Ненулевые элементы поля Z
p
, p > 2, разбиты на множества A
и B так, что произведение любых элементов A принадлежит A, произве
-
дение любых двух элементов B также принадлежит A. Докажите, что A
––
множество квадратичных вычетов, а B
––
квадратичных невычетов.
10*. Докажите, что для любого n найдется делящееся на n число,
десятичная запись которого содержит n единиц, а остальные
––
нули.
11*. Докажите, что для любого n > 1 существуют натуральные чис
-
ла m, M такие, что x
n
+ y
n
6≡M (mod m).
§ 2.8. Первообразные корни 117
12*. Докажите, что степень двойки может начинаться с любой ком
-
бинации цифр.
13*. Докажите, что
(a
n
−b
n
, n) =
a
n
−b
n
a − b
, n
,
где a, b, n
––
натуральные числа.
14*. Докажите, что если при натуральных a, n число (a
n
−1)
/
(a −1)
есть степень простого числа, то n
––
тоже простое число.
15*. (Д. Загир.) Пусть p
––
простое число вида 4k + 1. Докажите, что
преобразование
f(x, y, z) =
(2y −x, y, x − y + z), если y −z < x < 2y;
(x −2y, x −y + z, y), если 2y < x;
(x + 2z, z, y −x −z) в остальных случаях
является перестановкой порядка 2 на множестве всех натуральных ре
-
шений уравнения x
2
+ 4yz = p, имеющей лишь одну неподвижную точку,
именно, (1, 1, k).
16*. (Д. Загир.) Докажите, что уравнение x
2
+ 4yz = p имеет нечет
-
ное число натуральных решений, и так как преобразование g(x, y, z) =
= (x, z, y) тоже является перестановкой порядка 2 на множестве всех его
натуральных решений, оно имеет хотя бы одну неподвижную точку, т. е.
точку вида (x, y, y), где x
2
+ 4y
2
= p.
17*. Докажите, что простое вида 4k + 1 представимо в виде суммы
двух квадратов ровно одним способом (с точностью до перестановки сла
-
гаемых), а простые вида 4k + 3 непредставимы таким образом.
18*. Пусть n = (2
2p
−1)
/
3, p > 3,
––
простое число. Докажите, что
а) n |2
2p
−1; б) 4p(2
p−1
+ 1) |n −1; в) n |2
n
−2.
19*. (Чебышёв.) Применяя квадратичный закон взаимности, дока
-
жите, что 2
––
первообразный корень по модулю простого числа p вида
4q + 1, где q
––
простое, и по модулю простого числа p вида 2q + 1, где
q = 4k + 1
––
простое. Если же в последнем случае простое q = 4k + 3,
то первообразным корнем по модулю p = 2q + 1 будет минус два.
20*. (Чебышёв.) Применяя квадратичный закон взаимности, докажи
-
те, что 3 есть первообразный корень по модулю простого числа Ферма
2
2
n
+ 1. Применяя квадратичный закон взаимности, докажите, что 3 есть
первообразный корень по модулю простого числа вида 4 ·2
m
N + 1, где
N > 9
2
m
/
(4 ·2
m
)
—
также простое.
21. (Чебышёв.) Применяя предыдущие задачи, проверьте, что два бу
-
дет первообразным корнем по модулям 11, 59, 83, 107, 123; три будет пер
-
вообразным корнем по модулям 5, 17, 89, 137, 233, 257, 569, 809, 857, 6737,
65537; минус два будет первообразным корнем по модулям 7, 13, 47.
118 Глава II. Числа и группы
22*. Монотонная функция обладает свойством мультипликативно-
сти: для любых взаимно простых m и n для ее значений справедливо
равенство
f(mn) = f(m) f(n).
Докажите, что f(n) = n
α
для любого натурального числа n.
23. Пусть a
1
, ..., a
n
––
не обязательно различные элементы группы
порядка n. Докажите, что произведение нескольких подряд идущих эле
-
ментов равно единице.
24. Можно ли группу представить в виде объединения двух собствен
-
ных подгрупп?
25*. Любая конечная группа более чем из двух элементов имеет
нетождественный автоморфизм.
У к а з а н и е. Если группа некоммутативна, то она имеет нетож
-
дественный автоморфизм вида x →axa
−1
. Если она коммутативна
и не каждый квадрат в ней равен единице, то автоморфизм x →x
−1
––
нетождественный. В оставшихся случаях она изоморфна группе (Z
2
)
n
.
26*. (С. В. Конягин.) Пусть n
––
наименьшее число элементов a
i
,
i = 1, . . ., n, в конечной абелевой группе G, такое, что любой элемент G
можно представить в виде ±a
i
1
±a
i
2
±... Докажите, что
log
3
|G| 6 n 6 log
2
|G|.
У к а з а н и е. Для получения верхней оценки выберите максималь
-
ное множество элементов a
i
, i = 1, ..., n, такое, что все их суммы будут
попарно различны.
27**. Докажите, что существует сколь угодно много подряд идущих
натуральных чисел, не представимых в виде суммы квадратов двух нату
-
ральных чисел.
§ 2.9. Алгебра и криптология
Читатель уже имеет представление, что такое алгебра. А что такое
криптология? До недавнего времени это слово можно было услышать
только на специальных курсах в некоторых специальных учебных заве
-
дениях. Но сейчас оно стало мелькать на страницах научных журналов
и в трудах конференций. Был открыто опубликован первый в России
учебник по криптографии, написанный преподавателями академии ФСБ.
Начала появляться и популярная литература по этому вопросу, в том
числе перевод написанной еще в 1970
-
е годы книги Д. Кана
«
Взломщики
кодов
»
(M.: Центрполиграф, 2000).
§ 2.9. Алгебра и криптология 119
Нам кажется уместным дать здесь краткий, в основном исторический,
обзор на эту тему.
Криптология делится на два направления
––
криптографию и крипто
-
анализ. Криптография * защищает информацию с помощью шифрова-
ния открытого текста, на жаргоне криптографов называемого француз
-
ским словом клер.
Определение 62. Шифрование
––
это обратимое преобразование
клера в шифртекст. Оно определяется двумя взаимно обратными
отображениями E
k
: T →C и D
k
: C →T , где T
––
множество всех клеров,
C
––
множество всех шифртекстов, k
––
ключ, выбираемый из простран-
ства ключей K . Если обозначить через E множество {E
k
: k ∈ K} всех
отображений зашифрования а через D множество {D
k
: k ∈K} всех
отображений расшифрования, то для любых t ∈ T , k ∈K выполняет
-
ся равенство D
k
(E
k
(t)) = t. Тогда совокупность (T, C, K, E, D) назовем
шифром, или шифр-системой.
Простейшими и старейшими классами шифров являются шифры пе
-
рестановки и шифры замены. В этих шифрах C = T = A
n
, где A
––
алфавит
текста, n
––
длина сообщения.
Определение 63. Роль ключа k в шифре перестановки играет
произвольная перестановка k ∈S
n
из группы перестановок множества
{1, ..., n}; таким образом, пространство ключей K = S
n
, отображение
шифрования определяется равенством
E
k
(a
1
a
2
... a
n
) = a
k(1)
a
k(2)
... a
k(n)
,
а отображение расшифрования определяется равенством
D
k
(a
1
a
2
... a
n
) = a
k
−1
(1)
a
k
−1
(2)
... a
k
−1
(n)
.
Определение 64. Роль ключа k в шифре замены играет произ
-
вольная перестановка k ∈S
A
из группы перестановок алфавита A; таким
образом, пространство ключей K = S
A
, отображение шифрования опре
-
деляется равенством
E
k
(a
1
a
2
... a
n
) = k(a
1
)k(a
2
) ... k(a
n
),
а отображение расшифрования определяется равенством
D
k
(a
1
a
2
... a
n
) = k
−1
(a
1
)k
−1
(a
2
) ... k
−1
(a
n
).
Уже из этих определений видна связь криптографии с алгеброй.
Из следующих далее примеров мы увидим, что старейшими применения
-
ми группы перестановок алгебра обязана именно криптографии.
* Тайнопись в переводе с греческого.
120 Глава II. Числа и группы
П р и м е р ы. 1. Первый шифр перестановки, согласно Плутарху, ис
-
пользовали в Спарте. На цилиндр, который назывался сцитала, плотно
наматывалась узкая пергаментная лента. Вдоль оси цилиндра записы
-
вался текст. Лента сматывалась и передавалась адресату, который читал
сообщение, наматывая ленту на такую же сциталу. Ключом к шифру
является диаметр сциталы. Первый же успешный метод вскрытия шиф
-
ра приписывается Аристотелю, который предложил наматывать ленту
на конус, сдвигая ее от вершины к основанию конуса. Там, где диаметр
конического сечения совпадал с диаметром сциталы, на ленте проступали
осмысленные слоги и слова, после чего изготовлялась сцитала соответ
-
ствующего диаметра.
2. Первый шифр замены изобрел Юлий Цезарь. В качестве переста
-
новки букв алфавита использовалась перестановка, которая для совре
-
менного алфавита выглядит так:
a b c d e f g h i j k l m n o p q r s t u v w x y z
d e f g h i j k l m n o p q r s t u v w x y z a b c
––
просто циклический сдвиг на три буквы. Обратная перестановка то
-
же, естественно, является циклическим сдвигом. В общем случае в этом
шифре использовался сдвиг вида i → (i + k) mod 26 и ключом являлось
число k. Так как ключевое пространство невелико, алгоритм шифрования
Цезарь, видимо, не особо афишировал.
3. Большее ключевое пространство у аффинного шифра, так как
в нем используются перестановки вида i → (ai + k) mod 26.
4. К классу шифров перестановки относятся шифры маршрутной
перестановки. Идея у них такая. Сообщение записывается в таблицу
по одному маршруту, например по горизонталям, а считывается по дру
-
гому, например по вертикалям. Для увеличения ключевого пространства
использовалась еще перестановка столбцов таблицы.
Кроме указанных двух классов шифров, издавна известны и другие
методы шифрования. Например, вторым шифровальным приспособлени
-
ем в Спарте была таблица Энея. На ней горизонтально располагался
алфавит, а по боковым сторонам делались выемки для наматывания ни
-
ти. Нить наматывалась на таблицу, двигаясь по каждой строке в одном
направлении, и напротив букв сообщения на ней завязывались узелки,
которые и представляли собой шифртекст (фактически в двоичном ал
-
фавите). Для чтения сообщения нить наматывалась на ту же таблицу,
которая и служила ключом к шифру. История не сохранила сообщений
о вскрытии этого шифра.
Древнегреческий историк Полибий описал следующий способ шифро
-
вания. Алфавит записывался в квадратную таблицу 5 ×5 и каждая буква