Составители:
взаимно простых с n, тогда если р - простое число и a больше 0, но
меньше р, то а представляет собой квадратичный вычет по модулю р, если
х
2
=
a
(
mod р
).
Этому требованию соответствуют не все значения. Чтобы, а было
квадратичным вычетом по модулю n, оно должно быть
квадратичным вычетом по модулю всех простых делителей n.
Например [ 22 ], если p = 7, квадратичные вычеты равны 1,2 и 4:
1
2
= 1 ≡ 1 (mod 7), 2
2
= 4 ≡ 4 (mod 7), З
2
= 9 ≡ 2 (mod 7),
4
2
=16 ≡2(mod 7), 5
2
= 25 ≡ 4(mod 7), 6
2
= 36 ≡1 (mod 7).
Следует обратить внимание на то, что в этом списке каждый
квадратичный вычет появляется дважды. Таким образом, если а -
квадратичный вычет по модулю р, то у a есть ровно два квадратных
корня, причем значение одного из корней находится между 0 и
(р - 1)/2, а второго - между (p - 1)/2 и (p - 1). Один из этих
квадратных корней одновременно является квадратичным вычетом
по модулю р. Этот корень называют главным квадратным корнем. А
вот в любом из следующих уравнений не существует значений х,
удовлетворяющих этим уравнениям:
х
2
= 3 (mod 7), х
2
= 5 (mod 7), x
2
= 6(mod 7).
Числа 3, 5 и 6 являются квадратичными невычетами по модулю 7.
Если n - произведение двух простых чисел р и q, тогда
существует ровно (р - 1)(q - l)/4 квадратичных вычетов по модулю n.
Квадратичный вычет по модулю n является полным квадратом по
модулю n и, поскольку чтобы быть квадратом по модулю n, вычет
должен быть квадратом по модулю р и квадратом по модулю q.
Например, по модулю 35 (p = 5, q = 7, n =5 ⋅ 7=35) существуют
[(5 - 1)(7 - 1)]/4 = (4 ⋅ 6)/4 = 6 квадратичных вычетов: 1, 4, 9, 11, 16,
29, взаимно простых с 35.
165
Страницы
- « первая
- ‹ предыдущая
- …
- 161
- 162
- 163
- 164
- 165
- …
- следующая ›
- последняя »
