Лемма Гаусса (теория чисел) - Gausss lemma (number theory)

Эта статья посвящена лемме Гаусса в теории чисел. Для использования в других целях см. Лемма Гаусса.

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

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

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

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

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

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

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

Позволять п - количество этих остатков, превышающих п/2. потом

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

куда ${\displaystyle \left({\frac {a}{p}}\right)}$ это Символ Лежандра.

Пример

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

7, 14, 21, 28, 35.

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

7, 3, 10, 6, 2.

Три из этих целых чисел больше 11/2 (а именно 6, 7 и 10), поэтому п = 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}$

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

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

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

${\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}}}$

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

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

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

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

потому что а взаимно прост с п.

Это дает р = s, поскольку р и s положительные наименьшие вычеты. Но есть точно (п − 1)/2 из них, поэтому их значения представляют собой перестановку целых чисел 1, 2, …, (п − 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)}$.

Приложения

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

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

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

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

Леопольд Кронекер^{[2]:Бывший. 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).}$

Переключение п и 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}}}$

Высшие силы

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

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

Основная статья: Символ остатка мощности

Позволять 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}}|}$.

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

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

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

и деление на Икс − 1 дает

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

Сдача Икс = 1 и взяв остатки мода ${\displaystyle {\mathfrak {p}}}$,

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

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

Таким образом, классы вычетов ${\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}}}$

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

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

и с тех пор ${\displaystyle \mathrm {N} {\mathfrak {p}}\equiv 1}$ мод п,

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

хорошо определен и конгруэнтен уникальному пкорень -й степени из единицы ζ_п^s.

Этот корень единства называется псимвол остатка степени th для ${\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}}}$

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

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

если и только если есть ${\displaystyle \eta \in {\mathcal {O}}_{k}}$ такой, что α ≡ η^п мод ${\displaystyle {\mathfrak {p}}}$.

1/п системы

Позволять ${\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}.}$ потом А называется 1/п система мод ${\displaystyle {\mathfrak {p}}.}$^{[2]:Гл. 4.2}

Другими словами, есть ${\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, … (п − 1)/2, использованные в исходной версии леммы, представляют собой систему 1/2 (mod п).

Строительство 1/п система проста: пусть M быть представительным набором для ${\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}}$ из M. Выбирать а₂ из M и удалите числа, соответствующие ${\displaystyle a_{2},a_{2}\zeta _{n},a_{2}\zeta _{n}^{2},\dots ,a_{2}\zeta _{n}^{n-1}}$ Повторяйте до тех пор, пока M истощен. потом {а₁, а₂, … а_м} это 1/п системный мод ${\displaystyle {\mathfrak {p}}.}$

Лемма для псилы

Лемму Гаусса можно распространить на псимвол остатка мощности следующим образом.^{[2]:Предложение 4.3} Позволять ${\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}}}$ взаимно прост с обоими γ и п) и разреши А = {а₁, а₂, …, а_м} быть 1/п системный мод ${\displaystyle {\mathfrak {p}}.}$

Тогда для каждого я, 1 ≤ я ≤ м, есть целые числа π(я), уникальный (мод м), и б(я), уникальный (мод п), такое что

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

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

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

Классическая лемма для квадратичного символа Лежандра является частным случаем п = 2, ζ₂ = −1, А = {1, 2, …, (п − 1)/2}, б(k) = 1 если ак > п/2, б(k) = 0 если ак < п/2.

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

Доказательство пВ лемме-степени используются те же идеи, что и при доказательстве квадратичной леммы.

Существование целых чисел π(я) и б(я), и их уникальность (мод м) и (мод п) соответственно вытекают из того, что Aμ представляет собой репрезентативный набор.

Предположить, что π(я) = π(j) = п, т.е.

${\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}}},}$

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

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

${\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 ≤ я ≤ м, а_я и ${\displaystyle {\mathfrak {p}}}$ взаимно просты, а₁а₂…а_м может быть отменено с обеих сторон сравнения,

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

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

Отношение к переносу в теории групп

Позволять грамм - мультипликативная группа ненулевых классов вычетов в Z/пZ, и разреши ЧАС - подгруппа {+1, −1}. Рассмотрим следующие представители смежного класса ЧАС в грамм,

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

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

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

которая оказывается картой, отправляющей а к (−1)^п, куда а и п такие же, как в формулировке леммы. Тогда лемму Гаусса можно рассматривать как вычисление, которое явно идентифицирует этот гомоморфизм как характер квадратичного вычета.

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

Две другие характеристики квадратов по простому модулю: Критерий Эйлера и Лемма Золотарева.

Рекомендации

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