Лемма Золотарёва
В теории чисел, Лемма Золотарёва утверждает, что символ Лежандра
- [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 году в его новом доказательстве квадратичной взаимности.
Примечания
- Zolotareff G. Nouvelle démonstration de la loi de de réciprocité de Legendre (фр.) // Nouvelles Annales de Mathématiques[англ.] : magazine. — 1872. — Vol. 11. — P. 354—362.
Ссылки
- Статья на ресурсе PlanetMath о лемме Золотарёва; включает его доказательство квадратичной взаимности.