Составители:
Рубрика:
21
Упражнения
Вычислите следующие символы Лежандра:
7 3 11 35 169 523
,, , , , .
577 1113 13
Символ Якоби является обобщением символа Лежандра на случай
произвольного нечетного модуля n > 2. Пусть число n представлено в
канонической форме: n = p
1
s
1
p
2
s
2
...p
k
s
k
. Тогда символ Якоби определяет-
ся как произведение символов Лежандра:
12
12
.
k
s
ss
k
a
aa
a
p
pp
n
=
K
Например, пусть n = 363825=3
3
5
2
7
2
11
1
. Найдем символ Якоби для
числа a = 863. Сначала найдем наименьший положительный вычет чис-
ла 863 по модулям p = 3, 5, 7 и 11.
863 ≡ 2 mod 3; 863 ≡ 3 mod 5; 863 ≡ 2 mod 7; 863 ≡ 5 mod 11.
Тогда символ Якоби можно вычислить следующим образом:
32213221
863 863 863 863 863 2 3 2 5
363825 3 5 7 11 3 5 7 11
==
(2
1
≡ –1 mod 3)
3
(3
2
≡ –1 mod 5)
2
(2
3
≡ 1 mod 7)
2
(5
5
≡ 1 mod 11)
1
=
= (–1)(1)(1)(1) = –1. Таким образом, число 863 является квадратич-
ным невычетом по модулю 363825.
Для произведения чисел справедливо свойство мультипликативности:
.
ab a b
nnn
=
Тогда
.
abb a b b a
nnnnn
==
Для некоторых значений a символ Якоби вычисляется без перевода
n в каноническую форму следующим образом
()
()
()
()
2
1/2 1/8
1-1 2
1; 1 ; 1 .
nn
nn n
−−
==− =−
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
