Русская Википедия:Лемма Золотарёва
В теории чисел, Лемма Золотарёва утверждает, что символ Лежандра
- <math>\left(\frac{a}{p}\right)</math>
для целого числа a по модулю нечётного простого числа р, которое не делит a, можно вычислить как знак перестановки:
- <math>\left(\frac{a}{p}\right) = \varepsilon(\pi_a)</math>
где ε обозначает знак перестановки и π является перестановкой ненулевых вычетов по модулю р , полученной умножением на a.
Доказательство из леммы Гаусса
Лемма Золотарёва легко выводится из леммы Гаусса и наоборот. Например,
- <math>\left(\frac{3}{11}\right)</math> ,
является символом Лежандра (a / p) при а = 3 и р = 11. Начнём с множества {1,2, …, р-1} в виде матрицы из двух строк, так, что сумма двух элементов любого столбца равна нулю по модулю р , например:
1 | 2 | 3 | 4 | 5 |
10 | 9 | 8 | 7 | 6 |
Применим перестановку <math>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>G</math> — любая конечная группа чётного порядка <math>n</math>. Пусть <math>a\in G</math> — элемент порядка <math>d</math>. С одной стороны, если <math>n=2^r q, 2\nmid q</math>, то <math>a</math> — не квадрат в <math>G</math> тогда и только тогда, когда <math>2^r \mid d</math>, то есть <math>\frac{n}{d}</math> нечётно, а <math>d</math> — чётно. С другой стороны, пусть <math>\pi_a : g\mapsto ag</math> — перестановка, порождённая элементом <math>a</math>. Ясно, что <math>\pi_a</math> может быть разложена в произведение <math>\frac{|G|}{d}</math> циклов одинаковой длины <math>d</math>. Чётность перестановки <math>\varepsilon (\pi_a)=(-1)^{\frac{|G|}{d}(d-1)}</math>. Значит <math>\pi_a</math> — нечётная перестановка тогда и только тогда, когда <math>\pi_a</math> распадается в нечётное число <math>\frac{|G|}{d}</math> циклов чётной длины <math>d</math>. Таким образом, <math>\pi_a</math> чётна тогда и только тогда, когда <math>a</math> — квадрат.
Утверждение для символа Лежандра получается, если в качестве <math>G</math> взять группу <math>\mathbb{Z}_p^{\times}</math> ненулевых вычетов по модулю <math>p</math>. Порядок этой группы равен <math>p-1</math>, а потому чётный при <math>p>2</math>.
История
Эта лемма использовалась Егором Ивановичем Золотарёвым в 1872 году в его новом доказательстве квадратичной взаимности.
Примечания
Ссылки
- Статья на ресурсе PlanetMath о лемме Золотарёва; включает его доказательство квадратичной взаимности.