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

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

\left({\frac {a}{p}}\right)

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

\left({\frac {a}{p}}\right)=\varepsilon (\pi _{a})

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

Доказательство из леммы Гаусса[править | править код]

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

\left({\frac {3}{11}}\right)

,

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

1	2	3	4	5
10	9	8	7	6

Применим перестановку $U:x\mapsto ax$ (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⁻¹ = VU. Лемма Золотарёва утверждает, что (a / p) = 1 тогда и только тогда, когда перестановка U чётная. Лемма Гаусса утверждает, что (a / p) = 1,тогда и только тогда, когда V чётная. Но W чётная, так что обе леммы эквивалентны для данных (но произвольных) a и р.

Общий случай[править | править код]

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

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