Лемма Золотарёва - Zolotarevs lemma

В теория чисел, Лемма Золотарева заявляет, что Символ Лежандра

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

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

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

где ε обозначает подпись перестановки и π_а это перестановка ненулевых классы остатков мод п индуцированный умножение к а.

Например, возьмите а = 2 и п = 7. Ненулевые квадраты по модулю 7 равны 1, 2 и 4, поэтому (2 | 7) = 1 и (6 | 7) = −1. Умножение ненулевых чисел на 2 по модулю 7 имеет циклическое разложение (1,2,4) (3,6,5), поэтому знак этой перестановки равен 1, то есть (2 | 7). Умножение ненулевых чисел на 6 по модулю 7 имеет циклическое разложение (1,6) (2,5) (3,4), знак которого равен −1, то есть (6 | 7).

Доказательство

В общем, для любого конечная группа грамм порядка п, несложно определить сигнатуру перестановки π_грамм полученный умножением слева на элемент грамм из грамм. Подстановка π_грамм будет четным, если не будет нечетного числа орбиты ровного размера. Предполагая п даже, следовательно, условие для π_грамм быть нечетной перестановкой, когда грамм есть заказ k, в том, что п/k должно быть нечетным, или что подгруппа <грамм> создано грамм должно быть странно индекс.

Мы применим это к группе ненулевых чисел mod п, который является циклическая группа порядка п - 1. jя степень примитивный корень по модулю p будет индексное исчисление индексировать наибольший общий делитель

я = (j, п − 1).

Условие ненулевого числа mod п быть квадратичный невычет должно быть нечетной степенью первообразного корня, поэтому лемма сводится к утверждению, что я это странно, когда j странно, что правда a fortiori, и j это странно, когда я нечетно, что верно, потому что п - 1 четный (п нечетно).

Еще одно доказательство

Лемму Золотарева легко вывести из Лемма Гаусса и наоборот. Пример

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

,

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

1	2	3	4	5
10	9	8	7	6

Примените перестановку ${ Displaystyle U: х mapsto ax { pmod {p}}}$ :

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. Лемма Золотарева гласит (а/п) = 1 тогда и только тогда, когда перестановка U даже. Лемма Гаусса говорит (а / п) = 1 тогда и только тогда. V даже. Но W четно, поэтому две леммы эквивалентны для данного (но произвольного) а ип.

Символ Якоби

Эту интерпретацию символа Лежандра как знака перестановки можно распространить на Символ Якоби

{ displaystyle left ({ frac {a} {n}} right),}

куда а и п относительно простые нечетные целые числа с п > 0: а обратимый мод п, поэтому умножение на а на Z/пZ является перестановкой, и обобщение леммы Золотарева состоит в том, что указанный выше символ Якоби является знаком этой перестановки.

Например, умножение на 2 на Z/21Z имеет циклическое разложение (0) (1,2,4,8,16,11) (3,6,12) (5,10,20,19,17,13) (7,14) (9,18,15 ), поэтому знак этой перестановки равен (1) (- 1) (1) (- 1) (- 1) (1) = −1, а символ Якоби (2 | 21) равен −1. (Обратите внимание, что умножение на 2 в единицах по модулю 21 является произведением двух 6-циклов, поэтому его знак равен 1. Таким образом, важно использовать все целые числа п и не только мод юнитов п для определения правильной перестановки.)

Когда п = п нечетное простое число и а не делится на п, умножение на а исправляет 0 мод п, поэтому знак умножения на а на все номера мод п и на модуле юнитов п имеют такой же знак. Но для композита п это не так, как мы видим в примере выше.

История

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

внешняя ссылка

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