Лемма Гаусса (теория чисел)
Лемма Гаусса в теории чисел дает условие, при котором целое число является квадратичным вычетом . Хотя это бесполезно с вычислительной точки зрения, оно имеет теоретическое значение, поскольку используется в некоторых доказательствах квадратичной взаимности .
Впервые он появился в Карла Фридриха Гаусса (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 для r , 2, …, ( p − 1)/2 . Действительно, у нас есть
потому что a взаимно просто с p .
Это дает r = s , поскольку r и s — положительные наименьшие вычеты. Но их ровно ( p − 1)/2 , поэтому их значения представляют собой перестановку целых чисел 1, 2, …, ( p − 1)/2 . Поэтому,
Сравнивая с нашей первой оценкой, мы можем исключить ненулевой коэффициент
и нам осталось
Это и есть желаемый результат, поскольку по критерию Эйлера левая часть представляет собой просто альтернативное выражение символа Лежандра. .
Обобщение
[ редактировать ]Для любого нечетного простого числа p пусть a — целое число, взаимно простое с p .
Позволять быть таким набором, что представляет собой непересекающийся союз и .
Затем , где . [ 2 ]
В исходном заявлении .
Доказательство почти то же самое.
Приложения
[ редактировать ]Лемма Гаусса используется во многих [ 3 ] : Ч. 1 [ 3 ] : 9 но ни в коем случае не все известные доказательства квадратичной взаимности.
Например, Готхольд Эйзенштейн [ 3 ] : 236 использовал лемму Гаусса, чтобы доказать, что если p — нечетное простое число, то
и использовал эту формулу для доказательства квадратичной взаимности. Используя эллиптические , а не круговые функции, он доказал кубической и законы взаимности четвертой степени . [ 3 ] : Ч. 8
Леопольд Кронекер [ 3 ] : Бывший. 1.34 использовал лемму, чтобы показать, что
Переключение p и q сразу же дает квадратичную взаимность.
Он также используется в, вероятно, самых простых доказательствах «второго дополнительного закона».
Высшие силы
[ редактировать ]Обобщения леммы Гаусса можно использовать для вычисления символов вычета более высокой степени. В своей второй монографии о биквадратичной взаимности [ 4 ] : §§69–71 Гаусс использовал лемму четвертой степени, чтобы вывести формулу для биквадратичного характера 1 + i в Z [ i ] — кольце гауссовских целых чисел . Впоследствии Эйзенштейн использовал версии третьей и четвертой степени, чтобы доказать кубической и взаимность четвертой степени . [ 3 ] : Ч. 8
символ n -го остатка
[ редактировать ]Пусть k — поле алгебраических чисел с кольцом целых чисел. и пусть быть главным идеалом . Идеальная норма из определяется как мощность кольца классов вычетов. С простое это конечное поле , поэтому идеальная норма .
Предположим, что примитивный корень n-й степени из единицы и это н и взаимно просты (т.е. ). Тогда никакие два различных корня n- й степени из единицы не могут быть конгруэнтны по модулю .
Это можно доказать от противного, начав с предположения, что против , 0 < р < s ≤ п . Пусть t = s − r такое, что против , и 0 < t < n . Из определения корней единства,
и деление на x - 1 дает
Полагая x = 1 и принимая вычеты по модулю ,
Поскольку н и являются взаимно простыми, против но согласно предположению один из множителей справа должен быть равен нулю. Следовательно, предположение о том, что два различных корня конгруэнтны, неверно.
Таким образом, классы вычетов содержащие степени ζ n, являются подгруппой порядка n своей (мультипликативной) группы единиц, Поэтому порядок кратно n и
Существует аналог теоремы Ферма в . Если для , затем [ 3 ] : Ч. 4.1
и поскольку против н ,
корректно определен и конгруэнтен единственному корню n -й степени из единицы ζ n с .
Этот корень из единицы называется символом вычета n-й степени для и обозначается
Можно доказать, что [ 3 ] : Предложение 4.1.
тогда и только тогда, когда существует такая, что α ≡ η н против .
1/ n систем
[ редактировать ]Позволять — мультипликативная группа корней n-й степени из единицы, и пусть быть представителями смежных классов Тогда A называется 1/ n системным модом. [ 3 ] : Ч. 4.2
Другими словами, существуют цифры в наборе и этот набор представляет собой репрезентативный набор для
Числа 1, 2, … ( p − 1)/2 , использованные в исходной версии леммы, представляют собой систему 1/2 (mod p ).
Построить систему 1/ n несложно: пусть M — представительный набор для Выберите любой и удалим числа, соответствующие от М. Выберите 2 конгруэнтные из M и удалите числа, Повторяйте, пока M не закончится. Тогда { a 1 , a 2 , … a m } — это 1/ n системный мод.
Лемма для n- й степени
[ редактировать ]Лемму Гаусса можно распространить на символ остатка n-й степени следующим образом. [ 3 ] : Предложение 4.3. Позволять быть примитивным корнем n-й степени из единицы, главный идеал, (т.е. взаимно просто как с γ , так и с n ), и пусть A = { a 1 , a 2 , …, a m } — система 1/ n mod
Тогда для каждого i , 1 ≤ i ≤ m , существуют целые числа π ( i ) , уникальные (mod m ), и b ( i ) , уникальные (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 … am можно сократить с обеих сторон сравнения,
и теорема следует из того факта, что никакие два различных корня n- й степени из единицы не могут быть конгруэнтны (mod ).
Связь с переносом в теории групп
[ редактировать ]Пусть G — мультипликативная группа ненулевых классов вычетов в Z / p Z , и пусть H — подгруппа {+1, −1}. Рассмотрим следующие представители смежных классов H в G :
Применяя аппарат трансфера к этому набору представителей смежных классов, получаем гомоморфизм трансфера
которая оказывается картой, которая отправляет a в (−1) н , где a и n такие же, как в формулировке леммы. Тогда лемму Гаусса можно рассматривать как вычисление, которое явно идентифицирует этот гомоморфизм как характер квадратичного вычета.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Гаусс, Карл Фридрих (1965), Исследования по высшей арифметике (Disquisitiones Arithmeticae & Other Papers on Number Theory) (на немецком языке), перевод Х. Мазера (2-е изд.), Нью-Йорк: Челси, ISBN 0-8284-0191-8
- ^ Кремнизер, Коби. Лекции по теории чисел 2022 (PDF) .
- ^ Перейти обратно: а б с д и ж г час я дж Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4
- ^ Гаусс, Карл Фридрих (1832), Теория биквадратичных остатков, Commentatio secunda , том 7, Геттинген: Комментарий. Соц. королевские знания