Лемма Гаусса в теории чисел дает условие, чтобы целое число было квадратичным вычетом . Хотя это бесполезно с вычислительной точки зрения, оно имеет теоретическое значение, поскольку участвует в некоторых доказательствах квадратичной взаимности .
Он сделал свое первое появление в Гаусс третьего доказательства «s (1808) [1] : 458-462 из квадратичной взаимности , и он доказал это еще раз в своем пятом доказательстве (1818). [1] : 496–501
Утверждение леммы
Для любого нечетного простого числа p пусть a - целое число, взаимно простое с p .
Рассмотрим целые числа
и их наименьшие положительные вычеты по модулю p . (Все эти вычеты различны, поэтому их ( p - 1) / 2 ).
Пусть n будет числом этих вычетов, превышающих p / 2 . потом
где - символ Лежандра .
Пример
Взяв p = 11 и a = 7, соответствующая последовательность целых чисел будет
- 7, 14, 21, 28, 35.
После редукции по модулю 11 эта последовательность принимает вид
- 7, 3, 10, 6, 2.
Три из этих целых чисел больше 11/2 (а именно 6, 7 и 10), поэтому n = 3. Соответственно лемма Гаусса предсказывает, что
Это действительно правильно, потому что 7 не является квадратичным вычетом по модулю 11.
Вышеуказанная последовательность остатков
- 7, 3, 10, 6, 2
также может быть написано
- −4, 3, −1, −5, 2.
В этой форме целые числа больше 11/2 отображаются как отрицательные числа. Также очевидно, что абсолютные значения остатков представляют собой перестановку остатков
- 1, 2, 3, 4, 5.
Доказательство
Довольно простое доказательство [1] : 458–462, напоминающее одно из простейших доказательств малой теоремы Ферма , может быть получено путем вычисления произведения
по модулю p двумя разными способами. С одной стороны, это равно
Вторая оценка требует больше работы. Если x - ненулевой остаток по модулю p , давайте определим «абсолютное значение» x как
Поскольку n учитывает те кратные ka, которые находятся в последнем диапазоне, и поскольку для этих кратных значений - ka находится в первом диапазоне, мы имеем
Теперь заметьте, что значения | ра | в отличие для г = 1, 2, ..., ( р - 1) / 2 . Действительно, у нас есть
потому что a взаимно просто с p .
Это дает r = s , поскольку r и s положительные наименьшие вычеты. Но их ровно ( p - 1) / 2 , поэтому их значения представляют собой перестановку целых чисел 1, 2,…, ( p - 1) / 2 . Следовательно,
Сравнивая с нашей первой оценкой, мы можем исключить ненулевой множитель
и мы остались с
Это желаемый результат, потому что по критерию Эйлера левая часть представляет собой просто альтернативное выражение для символа Лежандра..
Приложения
Лемма Гаусса используется во многих [2] : гл. 1 [2] : 9, но далеко не все известные доказательства квадратичной взаимности.
Например, Готтхольд Эйзенштейн [2] : 236 использовал лемму Гаусса, чтобы доказать, что если p - нечетное простое число, то
и использовал эту формулу для доказательства квадратичной взаимности. Используя эллиптические, а не круговые функции, он доказал кубический и квадратичный законы взаимности . [2] : гл. 8
Леопольд Кронекер [2] : Исх. 1.34 использовал лемму, чтобы показать, что
Переключение p и q немедленно дает квадратичную взаимность.
Он также используется в, вероятно, самых простых доказательствах «второго дополнительного закона».
Высшие силы
Обобщения леммы Гаусса можно использовать для вычисления символов вычета более высокой степени. В своей второй монографии о биквадратичной взаимности [3] : §§69–71 Гаусс использовал лемму о четвертой степени, чтобы вывести формулу для биквадратичного характера 1 + i в Z [ i ] , кольце гауссовских целых чисел . Впоследствии Эйзенштейн использовал версии в третьей и четвертой степени, чтобы доказать взаимность кубической и четвертой степени . [2] : гл. 8
n- й символ степенного остатка
Пусть k - поле алгебраических чисел с кольцом целых чисел и разреши быть главным идеалом . Идеальная норма из определяется как мощность кольца классов вычетов. Спростое это конечное поле , поэтому идеальная норма .
Предположим, что примитивный корень n- й степени из единицы и что n иявляются взаимно простыми (т.е.). Тогда никакие два различных корня n- й степени из единицы не могут быть сравнимы по модулю.
Это можно доказать от противного, начав с предположения, что мод , 0 < r < s ≤ n . Пусть t = s - r такое, что мод , и 0 < t < n . Из определения корней единства
и деление на x - 1 дает
Положив x = 1 и взяв вычеты по модулю,
Поскольку n и взаимно просты, мод но согласно предположению, один из факторов справа должен быть равен нулю. Следовательно, предположение, что два различных корня конгруэнтны, неверно.
Таким образом, классы вычетов содержащие степени ζ n являются подгруппой порядка n своей (мультипликативной) группы единиц, Следовательно, порядок делится на n , и
Аналог теоремы Ферма имеется в . Если для , то [2] : гл. 4.1
и с тех пор мод n ,
корректно определено и конгруэнтно единственному корню n- й степени из единицы ζ n s .
Этот корень из единицы называется символом вычета степени n для и обозначается
Можно доказать, что [2] : Предложение 4.1
тогда и только тогда, когда есть такое, что α ≡ η n mod.
1 / п систем
Позволять - мультипликативная группа корней n- й степени из единицы, и пусть быть представителями смежных классов Тогда A называется модом системы 1 / n.[2] : гл. 4.2
Другими словами, есть числа в наборе и этот набор представляет собой репрезентативный набор для
Числа 1, 2,… ( p - 1) / 2 , использованные в исходной версии леммы, представляют собой систему 1/2 (mod p ).
Построить систему 1 / n несложно: пусть M будет репрезентативным множеством для Выберите любой и удалите числа, соответствующие от М . Выберите в 2 из M и удалить число конгруэнтныПовторяйте, пока М. не истощится. Тогда { a 1 , a 2 ,… a m } является модулем системы 1 / n.
Лемма для n- й степени
Лемму Гаусса можно распространить на символ вычета степени n следующим образом. [2] : Предложение 4.3. Пустьбыть примитивным корнем n- й степени из единицы, главный идеал, (т.е. взаимно проста как с γ, так и с n ), и пусть A = { a 1 , a 2 ,…, a m } - система 1 / n mod
Тогда для каждого i , 1 ≤ i ≤ m , существуют целые числа π ( i ) , unique (mod m ), и b ( i ) , unique (mod n ), такие, что
а символ остатка n- й степени задается формулой
Классическая лемма для квадратичного символа Лежандра - это частный случай n = 2 , ζ 2 = −1 , A = {1, 2,…, ( p - 1) / 2} , b ( k ) = 1, если ak > p / 2 , b ( k ) = 0, если ak < p / 2 .
Доказательство
Доказательство леммы о степени n использует те же идеи, что и при доказательстве квадратичной леммы.
Существование целых чисел π ( i ) и b ( i ) и их уникальность (mod m ) и (mod n ), соответственно, проистекают из того факта, что Aμ является репрезентативным множеством.
Предположим, что π ( i ) = π ( j ) = p , т. Е.
а также
потом
Поскольку γ ивзаимно просты, обе части делятся на γ , что дает
что, поскольку A - система 1 / n , влечет s = r и i = j , показывая, что π является перестановкой множества {1, 2,…, m } .
Тогда, с одной стороны, по определению символа степенного вычета,
а с другой стороны, поскольку π - перестановка,
так
и поскольку для всех 1 ≤ i ≤ m , a i ивзаимно просты, a 1 a 2 … a m можно сократить с обеих сторон сравнения,
и теорема следует из того факта, что никакие два различных корня n- й степени из единицы не могут быть конгруэнтными (mod).
Отношение к переносу в теории групп
Пусть G - мультипликативная группа ненулевых классов вычетов в Z / p Z , и пусть H - подгруппа {+1, −1}. Рассмотрим следующие представители смежных классов группы H в G :
Применяя технику переноса к этому набору представителей смежных классов, мы получаем гомоморфизм переноса
которое оказывается отображением, которое отправляет a в (−1) n , где a и n такие, как в формулировке леммы. Тогда лемму Гаусса можно рассматривать как вычисление, которое явно идентифицирует этот гомоморфизм как характер квадратичного вычета.
Смотрите также
Две другие характеризации квадратов по простому модулю - это критерий Эйлера и лемма Золотарева .
Рекомендации
- ^ a b c Гаусс, Карл Фридрих (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae и другие статьи по теории чисел) (на немецком языке), перевод Х. Мазера (2-е изд.), Нью-Йорк: Челси, ISBN 0-8284-0191-8
- ^ Б с д е е г ч я J Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4
- ^ Гаусс, Карл Фридрих (1832), Theoria резидуум biquadraticorum, Commentatio secunda , 7 , Геттинген: Комментарий. Soc. regiae sci