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

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

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

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

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

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

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

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

Пусть $n —$ количество этих остатков, больших $p /2$ . Затем

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

где $\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. Соответственно лемма Гаусса предсказывает, что

\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} напоминающее одно из простейших доказательств малой теоремы Ферма , можно получить, вычислив произведение

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

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

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

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

|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$ находится в первом диапазоне, мы имеем

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

Теперь обратите внимание, что значения $| ра |$ различны = 1 для $r, 2, \dots, (p - 1)/2$ . Действительно, у нас есть

{\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, \dots, (p - 1)/2$ . Поэтому,

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

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

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

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

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

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

Обобщение

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

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

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

В исходном заявлении $I=\{1,2,\dots ,{\frac {p-1}{2}}\}$ .

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

Приложения

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

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

\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} использовал лемму, чтобы показать, что

\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$ сразу же дает квадратичную взаимность.

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

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

символ n -го остатка

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

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

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

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

и деление на $x - 1$ дает

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

Полагая $x = 1$ и принимая вычеты по модулю ${\mathfrak {p}}$ ,

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

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

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

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

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

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

и поскольку $\mathrm {N} {\mathfrak {p}}\equiv 1$ против $н$ ,

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

корректно определен и конгруэнтен единственному $корню n$ -й степени из единицы ζ _n^с.

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

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

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

тогда и только тогда, когда существует $\eta \in {\mathcal {O}}_{k}$ такая, что $α \equiv η н$ против ${\mathfrak {p}}$ .

1/ n систем

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

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

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

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

Лемма для n- й степени

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

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

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

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

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

Классическая лемма для квадратичного символа Лежандра — это частный случай $n = 2$ , $ζ 2 = -1$ , $A = {1, 2, \dots, (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$ , т.е.

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

и

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

Затем

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

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

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

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

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

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

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

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

так

\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 \leq i \leq m$ , $a i$ и ${\mathfrak {p}}$ взаимно просты, $a 1 a 2 \dots am можно сократить с$ обеих сторон сравнения,

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

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

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

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

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

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

\phi :G\to H,

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

См. также

Zolotarev's lemma

Ссылки

^ Перейти обратно: ^а ^б ^с Гаусс, Карл Фридрих (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, Геттинген: Комментарий. Соц. королевские знания

[Untersuchungen-1] Перейти обратно: ^а ^б ^с Гаусс, Карл Фридрих (1965), Исследования по высшей арифметике (Disquisitiones Arithmeticae & Other Papers on Number Theory) (на немецком языке), перевод Х. Мазера (2-е изд.), Нью-Йорк: Челси, ISBN 0-8284-0191-8

[2] Кремнизер, Коби. Лекции по теории чисел 2022 (PDF) .

[Lemmermeyer-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer , ISBN 3-540-66957-4

[GaussBQ-4] Гаусс, Карл Фридрих (1832), Теория биквадратичных остатков, Commentatio secunda , том 7, Геттинген: Комментарий. Соц. королевские знания

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

v т и Теория чисел
Поля	Алгебраическая теория чисел ( теория полей классов , неабелева теория полей классов , теория Ивасавы , теория Ивасавы–Тейта , теория Куммера ) Аналитическая теория чисел ( аналитическая теория L-функций , вероятностная теория чисел , теория решета ) Геометрическая теория чисел Вычислительная теория чисел Трансцендентная теория чисел Диофантова геометрия ( теория Аракелова , теория Ходжа–Аракелова ) Арифметическая комбинаторика ( аддитивная теория чисел ) Арифметическая геометрия ( анабелева геометрия , P-адическая теория Ходжа ) Арифметическая топология Арифметическая динамика
Ключевые понятия	Числа 0 Натуральные числа Единство Простые числа Составные числа Рациональные числа Иррациональные числа Алгебраические числа Трансцендентные числа P-адические числа ( P-адический анализ ) Арифметика Модульная арифметика Китайская теорема об остатках Арифметические функции
Расширенные концепции	Квадратичные формы Модульные формы L-функции Диофантовые уравнения Диофантово приближение Непрерывные дроби
Категория Список тем Список развлекательных тем Викибук Викиверситет