ВУЗ:
Составители:
Рубрика:
93
2. В ходе вычислений
n
k
⎛⎞
⎜⎟
⎝⎠
«числитель» уменьшается. Почему он в ко-
нечном итоге достигает 1 или степени 2?
3. Покажите, что (для
k нечётного)
1
k
−
⎛⎞
⎜⎟
⎝⎠
= 1, если и только если k ≡
≡ 1 (mod 4).
4. Предположим, что
j и k являются нечётными числами и > 0, а так-
же, что
j ≡ k (mod n), (j, n) = 1 и n ≡ 0 или 1 (mod 4). Покажите, что
n
j
⎛⎞
⎜⎟
⎝⎠
=
=
.
n
k
⎛⎞
⎜⎟
⎝⎠
(Примените сначала теорему о взаимности к каждой части этого
уравнения. Для
n ≡ 0 (mod 4), Вы найдёте её полезной, чтобы применить к
формуле
2
k
⎛⎞
⎜⎟
⎝⎠
.
5. Предположим, что
j и k являются нечётными числами и > 0, а так-
же, что
j ≡ k (mod 4n), (j, n) = 1. Докажите с помощью вышеприведённого
пункта (4), что
n
j
⎛⎞
⎜⎟
⎝⎠
=
n
k
⎛⎞
⎜⎟
⎝⎠
. (Замените n на 4n в пункте (5)). Этот полезный
результат показывает, почему значение
n
p
⎛⎞
⎜⎟
⎝⎠
для нечётного простого числа р
зависит только от вычета
р по модулю 4n. Для n = 7, –5 и 11 модуль 4n не
может быть сокращён, несмотря на то, что для
n = 5 и –3 он может быть со-
кращён до 2
n.
6. Относительно просто написать программу для реализации метода
оценки
n
k
⎛⎞
⎜⎟
⎝⎠
, использованного в предыдущем примере. Мы постоянно со-
кращаем
n mod k, выбирая степени 2 из n, обращая n и k и повторяя процесс.
Если Вам нравится писать собственные программы, то мы предоставим еще
одну возможность. Она не включает какой-нибудь защиты от того, чтобы у
n и k оказалось бы общее кратное (что может случиться тогда с Вашим ал-
горитмом?), или, что
k – чётное число. Мы также предполагаем, что n > 0.
Программа распечатывает последовательность символов Якоби, по-
лучающуюся в результате вычислений со знаками + или – перед числами.
Каждая строка, написанная в программе, равняется первоначальному
n
k
⎛⎞
⎜⎟
⎝⎠
.
7. Пусть число
р будет вида 4k +3 и пусть a и b удовлетворяют срав-
нению
a ≡ b
2
(mod p), где p не делит a (эквивалентно p не делит b). Теорема
Ферма показывает, что
b
4k+2
≡ 1 (mod p). Используйте это, чтобы показать,
что (
a
k+1
)
2
≡ a (mod p), т. е., что x = a
k+1
является решением x
2
≡ a (mod p).
(Здесь роль
b сводится к тому, что а сравнимо с квадратом по модулю р.
Заметим, что
x
2
≡ a (mod p) ⇔ x
2
≡ b
2
(mod p) ⇔ x ≡ ±b (mod p), так как р яв-
