Лемма Гаусса (теория чисел)

Условие, при котором целое число является квадратичным вычетом

Лемма Гаусса в теории чисел дает условие для целого числа быть квадратичным вычетом . Хотя это не полезно с вычислительной точки зрения, это имеет теоретическое значение, будучи задействованным в некоторых доказательствах квадратичной взаимности .

Впервые он появился в третьем доказательстве (1808) ^{[1] : 458–462} квадратичного закона взаимности Карла Фридриха Гаусса , и он доказал его снова в своем пятом доказательстве (1818). ^{[1] : 496–501}

Утверждение леммы

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

Рассмотрим целые числа

${\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}$

и их наименьшие положительные остатки по модулю p . Все эти остатки различны, поэтому их ( p − 1)/2 .

Пусть n — число этих остатков, которые больше p / 2. Тогда

${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n},}$

где находится символ Лежандра . ${\displaystyle \left({\frac {a}{p}}\right)}$

Пример

При p = 11 и a = 7 соответствующая последовательность целых чисел имеет вид

7, 14, 21, 28, 35.

После сокращения по модулю 11 эта последовательность становится

7, 3, 10, 6, 2.

Три из этих целых чисел больше 11/2 (а именно 6, 7 и 10), поэтому n = 3. Соответственно, лемма Гаусса предсказывает, что

${\displaystyle \left({\frac {7}{11}}\right)=(-1)^{3}=-1.}$

Это действительно верно, поскольку 7 не является квадратичным вычетом по модулю 11.

Вышеуказанная последовательность остатков

7, 3, 10, 6, 2

также может быть написано

−4, 3, −1, −5, 2.

В этой форме целые числа, большие 11/2, выглядят как отрицательные числа. Также очевидно, что абсолютные значения остатков являются перестановкой остатков

1, 2, 3, 4, 5.

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

Довольно простое доказательство, ^{[1] : 458–462} напоминающее одно из простейших доказательств малой теоремы Ферма , можно получить, оценив произведение

${\displaystyle Z=a\cdot 2a\cdot 3a\cdot \cdots \cdot {\frac {p-1}{2}}a}$

по модулю p двумя разными способами. С одной стороны, это равно

${\displaystyle Z=a^{(p-1)/2}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right)}$

Вторая оценка требует больше работы. Если x — ненулевой остаток по модулю p , давайте определим «абсолютное значение» x как

${\displaystyle |x|={\begin{cases}x&{\mbox{if }}1\leq x\leq {\frac {p-1}{2}},\\p-x&{\mbox{if }}{\frac {p+1}{2}}\leq x\leq p-1.\end{cases}}}$

Поскольку n учитывает те кратные ka, которые находятся в последнем диапазоне, и поскольку для этих кратных − ka находится в первом диапазоне, мы имеем

${\displaystyle Z=(-1)^{n}\left(|a|\cdot |2a|\cdot |3a|\cdot \cdots \cdots \left|{\frac {p-1}{2}}a\right|\right).}$

Теперь заметим, что значения | ra | различны для r = 1, 2, …, ( p − 1)/2 . Действительно, мы имеем

${\displaystyle {\begin{aligned}|ra|&\equiv |sa|&{\pmod {p}}\\ra&\equiv \pm sa&{\pmod {p}}\\r&\equiv \pm s&{\pmod {p}}\end{aligned}}}$

поскольку a взаимно просто с p .

Это дает r = s , поскольку r и s являются положительными наименьшими остатками. Но их ровно ( p − 1)/2 , поэтому их значения являются перестановкой целых чисел 1, 2, …, ( p − 1)/2 . Следовательно,

${\displaystyle Z=(-1)^{n}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right).}$

Сравнивая с нашей первой оценкой, мы можем исключить ненулевой множитель

${\displaystyle 1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}}$

и у нас осталось

${\displaystyle a^{(p-1)/2}=(-1)^{n}.}$

Это и есть желаемый результат, поскольку по критерию Эйлера левая часть представляет собой просто альтернативное выражение для символа Лежандра . ${\displaystyle \left({\frac {a}{p}}\right)}$

Обобщение

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

