В теории чисел лемма Золотарева утверждает, что символ Лежандра
для целого числа a по модулю нечетного простого числа p , где p не делит 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 будет иметь индекс, равный наибольшему общему делителю.
Условием того, чтобы ненулевое число по модулю p было квадратичным невычетом, является нечетная степень примитивного корня. Таким образом, лемма сводится к утверждению, что i нечетно, когда j нечетно, что тем более верно , и j нечетно, когда i нечетно, что верно, потому что p − 1 четно ( p нечетно).
Лемму Золотарева легко вывести из леммы Гаусса и наоборот . Пример
т. е. символ Лежандра ( a / p ) с a = 3 и p = 11 проиллюстрирует ход доказательства. Начните с набора {1, 2, . . . , p − 1}, организованный в виде матрицы из двух строк, так что сумма двух элементов в любом столбце равна нулю по модулю p , скажем:
Примените перестановку :
Столбцы по-прежнему обладают тем свойством, что сумма двух элементов в одном столбце равна нулю по модулю p . Теперь примените перестановку V , которая меняет местами любые пары, в которых верхний член изначально был нижним:
Наконец, примените перестановку W, которая возвращает исходную матрицу:
Имеем W −1 = VU . Лемма Золотарева гласит, что ( a / p ) = 1 тогда и только тогда, когда перестановка U четна. Лемма Гаусса гласит ( a/p ) = 1 тогда и только тогда, когда V четно . Но W четно, поэтому две леммы эквивалентны для данных (но произвольных) a и p .
Эту интерпретацию символа Лежандра как знака перестановки можно распространить на символ Якоби.
где 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 году в доказательстве квадратичной взаимности .
