Дискретная математика. Ерош И.Л - 127 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

127
модулю p можно найти возведением в квадрат чисел 1, 2, 3,..., (p–1)/2.
Таким образом, для любого p имеется ровно (p–1)/2 квадратичных вы
четов и столько же квадратичных невычетов.
Упражнения.
Найдите квадратичные вычеты и квадратичные невычеты по про
стым модулям p = 11, 13, 17, 19, 23.
Символ Лежандра для целого a и простого p > 2 определяется сле
дующим образом:
0, если делит ;
1, если – квадратичный вычет по модулю ;
1, если – квадратичный невычет по модулю .
pa
a
aр
p
a
р
1
23
4
5
6
78
9
4
Понятно, что a можно заменить любым целым числом, сравнимым
с a по модулю p, при этом символ Лежандра не изменится. Вычисление
символа Лежандра удобно производить по формуле
(–1)/2
mod .
p
a
ap
p
12
3
45
67
Действительно:
2
8
81mod5.
5
12
3 45
67
89
Упражнения.
Вычислите следующие символы Лежандра:
7 3 11 35 169 523
, , , , , .
57 71113 13
12 121 21 2 1 2 1 2
3 4 3 4 3 4 3 4 3 4 3 4
56 565 65 6 5 6 5 6
Символ Якоби является обобщением символа Лежандра на слу
чай произвольного нечетного модуля n > 2. Пусть число n представ
лено в канонической форме:
12
1
2
... .
k
s
ss
k
npp p1
Тогда символ Якоби оп
ределяется как произведение символов Лежандра:
12
12
... .
k
s
ss
k
a
aa
a
p
pp
n
121212
12
3
45
4545
45
67
6767 67
Например, пусть n = 363 825 = 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.
Тогда символ Якоби можно вычислить следующим образом:

Страницы