Пусть — множество, представляющее собой непересекающееся объединение множеств и . ${\displaystyle I\subset (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle I}$ ${\displaystyle -I=\{-i:i\in I\}}$

Тогда , где . ^[2] ${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{t}}$ ${\displaystyle t=\#\{j\in I:aj\in -I\}}$

В первоначальном заявлении . ${\displaystyle I=\{1,2,\dots ,{\frac {p-1}{2}}\}}$

Доказательство почти такое же.

Приложения

Лемма Гаусса используется во многих, ^{[3] : Гл. 1  [3] : 9} , но далеко не во всех известных доказательствах квадратичного закона взаимности.

Например, Готтхольд Эйзенштейн ^{[3] : 236} использовал лемму Гаусса, чтобы доказать, что если p — нечетное простое число, то

${\displaystyle \left({\frac {a}{p}}\right)=\prod _{n=1}^{(p-1)/2}{\frac {\sin {(2\pi an/p)}}{\sin {(2\pi n/p)}}},}$

и использовал эту формулу для доказательства квадратичной взаимности. Используя эллиптические, а не круговые функции, он доказал кубические и четвертичные законы взаимности. ^{[3] : Гл. 8}

Леопольд Кронекер ^{[3] : Пример 1.34} использовал лемму, чтобы показать, что

${\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right).}$

Перестановка p и q немедленно даёт квадратичную взаимность.

Он также используется в, вероятно, самых простых доказательствах «второго дополнительного закона».

${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8}={\begin{cases}+1{\text{ if }}p\equiv \pm 1{\pmod {8}}\\-1{\text{ if }}p\equiv \pm 3{\pmod {8}}\end{cases}}}$

Высшие силы

Обобщения леммы Гаусса могут быть использованы для вычисления символов вычетов более высокой степени. В своей второй монографии о биквадратичной взаимности, ^{[4] : §§69–71} Гаусс использовал лемму четвертой степени, чтобы вывести формулу для биквадратичного характера 1 + i в Z [ i ] , кольце гауссовых целых чисел . Впоследствии Эйзенштейн использовал версии третьей и четвертой степени, чтобы доказать кубическую и четверную взаимность . ^{[3] : Гл. 8}

нсимвол остатка степени th

Пусть k — алгебраическое числовое поле с кольцом целых чисел , а — простой идеал . Идеальная норма определяется как мощность кольца вычетов. Поскольку является простым, это конечное поле , поэтому идеальная норма равна . ${\displaystyle {\mathcal {O}}_{k},}$ ${\displaystyle {\mathfrak {p}}\subset {\mathcal {O}}_{k}}$ ${\displaystyle \mathrm {N} {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathcal {O}}_{k}/{\mathfrak {p}}}$ ${\displaystyle \mathrm {N} {\mathfrak {p}}=|{\mathcal {O}}_{k}/{\mathfrak {p}}|}$

Предположим, что примитивный корень степени n из единицы и что n и взаимно просты ( т.е. ). Тогда никакие два различных корня степени n из единицы не могут быть сравнимы по модулю . ${\displaystyle \zeta _{n}\in {\mathcal {O}}_{k},}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle n\not \in {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}}$

Это можно доказать от противного, начав с предположения, что mod , 0 < r < s ≤ n . Пусть t = s − r такой, что mod , и 0 < t < n . Из определения корней из единицы, ${\displaystyle \zeta _{n}^{r}\equiv \zeta _{n}^{s}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle \zeta _{n}^{t}\equiv 1}$ ${\displaystyle {\mathfrak {p}}}$

${\displaystyle x^{n}-1=(x-1)(x-\zeta _{n})(x-\zeta _{n}^{2})\dots (x-\zeta _{n}^{n-1}),}$

и деление на x − 1 дает

${\displaystyle x^{n-1}+x^{n-2}+\dots +x+1=(x-\zeta _{n})(x-\zeta _{n}^{2})\dots (x-\zeta _{n}^{n-1}).}$

Положим x = 1 и берем остатки по модулю , ${\displaystyle {\mathfrak {p}}}$

${\displaystyle n\equiv (1-\zeta _{n})(1-\zeta _{n}^{2})\dots (1-\zeta _{n}^{n-1}){\pmod {\mathfrak {p}}}.}$

Так как n и взаимно просты, mod , но при условии, что один из множителей справа должен быть равен нулю. Следовательно, предположение о том, что два различных корня конгруэнтны, ложно. ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle n\not \equiv 0}$ ${\displaystyle {\mathfrak {p}},}$

Таким образом, классы вычетов, содержащие степени ζ _n, являются подгруппой порядка n ее (мультипликативной) группы единиц, поэтому порядок кратен n , и ${\displaystyle {\mathcal {O}}_{k}/{\mathfrak {p}}}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }={\mathcal {O}}_{k}/{\mathfrak {p}}-\{0\}.}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }}$

