Перейти к содержанию

Лемма Золотарёва

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

В теории чисел, Лемма Золотарёва утверждает, что символ Лежандра

[math]\displaystyle{ \left(\frac{a}{p}\right) }[/math]

для целого числа a по модулю нечётного простого числа р, которое не делит a, можно вычислить как знак перестановки:

[math]\displaystyle{ \left(\frac{a}{p}\right) = \varepsilon(\pi_a) }[/math]

где ε обозначает знак перестановки и π является перестановкой ненулевых вычетов по модулю р , полученной умножением на a.

Доказательство из леммы Гаусса

Лемма Золотарёва легко выводится из леммы Гаусса и наоборот. Например,

[math]\displaystyle{ \left(\frac{3}{11}\right) }[/math] ,

является символом Лежандра (a / p) при а = 3 и р = 11. Начнём с множества {1,2, …, р-1} в виде матрицы из двух строк, так, что сумма двух элементов любого столбца равна нулю по модулю р , например:

1 2 3 4 5
10 9 8 7 6

Применим перестановку [math]\displaystyle{ U: x\mapsto ax }[/math] (mod р):

3 6 9 1 4
8 5 2 10 7

Столбцы ещё обладают тем свойством, что сумма двух элементов в одном столбце равна нулю по модулю р. Теперь применим подстановку V , которая поменяет местами любые две пары, в которых верхний член был изначально нижним членом:

3 5 2 1 4
8 6 9 10 7

Наконец, применим перестановку W, которая вернёт обратно исходную матрицу:

1 2 3 4 5
10 9 8 7 6

Таким образом, W−1 = VU. Лемма Золотарёва утверждает, что (a / p) = 1 тогда и только тогда, когда перестановка U чётная. Лемма Гаусса утверждает, что (a / p) = 1,тогда и только тогда, когда V чётная. Но W чётная, так что обе леммы эквивалентны для данных (но произвольных) a и р.

Общий случай

В общем случае, пусть [math]\displaystyle{ G }[/math] — любая конечная группа чётного порядка [math]\displaystyle{ n }[/math]. Пусть [math]\displaystyle{ a\in G }[/math] — элемент порядка [math]\displaystyle{ d }[/math]. С одной стороны, если [math]\displaystyle{ n=2^r q, 2\nmid q }[/math], то [math]\displaystyle{ a }[/math] — не квадрат в [math]\displaystyle{ G }[/math] тогда и только тогда, когда [math]\displaystyle{ 2^r \mid d }[/math], то есть [math]\displaystyle{ \frac{n}{d} }[/math] нечётно, а [math]\displaystyle{ d }[/math] — чётно. С другой стороны, пусть [math]\displaystyle{ \pi_a : g\mapsto ag }[/math] — перестановка, порождённая элементом [math]\displaystyle{ a }[/math]. Ясно, что [math]\displaystyle{ \pi_a }[/math] может быть разложена в произведение [math]\displaystyle{ \frac{|G|}{d} }[/math] циклов одинаковой длины [math]\displaystyle{ d }[/math]. Чётность перестановки [math]\displaystyle{ \varepsilon (\pi_a)=(-1)^{\frac{|G|}{d}(d-1)} }[/math]. Значит [math]\displaystyle{ \pi_a }[/math] — нечётная перестановка тогда и только тогда, когда [math]\displaystyle{ \pi_a }[/math] распадается в нечётное число [math]\displaystyle{ \frac{|G|}{d} }[/math] циклов чётной длины [math]\displaystyle{ d }[/math]. Таким образом, [math]\displaystyle{ \pi_a }[/math] чётна тогда и только тогда, когда [math]\displaystyle{ a }[/math] — квадрат.

Утверждение для символа Лежандра получается, если в качестве [math]\displaystyle{ G }[/math] взять группу [math]\displaystyle{ \mathbb{Z}_p^{\times} }[/math] ненулевых вычетов по модулю [math]\displaystyle{ p }[/math]. Порядок этой группы равен [math]\displaystyle{ p-1 }[/math], а потому чётный при [math]\displaystyle{ p\gt 2 }[/math].

История

Эта лемма использовалась Егором Ивановичем Золотарёвым в 1872 году в его новом доказательстве квадратичной взаимности.

Примечания

Ссылки