Zolotarev's lemma

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

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

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

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

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

Например, возьмем a = 2 и p = 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).

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

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

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

я знак равно ( j , п - 1).

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

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

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

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

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

1	2	3	4	5
10	9	8	7	6

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

3	6	9	1	4
8	5	2	10	7

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

3	5	2	1	4
8	6	9	10	7

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

1	2	3	4	5
10	9	8	7	6

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

Символ Якоби

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

$\left({\frac {a}{n}}\right),$

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

Например, умножение на 2 на Z /21 Z имеет циклическое разложение (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. Таким образом, важно использовать все целые числа по модулю n , а не только единицы по модулю n, чтобы определить правильную перестановку.)

Когда n = p — нечетное простое число и a не делится на p , умножение на a фиксирует 0 по модулю p , поэтому знак умножения на a на всех числах mod p и на единицах mod p имеет одинаковый знак. Но для составного n это не так, как мы видим в примере выше.

История

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

См. Также: лемма Гаусса.

Ссылки

• Золотарёв Г. (1872). «Новая демонстрация закона взаимности Лежандра» (PDF) . Новые летописи математики . 2-я серия. 11 : 354–362.

Внешние ссылки

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