${\displaystyle {\begin{aligned}\mathrm {N} {\mathfrak {p}}&=|{\mathcal {O}}_{k}/{\mathfrak {p}}|\\&=\left|({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }\right|+1\\&\equiv 1{\pmod {n}}.\end{aligned}}}$

Аналог теоремы Ферма в . Если для , то ^{[3] : Гл. 4.1} ${\displaystyle {\mathcal {O}}_{k}}$ ${\displaystyle \alpha \in {\mathcal {O}}_{k}}$ ${\displaystyle \alpha \not \in {\mathfrak {p}}}$

${\displaystyle \alpha ^{\mathrm {N} {\mathfrak {p}}-1}\equiv 1{\pmod {\mathfrak {p}}},}$

и так как mod n , ${\displaystyle \mathrm {N} {\mathfrak {p}}\equiv 1}$

${\displaystyle \alpha ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}\equiv \zeta _{n}^{s}{\pmod {\mathfrak {p}}}}$

хорошо определен и соответствует единственному корню степени n из единицы ζ _n ^s .

Этот корень из единицы называется символом остатка в n -й степени ${\displaystyle {\mathcal {O}}_{k},}$ и обозначается как

${\displaystyle {\begin{aligned}\left({\frac {\alpha }{\mathfrak {p}}}\right)_{n}&=\zeta _{n}^{s}\\&\equiv \alpha ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}{\pmod {\mathfrak {p}}}.\end{aligned}}}$

Можно доказать, что ^{[3] : Предложение 4.1}

${\displaystyle \left({\frac {\alpha }{\mathfrak {p}}}\right)_{n}=1}$

тогда и только тогда, когда существует такое , что α ≡ η ⁿ mod . ${\displaystyle \eta \in {\mathcal {O}}_{k}}$ ${\displaystyle {\mathfrak {p}}}$

1/нсистемы

Пусть — мультипликативная группа корней n-й степени из единицы, и пусть — представители смежных классов Тогда A называется системой 1/ n mod ^{[3] : Гл. 4.2} ${\displaystyle \mu _{n}=\{1,\zeta _{n},\zeta _{n}^{2},\dots ,\zeta _{n}^{n-1}\}}$ ${\displaystyle A=\{a_{1},a_{2},\dots ,a_{m}\}}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }/\mu _{n}.}$ ${\displaystyle {\mathfrak {p}}.}$

Другими словами, в наборе есть числа , и этот набор представляет собой репрезентативный набор для ${\displaystyle mn=\mathrm {N} {\mathfrak {p}}-1}$ ${\displaystyle A\mu =\{a_{i}\zeta _{n}^{j}\;:\;1\leq i\leq m,\;\;\;0\leq j\leq n-1\},}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }.}$

Числа 1, 2, … ( p − 1)/2 , используемые в исходной версии леммы, представляют собой систему 1/2 (mod p ).

Построение системы ₁ / n просто: пусть M будет представительным множеством для Выберите любое и удалите числа, конгруэнтные из M. Выберите 2 из M и удалите числа, конгруэнтные Повторяйте, пока M не будет исчерпан. Тогда { a ₁ , a ₂ , … a _m } является системой 1/ n mod ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }.}$ ${\displaystyle a_{1}\in M}$ ${\displaystyle a_{1},a_{1}\zeta _{n},a_{1}\zeta _{n}^{2},\dots ,a_{1}\zeta _{n}^{n-1}}$ ${\displaystyle a_{2},a_{2}\zeta _{n},a_{2}\zeta _{n}^{2},\dots ,a_{2}\zeta _{n}^{n-1}}$ ${\displaystyle {\mathfrak {p}}.}$

Лемма длянth полномочия

Лемму Гаусса можно распространить на символ вычета степени n следующим образом. ^{[3] : Предложение 4.3} Пусть — примитивный корень степени n из единицы, простой идеал (т.е. взаимно прост как с γ, так и с n ), и пусть A = { a ₁ , a ₂ , …, a _m } — система mod 1/ n ${\displaystyle \zeta _{n}\in {\mathcal {O}}_{k}}$ ${\displaystyle {\mathfrak {p}}\subset {\mathcal {O}}_{k}}$ ${\displaystyle \gamma \in {\mathcal {O}}_{k},\;\;n\gamma \not \in {\mathfrak {p}},}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}.}$

