Теория чисел (расчётка)

Квадратичные вычеты

Рассмотрим некотрое простое p < q и число a < p. Если число а сравнимо с квадратом некоторого числа х по модулю p, т.е. выполняется сравнение х²  а (mod p), тогда а называют квадратичным вычетом по модулю p. В противном случае а называют квадратичным невычетом по модулю p.

Если а – квадратичный вычет, сравнение х²  а (mod p) имеет два решения: +х и –х, т.е. а имеет два квадратных корня по модулю р.

Все квадратичные вычеты находят возведением в квадрат элементов 1, 2, 3, … , (р – 1) /2.

Не все значения а < р являются квадратичными вычетами.

Пример. При р = 7 квадратичные вычеты это 1, 2, 4:

1² = 1  1 (mod 7),

2² = 4  4 (mod 7),

3² = 9  2 (mod 7),

4² = 16  2 (mod 7),

5² = 25  4 (mod 7),

6² = 36  1 (mod 7).

Каждый квадратичный вычет появляется в этом списке дважды.

Не существует никаких значений х, которые удовлетворяли бы любому из следующих уравнений:

х²  3 (mod 7),

х²  5 (mod 7),

х²  6 (mod 7).

Числа 3, 5 и 6 – квадратичные невычеты по модулю 7.

Можно доказать, что существует точно (р – 1) / 2 квадратичных вычетов по модулю р и (р – 1) / 2 квадратичных невычетов по модулю р.

Если а – квадратичный вычет по модулю р, то а имеет точно два квадратных корня: один корень между 0 и (р – 1) / 2, другой корень между (р – 1) / 2 и (р – 1).

Один из этих квадратных корней также является квадратичным вычетом по модулю р. Он называется главным квадратичным корнем.

Вычисление квадратных корней при р = 7 представлено в таблице 1.7.1.

Таблица 1.7.1 Вычисление квадратных корней при р = 7

х²  а (mod 7)

Корни

х ₁

х ₂

1²  1 (mod 7)

2²  4 (mod 7)

3²  2 (mod 7)

-1 = -1 + 7 = 6

-2 = -2 + 7 = 5

-3 = -3 + 7 = 4

Если n – призведение двух простых р и q, т.е. n = p • q, то существует точно

(p – 1) • (q – 1) / 4

квадратичных вычетов по модулю n, взаимно простых n.

Пример. По модулю 35 (р = 5, q = 7, n = 5 • 7 = 35) существуют

(5 – 1) • (7 – 1) 4 • 6

= = 6

4 4

квадратичных вычетов: 1, 4, 9, 11, 16, 29, взаимно простых с 35.

Содержание