Составители:
Рубрика:
20
Пусть теперь 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. Поэтому все квадратичные вычеты по
модулю p можно найти возведением в квадрат чисел 1, 2, 3, ..., (p – 1)/2.
Таким образом, для любого p имеется ровно (p – 1)/2 квадратичных
вычетов и столько же квадратичных невычетов.
Упражнения
a) Найдите квадратичные вычеты и квадратичные невычеты по про-
стым модулям p = 11, 13, 17, 19, 23.
Символ Лежандра для целого a и простого p > 2 определяется сле-
дующим образом
0, если делит ;
1, если квадратичный вычет по модулю ;
1, если квадратичный невычет по модулю .
pa
a
ap
p
ap
=−
−−
Понятно, что a можно заменить любым целым числом, сравнимым
с a по модулю p, при этом символ Лежандра не изменится. Вычисление
символа Лежандра удобно производить по формуле
a
p
= a
(p–1)/2
mod p.
Действительно,
8
5
= 8
2
є –1 mod 5.
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
