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

UptoLike

ВУЗ: 

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

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

Рубрика: 

126
6.1.12. Квадратичные вычеты. Символ Лежандра. Символ Якоби
Рассмотрим поле Галуа F(p
h
) при p > 2 и h – целом. Исключим из
элементов поля нулевой элемент, а оставшееся множество обозначим
F
*
(p
h
). Если некоторый элемент a Î F
*
(p
h
) есть квадрат некоторого эле
мента x Î F*(p
h
), то a называют квадратичным вычетом, если же та
кого элемента x не найдется в F
*
(p
h
), то a называют квадратичным не+
вычетом.
Пример. Рассмотрим поле F(3
2
). Все элементы поля можно предста
вить в виде 0, 1, 2, a, a + 1, a + 2, 2a, 2a + 1, 2a + 2, где a – корень
некоторого неприводимого полинома степени 2 над полем F(3). Возьмем
в качестве такого полинома P(X) = X
2
–X–1. Тогда P(a) = a
2
–a–1 = 0.
При выполнении вычислений будем производить замену: a
2
= a+1.
F
*
(3
2
) будет содержать все те же элементы, кроме элемента 0, а имен
но: 1, 2, a, a + 1, a + 2, 2a, 2a + 1, 2a + 2. Будем последовательно
возводить в квадрат все элементы поля (кроме нулевого) и выявлять
квадратичные вычеты:
1
2
= 1; 2
2
= 1; a
2
= a+1; (a + 1)
2
= a
2
+ 2a+1 = a + 1 + 2a + 1 = 2;
(a+ 2)
2
= a
2
+ 4a+4 = (a+ 1) + 4a+4 = 2a+2; (2a)
2
= 4a
2
= (a + 1);
(2a + 1)
2
= 4a
2
+ 4a + 1 = a+ 1 + 4a + 1 = 2a + 2;
(2a + 2)
2
= 4a
2
+ 8a + 4 = a
2
+ 2a + 1 = 2.
Таким образом элементы 1, 2, a = 1 и 2a + 2 являются квадратич
ными вычетами, а остальные элементы a, a + 2, 2a и 2a + 1 – квадра
тичными невычетами.
Упражнения.
Найдите квадратичные вычеты и квадратичные невычеты в полях
Галуа: F(3
3
), F(5
2
).
Пусть теперь h = 1. Рассмотрим поле F(p) с элементами 0, 1, 2,...,
p–1. Если исключить элемент 0, то для остальных элементов поля
можно также определить, являются они квадратичными вычетами или
невычетами. Ясно, что элемент a, 1 £ a £ p–1 будет квадратичным вы
четом по модулю p тогда и только тогда, когда выполняется сравнение
x
2
º a mod p, где x также является элементом поля F(p).
Пример. Пусть p = 7. Тогда 1
2
º 1 mod 7; 2
2
º 4 mod 7; 3
2
º 2 mod 7;
4
2
º 2 mod 7; 5
2
º 4 mod 7; 6
2
º 1 mod 7. Таким образом, квадратичны
ми вычетами являются числа 1, 2, 4, а квадратичными невычетами –
числа 3, 5, 6.
Если a – квадратичный вычет по модулю p, полученный возведени
ем в квадрат числа x, то это же число будет получено возведением в
квадрат числа –x º p – x mod p. Поэтому все квадратичные вычеты по

Страницы