Лемма Золотарёва - Википедия - 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} в виде матрицы из двух строк, так что сумма двух элементов в любом столбце равна нулю по модулю.п, сказать:

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

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

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

У нас есть 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 г. квадратичная взаимность.

Рекомендации

• Золотарев Г. (1872). "Nouvelle demonstration de la loi de Réciprocité de Legendre" (PDF). Nouvelles Annales de Mathématiques. 2e серия. 11: 354–362.

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

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