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

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

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

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

$\left(\frac{a}{p}\right)=\epsilon ({\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$. Чётность перестановки $\epsilon ({\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$.

История

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

Примечания

• Шаблон:Статья

Ссылки

• Статья на ресурсе PlanetMath о лемме Золотарёва; включает его доказательство квадратичной взаимности.