Тогда для каждого i , 1 ≤ i ≤ m , существуют целые числа π ( i ) , уникальные (mod m ), и b ( i ) , уникальные (mod n ), такие, что

${\displaystyle \gamma a_{i}\equiv \zeta _{n}^{b(i)}a_{\pi (i)}{\pmod {\mathfrak {p}}},}$

а символ остатка в степени n задается формулой

${\displaystyle \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}=\zeta _{n}^{b(1)+b(2)+\dots +b(m)}.}$

Классическая лемма для квадратичного символа Лежандра является частным случаем n = 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 , т.е.

${\displaystyle \gamma a_{i}\equiv \zeta _{n}^{r}a_{p}{\pmod {\mathfrak {p}}}}$

и

${\displaystyle \gamma a_{j}\equiv \zeta _{n}^{s}a_{p}{\pmod {\mathfrak {p}}}.}$

Затем

${\displaystyle \zeta _{n}^{s-r}\gamma a_{i}\equiv \zeta _{n}^{s}a_{p}\equiv \gamma a_{j}{\pmod {\mathfrak {p}}}}$

Поскольку γ и взаимно просты, обе части можно разделить на γ , что дает ${\displaystyle {\mathfrak {p}}}$

${\displaystyle \zeta _{n}^{s-r}a_{i}\equiv a_{j}{\pmod {\mathfrak {p}}},}$

что, поскольку A является системой 1/ n , подразумевает s = r и i = j , показывая, что π является перестановкой множества {1, 2, …, m } .

Тогда, с одной стороны, по определению символа степенного остатка,

${\displaystyle {\begin{aligned}(\gamma a_{1})(\gamma a_{2})\dots (\gamma a_{m})&=\gamma ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}a_{1}a_{2}\dots a_{m}\\&\equiv \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}a_{1}a_{2}\dots a_{m}{\pmod {\mathfrak {p}}},\end{aligned}}}$

и с другой стороны, поскольку π — это перестановка,

${\displaystyle {\begin{aligned}(\gamma a_{1})(\gamma a_{2})\dots (\gamma a_{m})&\equiv {\zeta _{n}^{b(1)}a_{\pi (1)}}{\zeta _{n}^{b(2)}a_{\pi (2)}}\dots {\zeta _{n}^{b(m)}a_{\pi (m)}}&{\pmod {\mathfrak {p}}}\\&\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{\pi (1)}a_{\pi (2)}\dots a_{\pi (m)}&{\pmod {\mathfrak {p}}}\\&\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{1}a_{2}\dots a_{m}&{\pmod {\mathfrak {p}}},\end{aligned}}}$

так

${\displaystyle \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}a_{1}a_{2}\dots a_{m}\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{1}a_{2}\dots a_{m}{\pmod {\mathfrak {p}}},}$

и поскольку для всех 1 ≤ i ≤ m числа a i _и являются взаимно простыми, то a ₁ a ₂ … a _m можно сократить с обеих сторон сравнения, ${\displaystyle {\mathfrak {p}}}$

${\displaystyle \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}{\pmod {\mathfrak {p}}},}$

и теорема следует из того факта, что никакие два различных корня степени n из единицы не могут быть конгруэнтны (mod ). ${\displaystyle {\mathfrak {p}}}$

Связь с переносом в теории групп

Пусть G — мультипликативная группа ненулевых классов вычетов в Z / p Z , а H — подгруппа {+1, −1}. Рассмотрим следующие представители смежных классов H в G ,

${\displaystyle 1,2,3,\dots ,{\frac {p-1}{2}}.}$

Применяя аппарат переноса к этому набору представителей смежных классов, мы получаем гомоморфизм переноса

${\displaystyle \phi :G\to H,}$

что оказывается отображением, которое переводит a в (−1) ⁿ , где a и n такие же, как в формулировке леммы. Лемму Гаусса можно тогда рассматривать как вычисление, которое явно идентифицирует этот гомоморфизм как характер квадратичного вычета.

Смотрите также

• Лемма Золотарева

Ссылки

1. Gauss, Карл Фридрих (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae и другие статьи по теории чисел) (на немецком языке), перевод Х. Мазера (2-е изд.), Нью-Йорк: Челси, ISBN 0-8284-0191-8
2. Кремницер, Коби. Лекции по теории чисел 2022 (PDF) .
3. Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4
4. Гаусс, Карл Фридрих (1832), Theoria residuorum biquadraticorum, Commentatio secunda , vol. 7, Геттинген: Комментарий. Соц. королевская наука