В теории чисел , лемма Золотарева утверждает , что символ Лежандра
для целого числа 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 порядка п , то несложно определить сигнатуру перестановки π г сделал левое умножение на элемент д из G . Перестановка π g будет четной, если не будет нечетного числа орбит четного размера. Предполагая, что n четное, поэтому условием для π g быть нечетной перестановкой, когда g имеет порядок k , является то, что n / k должно быть нечетным или что подгруппа < g >, сгенерированная g, должна иметь нечетный индекс .
Мы применим это к группе ненулевых чисел по модулю p , которая является циклической группой порядка p - 1. J- я степень первообразного корня по модулю p будет иметь индекс наибольшего общего делителя
- i = ( j , p - 1).
Условие того, чтобы ненулевое число по модулю p было квадратичным невычетом , должно быть нечетной степенью первообразного корня. Следовательно, лемма сводится к утверждению, что i нечетно, когда j нечетно, что верно a fortiori , и j нечетно, когда i нечетно, что верно, потому что p - 1 четно ( p нечетно).
Еще одно доказательство
Лемма Золотарева легко выводится из леммы Гаусса и наоборот . Пример
- ,
т.е. символ Лежандра ( a / p ) с a = 3 и p = 11 проиллюстрирует, как идет доказательство. Начнем с набора {1, 2,. . . , p - 1} в виде матрицы из двух строк, так что сумма двух элементов в любом столбце равна нулю по модулю p , например:
1 | 2 | 3 | 4 | 5 |
10 | 9 | 8 | 7 | 6 |
Примените перестановку :
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 |
Имеем 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 году в доказательстве квадратичной взаимности .
Рекомендации
- Золотарёв Г. (1872). "Nouvelle demonstration de la loi de Réciprocité de Legendre" (PDF) . Nouvelles Annales de Mathématiques . 2e серия. 11 : 354–362.
Внешние ссылки
- Статья в PlanetMath по лемме Золотарева; включает его доказательство квадратичной взаимности