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

UptoLike

ВУЗ: 

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

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

Рубрика: 

128
32213221
863 863 863 863 863 2 3 2 5
363825 3 5 7 11 3 5 7 11
1 2 1 21 21 21 2 1212121 2
333
4 5 4 54 54 54 5 4545454 5
6 7 6 76 76 76 7 6767676 7
= (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
1 21212
3
4 54545
6 76767
Тогда
.
abb a b b a
nnnnn
1 212121212
33
4 545454545
6 767676767
Для некоторых значений a символ Якоби вычисляется без перевода
n в каноническую форму следующим образом:
1
1;
n
12
3
45
67
(–1)/2
1
(1) ;
n
n
1
2 3
41
56
78
2
(1)/8
2
(1) .
n
n
12
3 4
56
78
При вычислении символа Якоби основное сведение выполняется на
основе закона взаимности:
(1)(1)/4
(1) ,
mn
mn
nm
12 12
34
56 56
78 78
где m и n – нечетные числа, большие двух.
Если не выполняется сравнение m º n º 3 mod 4, то
.
mn
nm
1212
3
4545
6767
Если же это сравнение выполняется, то
.
mn
nm
12 12
34
56 56
78 78
Пример. Определить, является ли число a = 369 квадратичным вы
четом или квадратичным невычетом по модулю 247?
369 º 1 mod 4, поэтому можно вычислить:

Страницы