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

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

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

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

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

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

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

${\displaystyle \left({\frac {3}{11}}\right)}$ ,

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

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

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

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

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

Общий случай

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

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

История

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

Примечания

• Zolotareff G. (фр.) // (англ.) ( : magazine. — 1872. — Vol. 11 . — P. 354—362 .

Ссылки

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